TeilyMa's BlogHomeArchivesTagsCategories
杭电2017年计算机复试真题
|文章
字数总计: 2k|阅读时长: 8 分钟

注意：此复试题目是根据CSDN博客逃离地球的小小呆上发布的回忆版整理复原。为了恢复试题的原貌，我根据试题要求进行合理的脑补，按照oj系统的风格补全了试题的Problem Description、Input、Output、Sample Input、Sample Out等内容，并加入了详解、具体的代码实现。因为是复原版，不能保证当时的题目就是这么呈现的，也不能说明考场上的试题就是oj风格叙述的，仅供大家参考。有什么错误、不合理的地方欢迎指出。
原创不易，还请大家多支持

第一题

Problem Description

关羽过关斩三将，输入关羽和其他三将的武力值，输出关羽成功还是失败

Input

输入包括关羽的武力值，将领1武力值，将领2武力值，将领3武力值，武力值0<k<50

Output

检查输入的武力值是否合法，不合法则提示重新输入。关羽武力值x，将领武力值y满足(x-y)^2+(x-y)+41为素数时关羽获胜，关羽三次获胜输出WIN，若失败则输出失败的将领序号（第几关）

Sample Input

46
30
20
10

Sample Output

Win

这道题没什么技巧性，实质上就是素数的判断问题，同时注意对数据合法性的判断，这里我是用了一个方法来专门做此事

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <math.h>
void input(int& x)//输入武力值，并判断是否合法
{
	scanf("%d", &x);
	while (x <= 0 || x >= 50)
	{
		printf("武力值应该在0到50之间\n");
		scanf("%d", &x);
	}
}
bool IsPrime(int x)//判断是否是素数
{
	if (x == 1) return false;
	int temp = sqrt(x) + 1;
	for (int i = 2; i < temp; i++)
		if (x % i == 0)
			return false;
	return true;
}
int main() {
	int x, y;
	int cnt = 0;//计数器
	input(x);//输入关羽武力值
	while (cnt<3)
	{
		cnt++;
		input(y);//输入将领武力值
		if (!IsPrime((x - y) * (x - y) + (x - y) + 41))//若不是素数，则关羽失败
		{
			printf("关羽败给了%d号将领\n", cnt);
			return 1;
		}
	}
	printf("Win\n");
	return 0;
}

第二题

Problem Description

输入N个员工，每个员工输出ID号，上班时间，下班时间。第一行输出最早去的员工的ID和上班时间；第二行输出最迟走的员工的ID和下班时间；第三行输出工作最久的员工的ID和上班时间

Input

有多组测试用例。每组测试用例第一行包含一个正整数n，表示输入的员工数。接下来有n行，每一行包括员工ID、上班时间、下班时间。每个字段用空格隔开

Output

第一行输出最早去的员工的ID和上班时间；第二行输出最迟走的员工的ID和下班时间；第三行输出工作最久的员工的ID和上班时间

Sample Input

3
100001 07:00:00 17:00:00
100002 08:00:00 18:00:00
100003 09:00:00 21:00:00

Sample Output

