本来抱着做着玩的想法，结果被教育了。
满分 100 分，结果只拿了 72 分，尴尬。乙级题库是上个星期做完了？反正是过去有一段时间了，最近都在 Leetcode 上打码了，PAT 玩的少，好像有点手生了？话说回来，这还是第一次做 PAT 的考试题，不熟悉也是正常吧，给自己一点安慰。
废话少说，直接看题目吧。
7-1 暴力破解
旅行箱上的密码锁通常都只有 3 位数字，如果忘了密码，只要有足够的耐心，哪怕用逐一枚举的办法，也可以暴力破解。如果还能隐约记得数字的范围，则可以大大降低破解的工作量。
本题就请你根据用户记忆中的数字范围，列出所有可能的密码。
输入格式
输入第一行给出一个正整数 n（≤8），随后一行列出 n 个 0 - 9 范围内的数字，是用户记忆中可能属于密码的数字。题目保证 n 个数字没有重复，数字间以空格分隔。
输出格式
按照密码组成的 3 位数从小到大的顺序，输出这 n 个数字能组成的所有可能的 3 位数密码。要求每行输出 10 个，同行数字以 1 个空格分隔，行首尾不得有多余空格。注意：如果有前导零，也不可忽略。
输入样例
1 | 3 |
输出样例
1 | 222 225 228 252 255 258 282 285 288 522 |
Analysis
这个题迷惑性挺强的，第一眼看过去，以为是求 3 个数字全排列的题目。实际上也确实是这样的题目，但是没有那么简单。因为数字个数是不限定的，可能会给少于 3 个的数字，也可能会给大于 3 个的数字。所以，大体上就有 2 种情况：
- n >= 3。
- n < 3。
在考试时间写这个问题的时候，一直在纠结怎么输出，怎么能枚举出所有的可能。一会觉得直接输出数字方便，一会又觉得直接算出来用集合自动排序更简单。结果最后还是选择了集合，因为集合既可以避免重复选取，又可以排序。
那么，接下来要考虑的问题就是把所有可能的数字算出来了。因为只需要组成 3 位数，所以按照之前的分析就可以知道：
- n >= 3，此时只用分别选择数字作为百位、十位和个位就行了，反而比较容易处理。
- n = 2，因为限定了最后得到的 3 位数中必须要有 2 个数字，从排列的角度来讲，就是往 2 个数字组成的队列中插空，但是这两个数字也是可以交换位置的，所以就是 2 * 3 = 6，一共 6 种可能的组合方式。
- n = 1，与 n = 2 时同理，但此时只用将唯一的数字分别当作百位、十位和个位，计算一次就行了。
- n = 0，这个情况，做题的时候忘了...实际上就 000-999 这 1000 个数。
以上就是做题时的分析了，浪费了挺多时间的。
Code
这是当时写的代码，真乱啊。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
75
76
77
78
79
using namespace std;
set<int> password;
const int maxn = 10 + 5;
int arr[maxn] = {0}, n;
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
int tmp;
if(n == 1) {
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
tmp = arr[0] * 100 + i * 10 + j;
password.insert(tmp);
}
}
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
tmp = i * 100 + arr[0] * 10 + j;
password.insert(tmp);
}
}
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
tmp = i * 100 + j * 10 + arr[0];
password.insert(tmp);
}
}
} else if(n == 2) {
for(int i = 0; i < 10; i++) {
tmp = i * 100 + arr[0] * 10 + arr[1];
password.insert(tmp);
}
for(int i = 0; i < 10; i++) {
tmp = arr[0] * 100 + i * 10 + arr[1];
password.insert(tmp);
}
for(int i = 0; i < 10; i++) {
tmp = arr[0] * 100 + arr[1] * 10 + i;
password.insert(tmp);
}
for(int i = 0; i < 10; i++) {
tmp = i * 100 + arr[1] * 10 + arr[0];
password.insert(tmp);
}
for(int i = 0; i < 10; i++) {
tmp = arr[1] * 100 + i * 10 + arr[0];
password.insert(tmp);
}
for(int i = 0; i < 10; i++) {
tmp = arr[1] * 100 + arr[0] * 10 + i;
password.insert(tmp);
}
} else {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
tmp = arr[i] * 100 + arr[j] * 10 + arr[k];
password.insert(tmp);
}
}
}
}
// cout << password.size() << endl;
set<int>::iterator it = password.begin();
int cnt = 0;
for(; it != password.end(); it++) {
printf("%03d", *it);
cnt++;
if(cnt == password.size()) cout << endl;
else if(cnt % 10) cout << ' ';
else cout << endl;
}
return 0;
}
上面的代码，提交上去之后，只拿了 12 分，还有 2 个测试点没过。
现在想想，可能有个测试点是 n = 0 的情况吧，那另外一个测试点呢？
7-2 学霸
所谓“学霸”，就是每个学期选课学时最长的人。本题就给你所有课程的学时和选课名单，请你找出那个学霸。如果有总学时并列最多的情况，则选那个选课门数最多的。如果还有并列，就按学号升序输出他们吧~
输入格式
输入在第一行中给出一个正整数：N（≤5000）为课程总数。随后 N 行，每行给出一门课的选课信息，格式如下1
学时 人数 选课人1 选课人2 ……
其中 学时 是该课程的学时，一个不超过 100 的正整数；人数 是该课程的选课人数，为不超过 200 的非负整数；选课人i 是第 i 个选课学生的编号，是一个 5 位数字。题目保证不同学生对应的编号不同，且同一门课程的选课名单中没有重复的学生。
输出格式
首先在一行中输出学霸（们）的选课总学时和门数，随后在下一行中按照编号升序输出所有满足题面描述的学霸。编号间以 1 个空格分隔，行首尾不得有多余空格。题目保证至少存在一位学霸。
输入样例
1 | 5 |
输出样例
1 | 96 4 |
Analysis
第二个题目是比较简单的，但是也有坑。而且，给的信息很多，需要仔细读题才能确定那些信息是用来得到结果的。一开始本来是想用 map 来做的，后面看到学生编号反正是个 5 位数，我直接散列得了。这个思路也没错，但是当时做的时候没有考虑到输出的限制，题目已经说了有并列的情况了，所以还需要对最后的结果进行排序。但是，做题的时候，有点方，完全没有想到这里来。其实就是太方了，搞得题目没有读清楚，就开始写了。
Code
这是当时写的代码，因为没有考虑到并列的情况，所以也只拿了 14 分...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
using namespace std;
const int maxn = 100000 + 5;
int studytimes[maxn] = {0}, amount[maxn] = {0};
int main() {
int n, time, peos, id;
cin >> n;
while(n--) {
cin >> time >> peos;
while(peos--) {
cin >> id;
studytimes[id] += time;
amount[id]++;
}
}
int max_time = studytimes[0], max_amount = amount[0];
for(int i = 1; i < maxn; i++) {
if(max_time < studytimes[i]) max_time = studytimes[i];
if(max_amount < amount[i]) max_amount = amount[i];
}
cout << max_time << ' ' << max_amount << endl;
bool flag = true;
for(int i = 1; i < maxn; i++) {
if(max_time == studytimes[i] && max_amount == amount[i]) {
if(flag) {
printf("%05d", i);
flag = false;
} else printf(" %05d", i);
}
}
return 0;
}
现在再看，真是不应该。
7-3 排课
排课是个世界难题。
假设每个学期有 N 个教学班的课需要排，每周有 M 个时间段可以上课，全校共有 K 间教室，不同排课组合方案的个数可能会超过整个宇宙的质子数。更为复杂的是，每个学期排课前，学校还会收集每个教学班任课老师不能上课的时间段，还要保证排课不与老师的时间安排起冲突。
当然，本题不是要求你实现一个排课算法，而是要求你实现一个排课方案检查算法。即给定每个教学班上课的时间和地点，你需要检查这个时间段和地点是否只有这一个班上课，并且这个上课时间不会正好是任课老师不能上课的时间。
输入格式
输入在第一行中给出三个正整数：$N（≤10^4）$为教学班总数；$M（≤40）$为一周内上课时间段的个数；$K（≤10^3）$为教室总数。数字间以空格分隔。以下我们就将教学班、时间段、教室分别从 1 开始顺序编号。
随后 N 行，每行给出一个教学班的任课教师时间限制和排课的信息。格式如下：1
L T[1] ... T[L] Time Room
其中L是任课教师的时间限制数量（< M），后面给出L个该老师不能上课的时间段编号；Time是该教学班安排的上课时间段编号，Room 是上课教室编号。我们假设每个教学班的任课老师都不一样。
输出格式
如果给定的课表安排是完全无冲突的，则在一行内输出：Perfect Arrangement for N classes!其中N是教学班数量。
如果课表有冲突，则需要输出冲突原因。我们首先假设教学班是按照编号递增序进行排课的，教学资源先到先得。如果后面安排的教学班 A 跟前面的教学班 B 排在了同一个时间和地点，则在一行中输出ERROR: Conflict between A and B.，此时教学班 A 暂不安排。如果教学班 A 的上课时间跟任课教师有冲突，则在一行中输出ERROR: Conflict with instructor for A.。当两种冲突都发生时，分两行输出，先输出教学班冲突的信息。
输入样例 1
1 | 5 20 10 |
输出样例 1
1 | Perfect Arrangement for 5 classes! |
输入样例 2
1 | 5 20 10 |
输出样例 2
1 | ERROR: Conflict between 2 and 1. |
Analysis
这个题跟第二道题是一个类型的题目，都是信息给的很多，需要根据题目条件，运用不同的信息。唯一的坑点，就是要读清楚题目，但遗憾的是，这与我无关...
Code
这是当时写的代码，提交后是 15 分...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
const int maxn = 10000 + 5;
struct Class {
int timelimit[45];
int time, room;
} cla[maxn];
int main() {
int n, m, k, l, time_t, room_t;
scanf("%d %d %d", &n, &m, &k);
scanf("%d", &l);
for(int j = 0; j < l; j++) {
scanf("%d", &cla[1].timelimit[j]);
}
scanf("%d %d", &cla[1].time, &cla[1].room);
bool flag1 = true;
for(int i = 2; i <= n; i++) {
scanf("%d", &l);
for(int j = 0; j < l; j++) {
scanf("%d", &cla[i].timelimit[j]);
}
scanf("%d %d", &cla[i].time, &cla[i].room);
for(int j = 1; j < i; j++) {
if(cla[i].time == cla[j].time && cla[i].room == cla[j].room) {
printf("ERROR: Conflict between %d and %d.\n", i, j);
flag1 = false;
break;
}
}
for(int j = 0; j < l; j++) {
if(cla[i].time == cla[i].timelimit[j]) {
printf("ERROR: Conflict with instructor for %d.\n", i);
cla[i].time = -1;
flag1 = false;
break;
}
}
}
if(flag1) printf("Perfect Arrangement for %d classes!\n", n);
return 0;
}
7-4 简易测谎
测谎通常使用一套准备好的问题提问被测试者，通过分析被测试者的反应得到结果。比较高级的测谎技术会使用测谎仪，监视被测试者的生理活动状况。我们这里的简易测谎则是通过对问题答案的特征分析来做出判断。
首先我们要求被测试者做完 N 道单选题，每道题有 8 个选项，由小写英文字母a-h来表示。这样就得到一个长度为 N 的、由a-h小写英文字母组成的字符串。对每个字符串打分，得分超过某个给定阈值 T 的就判断为“疑似说谎者”。打分原则如下：
- 以
f开头的，得分 −2； - 以
a结尾的，得分 −1； - 对于每一段长度大于 5 的连续选择同一字母的最长子串，得分 +3；
a后面紧跟e或h的，得分 −4；
对于每一段长度大于 3 的连续选择相邻递增字母的最长子串（例如abcd或defgh），得分 +5。
本题就请你写程序完成对被测试者的判断。
输入格式
输入第一行给出 3 个正整数：N（6≤N≤100）为测谎问卷的题目数；T （≤100）为判断说谎的得分阈值；K（≤100）为被测试者人数。
随后 K 行，每行给出一个被测试者的答案字符串。
输出格式
对每个被测试者的答案，在一行中输出其得分。如果分数超过阈值，则在其分数后输出!!!。
输入样例
1 | 12 1 6 |
输出样例
1 | -1 |
Analysis
这个题感觉是这套卷子最常规的一道题了，因为很明显就是字符串处理的题目。但这个题目的坑点在于，要分开讨论的情况太多了，比较费时间。特别是连续长度大于 5 的情况和连续相邻递增字母的情况，需要仔细梳理一下下标的对应关系，实际上，并不是一个难题。
Code
这是当时写的代码，提交后是 18 分。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
const int maxn = 100 + 5;
char str[maxn];
int main() {
int n, T, t, k;
scanf("%d %d %d", &n, &T, &k);
while(k--) {
scanf("%s", str);
t = 0;
if(str[0] == 'f') t -= 2;
if(str[n - 1] == 'a') t -= 1;
for(int i = 0; i < n; i++) {
if(str[i] == 'a') {
if(str[i + 1] == 'e' || str[i + 1] == 'h') {
t -= 4;
i = i + 1;
}
}
if(str[i] == str[i + 1]) {
int j;
for(j = i + 2; j < n; j++) {
if(str[i] != str[j]) break;
}
if(j - i > 5) {
t += 3;
i = j;
i--;
}
}
if(str[i + 1] == str[i] + 1) {
int j;
for(j = i; j < n; j++) {
if(str[j + 1] != str[j] + 1) break;
}
if(j - i >= 3) {
t += 5;
i = j;
i--;
}
}
}
printf("%d", t);
if(t > T) printf("!!!");
printf("\n");
}
return 0;
}
7-5 前K大数
本题目标非常简单：给定 N 个整数，找出前 K 个最大的数，并按递减序输出。
输入格式
输入第一行给出 2 个正整数$N (≤10^6) $和 $K (≤5)$。随后一行给出 N 个整数键值，范围在区间$[−2^{30} ,2^{30}]$内，以空格分隔。
输出格式
按递减序在一行中输出前 K 个最大的数。
注意：一行中输出的数字间须以 1 个空格分隔，行首尾不得有多余空格。
输入样例 1
1 | 10 4 |
输出样例 1
1 | 80 60 40 30 |
输入样例 2
1 | 4 5 |
输出样例 2
1 | 99 23 1 -17 |
Analysis
这个题的形式倒是很简单，不过想拿满分也不是那么容易。因为题目没说不会出现重复元素，所以，很明显的一个坑点就是重复元素。一开始想到的做法是先排序，然后用 hashmap 把输出过的元素标记了，结果提交之后直接就 Time Limited Exceeded 跟 Memory Limited Exceeded 了。然后就直接跳过做前面的题去了，当时这道题是第三个做的。
Code
这是当时写的代码，提交之后是 13 分。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
using namespace std;
bool cmp(int a, int b) {
return a > b;
}
unordered_map<int, int> ht;
const int maxn = 1000000 + 5;
int numbers[maxn] = {0};
int main() {
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++) {
cin >> numbers[i];
}
sort(numbers, numbers + n, cmp);
bool flag = true;
int index = 0;
while(k) {
if(ht[numbers[index]] == 0) {
if(flag) {
cout << numbers[index];
flag = false;
} else cout << ' ' << numbers[index];
ht[numbers[index]] = 1;
k--;
}
index++;
if(index >= n) break;
}
return 0;
}
其实，感觉上面的代码正常应该不会超时，应该是那个测试样例死循环了。至于内存超限，只能不用 hashmap，再想想其他的做法了。
Summary
乙级题库的最后 10 道题好像是 2019 年的真题，具体是啥时候的就不知道了。但是，个人感觉比这次考试的要容易一些。特别是 1101、1102、1103、1106、1107、1108，基本跟送分题一样，但这张卷子的前 3 道题，不是那么明显的送分题，埋了一点点坑。这套卷子的第 4 题跟第 5 题就稍微常规一点了。
不过，话说回来，不知道是不是这几天没玩 PAT，所以手真的生了的缘故，刚一拿到题目，竟然有点无从下手的感觉。
总而言之，先把这几道题目的 AC 代码写出来吧。
