搜狗笔试题

Dear 丶 2022-05-22 05:26 215阅读 0赞

搜狗：  
1，有n\*n个正方形格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右走。一共走两次，把所有经过的格子的数加起来，求最大值。且两次如果经过同一个格子，则该格子的数只加一次。

思路：

搜索：一共搜（2n-2）步，每一步有四种走法。考虑不相交等条件可以剪去很多枝。

复杂度为O(4^n）

动态规划：

by:[绿色夹克衫][Link 1]

详细算法思路：http://www.51nod.com/question/index.html\#!questionId=657

s\[k\]\[i\]\[j\] = max(s\[k-1\]\[i-1\]\[j-1\],s\[k-1\]\[i-1\]\[j\],s\[k-1\]\[i\]\[j-1\],s\[k-1\]\[j\]\[i\])+map\[i\]\[k-i\]+map\[j\]\[k-j\];

复杂度为O(n^3)

#include <iostream>
    #define MAX(a,b) (a)>(b)?(a):(b)
    using namespace std;
    
    #define N 5
    int map[5][5]={
    	{2,0,8,0,2},
    	{0,0,0,0,0},
    	{0,3,2,0,0},
    	{0,10,0,0,0},
    	{2,0,8,0,2}};
    int sumMax=0;
    int p1x=0;
    int p1y=0;
    int p2x=0;
    int p2y=0;
    int curMax=0;
    
    /*
    编号系统为：
    00000
    11111
    22222
    33333
    44444
    走1次：编号有：0,1
    走2次：编号有：0,1,2
    走5次：编号有：1,2,3,4
    走k次：编号有：l,l+1,l+2...,h-1 //low,high 的计算见code
    编号到map坐标的转换为：
    编号i，则对应map[i][k-i].
    
    dp方程为：
    s[k][i][j] = max(s[k-1][i-1][j-1],s[k-1][i-1][j],s[k-1][i][j-1],s[k-1][j][i])+map[i][k-i]+map[j][k-j];
    */
    int dp(void){
    	int s[2*N-1][N][N];
    	s[0][0][0]=map[0][0];
    	
    	for(int k=1;k<2*N-1;k++){
    		int h = k<N?k+1:N;     //走k次后编号上限
    		int l = k<N?0:k-N+1;   //走k次后编号下限
    		for( int i=l;i<h;i++){
    			for( int j=i+1; j<h; j++){
    					int t=0;
    					if( k==1||i<j-1)
    						t= MAX(t,s[k-1][i][j-1]);
    					if( i-1>=0)
    						t= MAX(t, s[k-1][i-1][j-1]);
    					if( j<h)
    						t= MAX(t, s[k-1][i][j]);
    					if( i-1>=0&&j<h)
    						t= MAX(t, s[k-1][i-1][j]);
    					s[k][i][j]=t+map[i][k-i]+map[j][k-j];
    			}
    		}
    	}
    	return s[2*N-3][N-2][N-1]+map[N-1][N-1];
    }
    
    void dfs( int index){
    	if( index == 2*N-2){
    		if( curMax>sumMax)
    			sumMax = curMax;
    		return;
    	}
    
    	if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))
    	{
    		if( p1x>= p2x && p1y >= p2y )
    			return;
    	}
    
    	//right right
    	if( p1x+1<N && p2x+1<N ){
    		p1x++;p2x++;
    		int sum = map[p1x][p1y]+map[p2x][p2y];
    		curMax += sum;
    		dfs(index+1);
    		curMax -= sum;
    		p1x--;p2x--;
    	}
    
    	//down down
    	if( p1y+1<N && p2y+1<N ){
    		p1y++;p2y++;
    		int sum = map[p1x][p1y]+map[p2x][p2y];
    		curMax += sum;
    		dfs(index+1);
    		curMax -= sum;
    		p1y--;p2y--;
    	}
    
    	//rd
    	if( p1x+1<N && p2y+1<N ) {
    		p1x++;p2y++;
    		int sum = map[p1x][p1y]+map[p2x][p2y];
    		curMax += sum;
    		dfs(index+1);
    		curMax -= sum;
    		p1x--;p2y--;
    	}
    
    	//dr
    	if( p1y+1<N && p2x+1<N ) {
    		p1y++;p2x++;
    		int sum = map[p1x][p1y]+map[p2x][p2y];
    		curMax += sum;
    		dfs(index+1);
    		curMax -= sum;
    		p1y--;p2x--;
    	}
    }
    
    int main()
    {
    	curMax = map[0][0];
    	dfs(0);
    	cout <<"搜索结果："<<sumMax-map[N-1][N-1]<<endl;
    	cout <<"动态规划结果:"<<dp()<<endl;
    	return 0;
    }

2，有N个整数（数的大小为0-255）的有序序列，设计加密算法，把它们加密为K个整数（数的大小为0-255），再将K个整数顺序随机打乱，使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法。  
有三个子问题：  
1，N<=16,要求K<=16\*N.  
2，N<=16,要求K<=10\*N.  
3，N<=64,要求K<=15\*N.

[Link 1]: http://www.51nod.com/question/index.html#!questionId=657