杭电计算机17年复试真题详解

ゞ浴缸里的玫瑰 2022-05-30 06:35 267阅读 0赞

**目录**

### 文章目录 ###

左侧有杭电复试专栏，有需求的小伙伴可以进去查看我对历年真题的一些做法以及我复试的一些日记。

以上也算是为后来人做的一点贡献吧~  
\#**题目一**  
关羽过关斩三将，输入四个人的武力值（大于0小于50），若超过界限需要重新输入，关羽的武力值x，将士武力值为y，满足（x-y）^2+(x-y)+41 若为素数则关羽获胜，若关羽三次获胜输出WIN，若失败则输出失败的将领序号（第几关）。  
**思路：**

1.  首先完成素数打表模块儿，这个素数表在一会儿进行判断的时候使用
2.  完成判断模块儿，判断关羽能不能赢。
3.  格式化输入模块儿，输入不合法，就判定让其继续进行输入。
4.  主程序进行武力值的遍历，每次遍历都判断其合法性，不合法就跳出，并显示是在哪一关开始不合法的

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #define MAX 10000
    using namespace std;
    
    bool prime[MAX];
    void is_prime(){
    	memset(prime,true,MAX);
    	for(int i=2;i<MAX;i++){
    		if(prime[i]){
    			for(int j=2*i;j<MAX;j+=i)
    				prime[j]=false;
    		}		
    	}
    	prime[0]=false;prime[1]=false;
    }
    bool solve(int x,int y){
    	int temp=(x-y)*(x-y)+(x-y)+41;
    	if(prime[temp])//如果公式的计算结果是素数，那么就是关于赢了 
    		return true;
    	else
    		return false;
    }
    int main(){
    	int enemy[4],x,i;
    	is_prime();//进行预处理操作， 
    	while(true){
    		bool flag=true;//标记输入是否合法 
    		scanf("%d",&x);
    		if(x<=0||x>=50)
    			flag=false; 
    		for(i=1;i<4;i++){
    			scanf("%d",&enemy[i]);
    			if(enemy[i]<=0||enemy[i]>=50)
    				flag=false; 
    		}
    		if(flag)
    			break;
    		else{
    			printf("武力值应该在0到50之间\n");
    			continue;
    		}
    	}
    	bool flag=true;//如果输一把立即将此标记为false； 
    	for(i=1;i<4;i++){
    		if(!solve(x,enemy[i])){
    			flag=false;
    			break;
    		}	
    	}
    	if(flag){
    		printf("WIN\n");
    	}
    	else
    		printf("关羽输给了第%d个将军",i);
    	return 0;
    }

**不保证答案正确性，只是提供一种思路**  
\#**题目二：**  
输入N个员工，每个员工输出ID号，上班时间，下班时间，第一行输出最早去的员工的ID和上班时间第二行输出最迟走的员工的ID和下班时间第三行输出工作最久的员工的ID和上班时间(数据瞎编的)  
sampleinput：  
ID100001，07:00:0017:00:00  
ID100002，08:00:0018:00:00  
ID100003，09:00:0021:00:00  
sampleout:  
OPEN:ID100001,07:00:00  
CLOSE:ID100003,21:00:00  
(…):ID100003,12:00:00  
思路：  
1.定义时间结构体，方便存储时间类型的数据  
2.定义学生结构体，存储学生的相关信息，信息里面包含时间结构体  
3.根据题目要求定义三种排序规则cmp1,cmp2,cmp3.然后调用这些排序函数，逐行输出排序之后的结果即可。

#include<stdio.h>
    #include<string.h>
    #include<time.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct time{
    	int hour;
    	int min;
    	int sec;	
    };
    struct employer{
    	char id[100];
    	struct time t1,t2;
    	int diff;
    }buf[100];
    bool cmp1(employer a,employer b){//比较出上班时间最早的 
    	if(a.t1.hour!=b.t1.hour)
    		return a.t1.hour<b.t1.hour;
    	else if(a.t1.min!=b.t1.min)
    		return a.t1.min<b.t1.min;
    	else
    		return a.t1.sec<b.t1.sec;
    }
    bool cmp2(employer a,employer b){//比较出下班时间最晚的 
    	if(a.t2.hour!=b.t2.hour)
    		return a.t2.hour>b.t2.hour;
    	else if(a.t2.min!=b.t2.min)
    		return a.t2.min>b.t2.min;
    	else
    		return a.t2.sec>b.t2.sec;
    }
    bool cmp3(employer a,employer b){//比较出留在单位的时间最长的 
    	return a.diff>b.diff; 
    }
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    		scanf("%s%d:%d:%d %d:%d:%d",&buf[i].id,&buf[i].t1.hour,&buf[i].t1.min,&buf[i].t1.sec,
    		&buf[i].t2.hour,&buf[i].t2.min,&buf[i].t2.sec);
    		buf[i].diff=(buf[i].t1.hour*3600+buf[i].t1.min*60+buf[i].t1.sec)-(buf[i].t2.hour*3600+buf[i].t2.min*60+buf[i].t2.sec);	
    	}
    	//每进行一次比较，就输出一次排序后的结果
    	sort(buf,buf+n,cmp1);
    	printf("%s %d:%d:%d\n",buf[0].id,buf[0].t1.hour,buf[0].t1.min,buf[0].t1.sec);
    	sort(buf,buf+n,cmp2);
    	printf("%s %d:%d:%d\n",buf[0].id,buf[0].t2.hour,buf[0].t2.min,buf[0].t2.sec);
    	sort(buf,buf+n,cmp3);
    	printf("%s %d:%d:%d\n",buf[0].id,buf[0].t1.hour,buf[0].t1.min,buf[0].t1.sec);
    	return 0;
    }