ID100001 07:00:00
ID100003 21:00:00
ID100003 12:00:00
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Staff
{
	struct time {
		int hour;
		int min;
		int sec;
	};
	char ID[20];
	time start, end;
	int duration;//总的工作时间，以秒计
	void getDura() {
		int h, m, s;
		h = end.hour - start.hour;
		m = end.min - start.min;
		s = end.sec - start.sec;
		if (s<0)
		{
			s += 60;
			m--;
		}
		if (m<0)
		{
			m += 60;
			h--;
		}
		duration = h * 3600 + m * 60 + s;
	}
}staffs[50];
bool cmp1(Staff a,Staff b)//对上班时间排序
{
	if (a.start.hour!=b.start.hour)//若小时不相等，按小时排
		return a.start.hour < b.start.hour;
	if (a.start.min!=b.start.min)//若分钟不相等，按分钟排
		return a.start.min < b.start.min;
	else//最后按秒排
		return a.start.sec < b.start.sec;
}
bool cmp2(Staff a, Staff b)//对下班时间排序
{
	if (a.end.hour != b.end.hour)//若小时不相等，按小时排
		return a.end.hour > b.end.hour;
	if (a.end.min != b.end.min)//若分钟不相等，按分钟排
		return a.end.min > b.end.min;
	else//最后按秒排
		return a.end.sec > b.end.sec;
}
bool cmp3(Staff a, Staff b)//对工作时间排序
{
	return a.duration > b.duration;
}
int main() {
	int n;
	while (scanf("%d",&n)!=EOF)
	{
		int i;
		for (i = 0; i < n; i++)
		{
			scanf("%s", &staffs[i].ID);
			scanf("%d:%d:%d", &staffs[i].start.hour, &staffs[i].start.min, &staffs[i].start.sec);
			scanf("%d:%d:%d", &staffs[i].end.hour, &staffs[i].end.min, &staffs[i].end.sec);
			staffs[i].getDura();//计算工作时间
		}
		sort(staffs, staffs + i, cmp1);//使用第一种排序方式
		printf("%s %02d:%02d:%02d\n", staffs[0].ID, staffs[0].start.hour, staffs[0].start.min, staffs[0].start.sec);
		sort(staffs, staffs + i, cmp2);//使用第二种排序方式
		printf("%s %02d:%02d:%02d\n", staffs[0].ID, staffs[0].end.hour, staffs[0].end.min, staffs[0].end.sec);
		sort(staffs, staffs + i, cmp3);//使用第三种排序方式
		printf("%s %02d:%02d:%02d\n", staffs[0].ID, staffs[0].start.hour, staffs[0].start.min, staffs[0].start.sec);
	}
	return 0;
}

这道题可以看做是历年真题基础知识点的一个汇总，其中用到的排序几乎年年涉及；然后是关于时间差的计算在2013年第一题中就有出现过。

第三题

Problem Description

有一个长M宽N的材料和一个长s宽t的模板，从材料中切除模板，求最大能切出来的模板的数量。

Input

输入共有四部分，第一部分有两个数字M、N，分别表示大矩阵有M行N列。第二部分有M行，是材料的元素。第三部分也有两个数字s、t(s<=M,t<=N)，分别代表小矩阵有s行t列。第四部分有s行，是模板的元素。

Output

输出可以从材料中切除多少块模板，输出占一行

Sample Input

3 4
abcd
cdab
accd
2 2
ab
cd

Sample Output

2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>

char Matrix1[101][101];//存储材料矩阵
char Matrix2[101][101];//存储模板矩阵
int M, N, s, t;
int ans = 0;//当前求出的最多可以分割出的模板数
int Max = 0;//最大可以分割出的模板数
bool judge(char matrix[][101],int x, int y) {
	for (int i = 0; i < s; i++)
		for (int j = 0; j < t; j++)
			if (matrix[x+i][y+j]!=Matrix2[i][j])
				return false;
	return true;
}
void markMatrix(int x,int y) {//标记已切出的模板
	for (int i = 0; i < s; i++)
		for (int j = 0; j < t; j++)
			Matrix1[x + i][y + j] = '0';
}
void DFS(char matrix[][101], int x, int y, int Max) {
	if (ans<Max)
		ans = Max;
	if (x >= M) return;//递归出口
	for (int i = y; i <= N-t; i++)
	{
		if (judge(matrix, x, i))//若此位置可以切出模板，则标记此位置
		{
			markMatrix(x, i);
			DFS(matrix, x, i + t, Max + 1);//继续递归
		}
	}
	DFS(matrix, x + 1, 0, Max);
}
int main()
{
	scanf("%d%d", &M, &N);
	for (int i = 0; i < M; i++)//给材料矩阵赋值
		scanf("%s", Matrix1[i]);
	scanf("%d%d", &s, &t);
	for (int i = 0; i < s; i++)//给模板矩阵赋值
		scanf("%s", Matrix2[i]);
	DFS(Matrix1, 0, 0, 0);
	printf("%d\n", ans);
	return 0;
}

这道题与2016年第四题有很多相似的地方，甚至核心思路都完全一致。这个程序代码是我参考博主逃离地球的小小呆的DFS写的，但是感觉这里使用DFS有点勉强，完全可以不用的。当然也有可能是我对DFS不熟悉。这道题的思路主要就是把模板放到材料上一一比对，若完全相同，则标记材料该模板已切出，循环遍历至材料矩阵的最后一行即可得到答案。

文章作者: Teily
文章链接: https://teily.cn/article/HDU2017.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 TeilyMa's Blog！
杭电复试考试相关