很久没来 PAT 了，没想到乙级题库新增了 5 道题😁~百度了一下，发现这是 2020 年春考 PAT 的原题，正好是周末的时间，做一下。
1111 对称日
Analysis
题意很清晰，把字母转换为数字，然后判断是否是回文串即可，所以需要解决的问题有两个：
- 字母转换为数字，这个问题题库有类似的题
- 判断回文串，这是 C 语言的课后习题😂
注意这个题有个细节，默认的格式是YYYYMMDD，年、月、日的位数已经定死了，如果遇到某一项位数不够的情况，需要补前导零，不如 1 月，在整个字符串内是01。
当然，也可以不从字符串的角度来思考这个问题，直接从数字的角度来思考也是一样的。
Code
method 1
1 |
|
从数字的角度思考，最后还是要回归到字符串上，因为最后还要判断回文串。
method 2
1 |
|
1112 超标区间
Analysis
这个题是个简单的滑动窗口（或者说双指针）题目，利用类似的思想即可。
设置两个指针A和B，从A指针进入循环，每次遇到一个符合条件的数字时，利用B指针从当前的横坐标开始遍历数组，找出连续符合的所有数字，这样就可以利用A、B指针求出当前区间了，然后再更新循环变量的值。
唯一需要多思考一下的边界是当数组最后一个元素符合条件时，B的值是数组的长度，所以循环条件使用B < N和A < N即可，实际上这个题也规定了横坐标的值是$[0, N - 1]$。
Code
1 |
|
1113 钱串子的加法
Analysis
不多说了，一个常规的进制转换题型，从 16 进制换成了 30 进制而已。
需要注意的一个测试点是输入多个0的情况，比如输入000和000，最后结果不是000，而是0，所以需要删除最后结果中的前导 0。
Code
1 |
|
代码中的 map 可以使用简单的int数组和char数组来完成。
1114 全素日
Analysis
题意很明确了，需要解决两个问题：
- 逐个拆分出所有的数字情况
- 判断是否是素数
针对第一个问题，直接用 string 容器来完成即可。而第二个问题，最大的数也不过 99991231，直接判断也是不会超时的。
Code
1 |
|
1115 裁判机
Analysis
题目略长，实际上是写一个类似数字接龙的游戏，要求就是题目的要求了。一开始以为是个模拟题，所以直接模拟了，但是有个 4 分测试点过不去。仔细一想，应该还得有点哈希的思路，换了后，结果内存超限了。好吧，看来是明确禁止使用比较大的容器了，只好利用int数组代替 unordered_map 了，再次提交，AC。
Code
version 1
这是第一版代码了，写的臭长臭长的，思路不够简洁，就是纯纯的模拟，最后是测试点 5 超时了。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
using namespace std;
int matrix[15][1005] = {0}, N, M;
unordered_map<int, set<int>> number2diff;
bool player[15] = {false};
int main(int argc, char const *argv[]) {
int init1, init2;
scanf("%d %d", &init1, &init2);
set<int> st1, st2;
if(init1 > init2)
st1.insert(init1 - init2);
else
st2.insert(init2 - init1);
number2diff.insert({init1, st1});
number2diff.insert({init2, st2});
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
scanf("%d", &matrix[i][j]);
for(int j = 1; j <= M; j++) {
for(int i = 1; i <= N; i++) {
int tmp = matrix[i][j];
if(player[i] == true) continue;
if(number2diff.find(tmp) != number2diff.end()) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
bool flag = false;
for(auto &p: number2diff) {
auto it = p.second.lower_bound(tmp);
if(it != p.second.end() && *it == tmp) {
flag = true;
break;
}
}
if(!flag) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
set<int> st;
for(auto &p: number2diff) {
if(p.first < tmp)
st.insert(tmp - p.first);
}
number2diff.insert({tmp, st});
for(auto &p: number2diff) {
if(p.first > tmp) {
p.second.insert(p.first - tmp);
}
}
}
}
}
}
vector<int> winner;
for(int i = 1; i <= N; i++) {
if(player[i] == false) winner.push_back(i);
}
if(winner.size() == 0)
printf("No winner.\n");
else {
printf("Winner(s):");
for(int &i: winner)
printf(" %d", i);
}
return 0;
}
version 2
第二版代码，使用了一点哈希的思路。这个思路的来源是突然发现题目只要求每个人给出数字不能重复出现，并未要求数字之间的差值不能重复出现。那么，只需要记录每个人每回合给出数字之前的所有差值是否出现，然后再满足：
- 当前给出的数字与之前给出的数字不重复
- 当前给出的数字与之前给出的数字的差值存在
为了方便起见，使用 unordered_set 来当作 hashmap，但是下面这段代码还是超时了。
估计姥姥是铁了心不让用容器了...🤣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
using namespace std;
int matrix[15][1005] = {0}, N, M;
bool player[15] = {false};
set<int> num;
unordered_set<int> diff;
int main(int argc, char const *argv[]) {
scanf("%d %d", &N, &M);
num.insert(N);
num.insert(M);
diff.insert(abs(N - M));
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
scanf("%d", &matrix[i][j]);
}
}
for(int j = 1; j <= M; j++) {
for(int i = 1; i <= N; i++) {
int tmp = matrix[i][j];
if(player[i] == true) continue;
if(num.find(tmp) != num.end()) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
bool flag = false;
if(diff.find(tmp) != diff.end())
flag = true;
if(!flag) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
for(auto &i: num)
diff.insert(abs(i - tmp));
num.insert(tmp);
}
}
}
}
vector<int> winner;
for(int i = 1; i <= N; i++) {
if(player[i] == false) winner.push_back(i);
}
if(winner.size() == 0)
printf("No winner.\n");
else {
printf("Winner(s):");
for(int &i: winner)
printf(" %d", i);
}
return 0;
}
version 3
注意到题目给定数字的范围在$[1, 10^5]$，所以可以用一个int数组来当作 hashmap。
不过，这段代码也是 320ms 左右通过测试点 5 的，是不是还可以优化下？
最容易想到的优化方式就是将 set 替换为 unordered_set，哈哈，试了下，测试点 5 的时间成了 170ms 了😂。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
using namespace std;
int matrix[15][1005] = {0}, N, M;
bool player[15] = {false};
set<int> num;
const int MAXN = 100000 + 5;
int diff[MAXN] = {0};
int main(int argc, char const *argv[]) {
scanf("%d %d", &N, &M);
num.insert(N);
num.insert(M);
diff[abs(N - M)] = true;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
scanf("%d", &matrix[i][j]);
}
}
for(int j = 1; j <= M; j++) {
for(int i = 1; i <= N; i++) {
int tmp = matrix[i][j];
if(player[i] == true) continue;
if(num.find(tmp) != num.end()) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
bool flag = false;
if(diff[tmp] == true)
flag = true;
if(!flag) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
for(auto &i: num)
diff[abs(i - tmp)] = true;
num.insert(tmp);
}
}
}
}
vector<int> winner;
for(int i = 1; i <= N; i++) {
if(player[i] == false) winner.push_back(i);
}
if(winner.size() == 0)
printf("No winner.\n");
else {
printf("Winner(s):");
for(int &i: winner)
printf(" %d", i);
}
return 0;
}
version 4
仔细想了下，前面提到了每个人提出的数字不能与之前的数字重复，那这个问题不还是 hashmap 的问题吗😂？
所以，使用两个 hashmap 来记录数字和差值是否出现，再用一个 vector 来保存出现过的数字即可。
提交了下，测试点 5 耗时才 50ms ，还是 C 语言好使😆。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
using namespace std;
int matrix[15][1005] = {0}, N, M;
bool player[15] = {false};
const int MAXN = 100000 + 5;
vector<int> nums;
bool num[MAXN] = {false}, diff[MAXN] = {false};
int main(int argc, char const *argv[]) {
scanf("%d %d", &N, &M);
nums.push_back(N), nums.push_back(M);
num[N] = 1, num[M] = 1;
diff[abs(N - M)] = true;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
scanf("%d", &matrix[i][j]);
}
}
for(int j = 1; j <= M; j++) {
for(int i = 1; i <= N; i++) {
int tmp = matrix[i][j];
if(player[i] == true) continue;
if(num[tmp] == true) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
bool flag = false;
if(diff[tmp] == true)
flag = true;
if(!flag) {
printf("Round #%d: %d is out.\n", j, i);
player[i] = true;
} else {
for(auto &i: nums)
diff[abs(i - tmp)] = true;
num[tmp] = true;
nums.push_back(tmp);
}
}
}
}
vector<int> winner;
for(int i = 1; i <= N; i++) {
if(player[i] == false) winner.push_back(i);
}
if(winner.size() == 0)
printf("No winner.\n");
else {
printf("Winner(s):");
for(int &i: winner)
printf(" %d", i);
}
return 0;
}
回过头来再看，按照上面代码的逻辑，在 nums 中根本不可能出现重复元素，所以前面使用 set 白白浪费了自动去重的功能，还浪费了时间。
而且，这个题应该算作一道考察散列的题目，只要能想到散列这个知识点，基本就可以 AC 了。