\#**题目三：**  
有一个M*N的材料和一个s*t的模板，从材料中切除模板，求最大能切出来的模板的数量。  
sample input  
：  
3 4  
a b c d  
c d a b  
a c c d  
2 2  
a b  
c d  
sample out  
2  
sample output  
：  
思路：

1.  定义两个字符数组将这两幅图存储起来
2.  使用一个判断模块儿，当进行搜索的时候，判断该位置是否合法(也就是以该位置为起点的S*T图形是否能和输入的S*T图形恰好匹配)
3.  构造一个初始化模块儿，当位置合法的时候，可以选择使用或者不使用这种位置
4.  使用深搜模块儿，逐行进行扫描。
    
    1.  如果到某一位置，判断时合法。我们采取两种行动（要么将大图中匹配的位置标记为0，然后继续深度搜索，要么就当什么事都没有发生，继续逐行扫描）采取这两种操作的原因是，我们不知道哪种操作是更好的结果，所以我们就都试试
    2.  当该行扫描完之后，进入下一行继续进行扫描。
    3.  程序出口是扫描到了最后一行
    4.  因为递归过程中遍历了所有的可能，如果遇到更优解，我们需要进行答案的更新。

写法一：

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    #define MX 100
    #define MY 100
    char map_a[MX][MY];//存储大图
    char map_b[MX][MY];//存储小图
    //char temp[MX][MY];//存储变化中的图 
    using namespace std;
    int m,n,s,t,ans;//用来储存大图和小图的长和宽 
    bool judge(char Map[MX][MY],int x,int y){//判断大图里面是否包含小图 
    	for(int i=0;i<s;i++){
    		for(int j=0;j<t;j++)
    			if(Map[x+i][y+j]!=map_b[i][j])
    				return false;
    	} 
    	return true;
    }
    void dfs(char Map[MX][MY],int x,int y,int max){
    	if(max>ans)//更新答案 
    		ans=max;
    	if(y>=n)//给出程序出口 
    		return ;
    	if(x>=m)
    		dfs(Map,0,y+1,max);//第一列走完了之后，换第二列 
    	else{
    		if(judge(Map,x,y)){
    			char temp[MX][MY]={0};
    			for(int i=0;i<m;i++)//初始化中间图 
    				for(int j=0;j<n;j++)
    					temp[i][j]=Map[i][j];
    			for(int i=0;i<s;i++)
    				for(int j=0;j<t;j++)
    					temp[x+i][y+j]='0';//把参与过匹配的地方标记为0 
    			dfs(temp,x+s,y,max+1);//确定取这一块儿 
    			dfs(Map,x+1,y,max);//不取这一块儿，按部就班继续走 
    		}
    		else
    			dfs(Map,x+1,y,max);//不匹配则按列走 		
    	} 
    
    }
    int main(){
    	cin>>m>>n;//输入大图的长和宽 
    	for(int i=0;i<m;i++)
    		for(int j=0;j<n;j++)
    			cin>>map_a[i][j]; 
    	cin>>s>>t;//输入小图的长和宽 
    	for(int i=0;i<s;i++)
    		for(int j=0;j<t;j++)
    			cin>>map_b[i][j];
    	ans=0;
    	dfs(map_a,0,0,0); 
    	cout<<ans<<endl;	
    	return 0;
    }

写法二：  
此写法更新于0324杭电6教计算机考研教室

#include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    using namespace std; 
    #define MAX 1010
    char map[MAX][MAX],mapb[MAX][MAX];
    char temp[MAX][MAX];//记录中间图的变换，方便在递归中的回溯进行使用 
    int M,N,s,t;//分别为这两个图形的长和宽 
    int Max,ans;//分别记录每次遍历的最大块儿数和最终答案 
    bool judge(char map[][MAX],int i,int j){//传入当前所搜索到的位置 
    	int x=i;int y=j;//x来表示行数，y来表示列数 
    	for(i=0;i<s;i++)//判断两个图是否匹配 
    		for(j=0;j<t;j++)
    			if(map[x+i][y+j]!=mapb[i][j])
    				return false;
    	return true;
    }
    init_temp(int x,int y){//将已经遍历过的位置标记 
    	for(int i=0;i<M;i++) 
    		for(int j=0;j<N;j++)
    			temp[i][j]=map[i][j];
    	for(int i=0;i<s;i++)
    		for(int j=0;j<t;j++)
    			temp[x+i][y+j]='0'; 
    }
    void dfs(char map[][MAX],int x,int y,int Max){
    	if(ans<Max)//ans来记录块儿的数量 
    		ans=Max;
    	if(x>=M){//记录递归出口,走到最后一行就返回 
    		return ;
    	}
    	for(int i=y;i<N;i++){//对x行的每一列都进行搜索
    		 if(judge(map,x,i)){//满足判段进行下一步递归 
    		 	init_temp(x,i);
    			dfs(temp,x,i+t,Max+1);//将遍历过的位置标记，然后继续遍历	
    		 }	 
    	} 
    	dfs(map,x+1,0,Max);
    }
    int main(){
    	cin>>M>>N;
    	for(int i=0;i<M;i++)	
    		for(int j=0;j<N;j++)
    			cin>>map[i][j];
    	cin>>s>>t;
    	for(int i=0;i<s;i++)
    		for(int j=0;j<t;j++)
    			cin>>mapb[i][j];
    	ans=0;Max=0;
    	dfs(map,0,0,0);	
    	cout<<ans<<endl;
    	return 0;
    }