成绩
首先晒一下成绩。 
成绩单 
认证经历
这是第二次参加CCF认证，第一次是在大四的时候，部分考研的同学需要用CCF的成绩作为考研复试机试成绩，找班主任（也是院长）请假去其它学校参加考试。院长一听，就去了解一下CCF认证，觉得还不错，就向那边将我们学校申请为CCF考点，但是一次CCF考试的报名的人数需要达到一定人数才能进行，然后就出现了下面戏剧性的一幕：院长要求XX，XX和XX几个专业的所有大四学生必须参加第16次的CCF考试，并且免报名费，学院出钱。我就这样参加了CCF的考试。第一次参加CCF考试，经验不足。虽然平时有刷天梯赛和蓝桥杯的题目，但是两者的出题思路及考查点不太一样，特别是CCF第3题的题目长度在蓝桥杯和天梯赛基本见不到。并且第16次认证的题目比往年难多了，第2题求中缀表达式的值，这是栈的常见的应用，当时比较执拗，想的是如何用栈将中缀表达式转成后缀表达式，然后再用栈对后缀表达式的值，在这道题上花费了太长时间，到了最后才选择暴力的方法，看了第3题和第4题的题目，选择做了第4题，与进程死锁有关。当时很快有了模拟的思路，写完时间也差不多了，赛后第4题得了80分还不错。但是第1题却破天荒的错了，后来分析错误原因：用了g%的格式控制符。但最后提交只得了一点分，所以，这里需要提醒各位的是，考试建议使用常用的写法，有一些写法不同的编译器不一定能通过。总的来说，第一次认证考试体验感不是很好，题目长（3 4题都很大，并且涉及专业知识看了比较难受）并且题目有些问题，中途组委会通知改的。考试时采用的策略也不够明智，在第2道上花费太长时间，很大一部分时间是想着如何用常规解法去解题，而忽略了快捷的暴力解法。 周日参加的第二次CCF认证考试，题意很好理解。很快把1、2和4题做出来了（大概花了一个半小时），这里大概说一下解题思路。
201912-1报数 题解
题目大意是4个人轮流报数从1开始，遇到7的倍数或含7的数就跳过。题目输入是n表示的4个人总共报的数（不含跳过的数）。 思路很简单：模拟用idx表示当前报数人的编号，num表示当前报的数，i计数（不含路过的数）。如果当前数是7的倍数或含7的数，则idx跳过的数加1，然后i不变。反之，idx跳过的数不变，i+1。
201912-1报数 考试时代码（100分）
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
| #include<bits/stdc++.h>
using namespace std;
bool judge(int num){
if(num % 7 == 0){
return true;
}
int tmp = num;
while(tmp){
if(tmp % 10 == 7){
return true;
}
tmp = tmp / 10;
}
return false;
}
int main(){
int n, cnt[4], num = 0, idx = 0;
memset(cnt, 0, sizeof(cnt));
scanf("%d", &n);
for(int i = 0; i < n;){
++num;
if(judge(num)){
++cnt[idx];
}
else{
++i;
}
idx = (idx + 1) % 4;
}
for(int i = 0; i < 4; ++i){
printf("%d\n", cnt[i]);
}
return 0;
}
|
201912-2回收站选址 题解
题目大意：先给所有垃圾堆的坐标，然后从这些垃圾堆中选出回收站，回收站需满足：首先上下左右必须都是垃圾堆，然后4个对角的垃圾堆的个数表示该回收站的分数。最后需要统计的是得分为0， 1， 2， 3， 4回收站的个数。 思路：首先选用map对所有垃圾堆的坐标进行标记（因为垃圾堆的坐标可能为负值，用int数组不能直接标记，除非用哈希函数映射），并用vector存下所有垃圾堆的坐标。然后遍历vector中按题目给出的要求判断即可。注意这里vector中的元素和map的键都是pair类型。
201912-2回收站选址 考试时的代码（100分）
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
| #include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, bool>myMap;
vector<pair<int, int>>vec;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int dir2[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
int cnt[5];
int main(){
int n, x, y, nx, ny;
scanf("%d", &n);
myMap.clear();
vec.clear();
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; ++i){
scanf("%d%d", &x, &y);
vec.push_back(make_pair(x, y));
myMap[make_pair(x, y)] = true;
}
for(int i= 0; i < n; ++i){
x = vec[i].first;
y = vec[i].second;
bool flag = true;
int num = 0;
for(int i = 0; i < 4; ++i){
nx = x + dir[i][0];
ny = y + dir[i][1];
if(myMap.find(make_pair(nx, ny)) == myMap.end()){
flag = false;
break;
}
}
if(flag){
for(int i = 0; i < 4; ++i){
nx = x + dir2[i][0];
ny = y + dir2[i][1];
if(myMap.find(make_pair(nx, ny)) != myMap.end()){
++num;
}
}
cnt[num]++;
}
}
for(int i = 0; i < 5; ++i){
printf("%d\n", cnt[i]);
}
return 0;
}
|
201912-4区块链 题解
我的理解是：首先根据题意可以建图，然后图中的每个结点都维持了一条链，每个结点初始时，链上都有一个编号为0的初始块。然后有两个操作：查询操作和更新操作。在进行查询操作和更新操作都需要检查在此之前，是否存在其它节点的更新操作的信息传过来，如果有的话，则需要判断传播节点的主链$l_1$与当前节点的主链$l_2$关系，$l_1$的长度大于$l_2$的长度，直接令$l_2$ = $l_1$。如果$len(l_1)=len(l_2)$且$l_1$的最后一个元素的值小于$l_2$的最后一个值，则令$l_2$ = $l_1$。注意，一旦结点维持的主链的信息更新，就需要将其传播给相邻节点（存在传播时长）。我考试的时侯是用一个队列来维持这个传播的更新信息，存储的元素包含节点值，信息到达节点的时刻，主链三个信息。我估计可能是数据太大的时候，队列可能会内存超限。
201912-4区块链 考试时的代码（70分）
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include<bits/stdc++.h>
using namespace std;
struct Node{
int time;
int u;
vector<int>vec;
};
queue<Node>que;
vector<vector<int>>gra(505, vector<int>());
vector<vector<int>>block(505, vector<int>());
void toNum(string s, vector<int>& res){
res.clear();
int num = 0;
for(int i = 0; i < s.size(); ++i){
if(isdigit(s[i])){
num = num * 10 + s[i] - '0';
}
else{
res.push_back(num);
num = 0;
}
}
if(num != 0)
res.push_back(num);
}
int main(){
int n, m, t, k;
int u, v, a, b, c;
string s;
vector<int>res;
while(!que.empty()){
que.pop();
}
gra.clear();
block.clear();
for(int i = 0; i < 505; ++i){
block[i].push_back(0);
}
scanf("%d%d",&n, &m);
for(int i = 0; i < m; ++i){
scanf("%d%d", &u, &v);
gra[u].push_back(v);
gra[v].push_back(u);
}
scanf("%d%d", &t, &k);
getchar();
for(int i = 0; i < k; ++i){
getline(cin, s);
toNum(s, res);
while(!que.empty()){
Node frt = que.front();
if(frt.time <= res[1]){
que.pop();
int u = frt.u, v;
for(int i = 0; i < gra[u].size(); ++i){
v = gra[u][i];
if(block[v].size() < frt.vec.size()){
block[v] = frt.vec;
Node tmp;
tmp.time = frt.time + t;
tmp.u = v;
tmp.vec = block[v];
que.push(tmp);
}
else if(block[v].size() == frt.vec.size()){
if(block[v].back() > frt.vec.back()){
block[v] = frt.vec;
Node tmp;
tmp.time = frt.time + t;
tmp.u = v;
tmp.vec = block[v];
que.push(tmp);
}
}
}
}
else{
break;
}
}
if(res.size() == 3){
block[res[0]].push_back(res[2]);
Node tmp;
tmp.time = res[1] + t;
tmp.u = res[0];
tmp.vec = block[res[0]];
que.push(tmp);
}
else{
int u = res[0];
printf("%d", block[u].size());
for(int i = 0; i < block[u].size(); ++i){
printf(" %d", block[u][i]);
}
printf("\n");
}
}
return 0;
}
|
201912-3化学方程式 题解
题目大意：化学方程式配平，检查两边的元素是否相等。 考试只考虑了60%的测试用例，带括号的一直调试不通（其实也算不上调试，我的调试有问题，只能用printf慢慢输出了）。具体见代码，过60%很容易。
201912-3化学方程式 考试时的代码（60分）
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include<bits/stdc++.h>
using namespace std;
map<string, int>myMap1, myMap2;
void deal(string s, map<string, int>& myMap){
int num = 1, len = s.size();
for(int i = 0; i < s.size(); ++i){
if(isdigit(s[i])){
num = 0;
while(isdigit(s[i])){
num = num * 10 + (s[i] - '0');
++i;
}
--i;
}
else if(isupper(s[i])){
string tmp;
int sum = num;
tmp.push_back(s[i]);
if(i < len - 1 && islower(s[i + 1])){
++i;
tmp.push_back(s[i]);
}
if(i < len - 1 && isdigit(s[i + 1])){
int tmpNum = 0;
++i;
while(i < len && isdigit(s[i])){
tmpNum = tmpNum * 10 + (s[i] - '0');
++i;
}
--i;
sum = sum * tmpNum;
}
if(myMap.find(tmp) != myMap.end()){
myMap[tmp] = myMap[tmp] + sum;
}
else{
myMap[tmp] = sum;
}
}
}
}
void cal(string s, map<string, int>& myMap){
int idx = 0, tmp;
string str;
while((tmp = s.find('+', idx)) != -1){
str = s.substr(idx, tmp - idx);
deal(str, myMap);
idx = tmp + 1;
}
str = s.substr(idx);
deal(str, myMap);
}
int main(){
int n;
string s;
scanf("%d", &n);
getchar();
for(int i = 0; i < n; ++i){
getline(cin, s);
int idx = s.find('=');
string str1 = s.substr(0, idx);
string str2 = s.substr(idx+1);
myMap1.clear();
myMap2.clear();
cal(str1, myMap1);
cal(str2, myMap2);
if(myMap1.size() != myMap2.size()){
printf("N\n");
}
else{
bool flag = true;
for(auto iter1 = myMap1.begin(), iter2 = myMap2.begin(); iter1 != myMap1.end() && iter2 != myMap2.end(); ++iter1, ++iter2){
if(iter1->first != iter2->first iter1->second != iter2->second){
flag = false;
break;
}
}
if(flag){
printf("Y\n");
}
else{
printf("N\n");
}
}
}
return 0;
}
|
这次在第3题仍然采用不太明智的策略，则开始就考虑了多重括号嵌套的情况，然后代码写了很长时间，真的很长时间，因为一直没有理清思路。后来写完了，运行一直有问题，排错很长时间无效，最后又只能放弃后40%的测试用例，专心调试前60%的用例，很快就通过。所以，在这里需要注意的是，对于用例层层递进的情形，代码如果一时不能处理所有情况，也可以逐渐完善，先保证通过最简单的测试用例，再考虑其它情况。
反思
可能是最后一次CCF，成绩离预期还是有点小差距，毕竟写题解的过程发现题目并不是很难，所以存在的问题还是要反省。 前一个半小时做完1，2，4题，后两个半小时做第3道题只得60分，对于时间利用率不高。做完1，2，4题大脑开始有点反应不过来（身体还是有点虚啊），第3题对于括号嵌套的情形迟迟没想清楚，导致代码Bug横生，如果及时调整思绪，从简单的情形做起，逐渐增加难度，完善代码，通过一重括号的测试用例应该没有问题。这里可以+20。第5题是大数模拟，听说水个20分没问题。用c++写个大数运算更应该没问题，只是麻烦，这里可以+20。最佳可达370+。 DEV的调试无法使用属于特殊情况，不应归咎。但个人的心态的调整，做题策略的更换，做题时间的分配却应该以时间，地点，条件为转移（巧妙将马克思原理应用于实践）。流水不腐，户枢不蠹。
经验分享
针对C++： 1. 头文件用万能头文件避免include一堆其它头文件，带来记忆负担。代码如下：
1
2
| #include<bits/stdc++>
using namespace std;
|
- 从文本读入数据，对于3， 4， 5题，题目的输入往往很长，而它的题目往往又是图片，不能用CV大法。这时，就能充分发挥文件读入的优势了。使用方法，在main函数的第一行加入以下代码
freopen("D://a.txt", "r", stdin)然后将数据粘贴进入D盘下的a.txt，这个路径可以自定义，然后运行的时候，直接从文件输入，输出仍在控制台。 注意：提交的时候freopen("D://a.txt", "r", stdin)一行一定要注释掉，一定要注释掉，一定要注释掉，重要的事情说三遍，不然提交会是0分。 我常用的模板文件代码为：
1
2
3
4
5
6
7
| #include<bits/stdc++>
using namespace std;
int main(){
return 0;
}
|
- 常用的stl的数据结构及函数一定要牢记，考试的时候能事半功倍。比如：数据结构：
map（这次的2 3 题都有用到），set，pair，stack，queue（其中优先队列蛮香的），string， vector等。函数如sort(排序)，binary_search(二分查找)，cctype的字符判断函数isdigit（是否为数字），isupper（是否为大写字母），islower（是否为小写字母）等，stoi（string转int），atoi（字符串转int），sprintf等。
- c++11是真香的，里面有正则表达式，它能让字符串的处理更加简单。有
unordered_map，unordered_set能有效解决查询超时的问题。
- 掌握常见的算法：
DFS，BFS，Prim，Dijstra，并查集等，虽然最近几次考的第4题模拟都能做的，不会涉及算法。
针对CCF考试： 1. 做题策略：我一般是1 2 4 3的顺序，如果第3题的题意比较容易理解，容易模拟，可以先做。第5题可以过前面简单规模，简单逻辑的用例。 2. 考试的时候无任何反馈，类似于蓝桥杯，与pat的在线评测不同，所以对于1，2题需仔细设计测试用例，保证得满分。 3. 注意输入输出的格式， 这个有时候很致命，201903-2的中缀表达式的那一题，当时我一个同学就把乘号当成常见的*，实际是x（小写的x），结果可想而知。对于输出YES和NO的，稍有不慎，会看成Yes和No。 这种情况理应避免。 4. 平常多练，注重首次通过率。 我要分享就这么多，这次200+，满足毕业答辨的要求了，2019太过平淡无奇，也算完成了一个小目标。，明天继续一天一道 LeetCode打卡任务，暂时告别CCF。