分享｜第 22 次 CCF CSP 认证战记

17959

2021.04.20

发布于未知归属地

背景

我去年 11 月 1 日接触 Leetcode，刷了大概 1000 题，周赛也取得过 54 名的成绩。然而，大概是因为从未背过八股文的缘故，我去字节面试，连一面都没有过。怎么办？现在去背八股文显然来不及。于是，我把希望寄托在今年 4 月 11 日的 CCF CSP 认证上，希望取得一个高分来证明自己的能力。
我一面挂了之后，我的简历又被捞起来。我想：这次不能随随便便去面试，得手里有东西才行。所以，我把字节面试的时间定在了 CSP 认证之后，想着：我拿着 CSP 认证的高分去面试，总不可能一面就挂掉吧。

准备

Leetcode 刷题 1000+
做了一下上一次 CCF CSP 认证的题目第 21 次CCF CSP 题解
花了一下午时间做了一次 CSP 模拟考试（做的第 19 次认证的题目，得分是 100+100+90+64+40=394）

过程

4 月 11 日下午 1:00，我来到上海大学参加认证。机器用的是 Windows 系统，这对平常用惯了 Linux 和 Mac 的我非常不利，好在 Dev-CPP 和 python3 还能正常使用。

第一题灰度直方图 (13:30 -- 14:30)

下午 1:30 认证开始，第一题灰度直方图是一道水题，看完题目，我就想用 python3 快速的解决它。我当时直接在提交框里写 python3 的代码，然后直接点提交按钮。由于太过于着急，我 python3 程序写错了，这次提交我一分未得。更倒霉的是，我发现那个提交系统竟然不能看自己提交过的代码。我只能重新创建一个 python3 的源程序文件，然后重新把 python3 的代码再写一遍。测过样例之后，我再提交，仍然是零分。我检查了 20 分钟，竟然查不出任何问题（事后才知道是我的输出格式有问题）。此时，我看了一下时间，是下午 2:05。前 35 分钟，我一分未得。
这时候，我告诉自己，一定要冷静下来。我坐在座位上，闭上眼睛，不断的深呼吸。过了 10 分钟左右，我的心态终于稳住了。我想：python3 一定不能再使用了。于是，我决定用 c++。我先花 5 分钟时间熟悉了 Dev-CPP 软件，学会了如何用这个软件把一个 CPP 源程序编译成一个可执行文件。下午 2:20，我开始用 c++ 做第一题。下午 2:30，我第一题提交通过。

Python3

c++

[n,m,h] = [int(_) for _ in input().split()]
ret = [0]*h
for i in range(n) :
    buf = [int(_) for _ in input().split()]
    for x in buf :
        ret[x] += 1
for i,v in enumerate(ret) :
    ed = ' ' if i<h-1 else '\n'
    print(str(v), end=ed)

第二题邻域均值 (14:30 -- 14:55)

做完第一题后，我开始读第二题。我读完题之后，发现这个问题可以用二维前缀和来解决。我花了大概 15 分钟写完了代码。下午 2:55，我第二题提交通过。

c++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

int main() {
	int n, L, r, t;
	scanf("%d%d%d%d", &n, &L, &r, &t);
	int A[n+1][n+1];
	int S[n+1][n+1];
	memset(S, 0, sizeof(S));
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			scanf("%d", &A[i][j]);
			S[i][j] = A[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			int up = max(i-r, 1);
			int down = min(i+r, n);
			int left = max(j-r, 1);
			int right = min(j+r, n);
			int area = (down-up+1)*(right-left+1);
			int sum = S[down][right] - S[down][left-1] - S[up-1][right] + S[up-1][left-1];
			if (area*t >= sum) ans ++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

第三题 DHCP服务器 (14:55 -- 16:10)

众所周知，每次 CSP 认证的第三题都是一道非常繁琐的模拟题。为了做对第三题，我在参加这次认证之前特意做了之前三次 CSP 认证的第三题（带配额的文件系统、点亮数字人生、Markdown渲染器）。我发现，只要耐心的在草稿纸上做好记录（记一下每个变量代表什么东西），就能大幅度降低打错变量名的概率，减少调试时间，从而快速的拿到这题的满分。
这次，我花了 45 分钟读这道题，并在草稿纸上做了记录（记了整整 2 张草稿纸）。然后，对着草稿纸写代码，大概写了 20 多分钟。写完后测了一下样例，随后直接提交通过。

c++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>

using namespace std;

int N, Tdef, Tmax, Tmin;
int n;
int t;
string sendH, receiveH, Mtype;
int IPadr, endT;
string H;
int state[16384];
int endTime[16384];
string occupier[16384];
int setT;

int check(string& x) {
	for (int i = 1; i <= N; ++ i) {
		if (state[i]!=0 && occupier[i]==x) return i;
	}
	return -1;
}

int getZero() {
	for (int i = 1; i <= N; ++ i) {
		if (state[i]==0) return i;
	}
	return -1;
}

int getThree() {
	for (int i = 1; i <= N; ++ i) {
		if (state[i]==3) return i;
	}
	return -1;
}

void clearName(string& x) {
	for (int i = 1; i <= N; ++ i) {
		if (state[i]==1 && occupier[i]==x) {
			state[i] = 0;
			occupier[i] = "";
			endTime[i] = 0;
		}
	}
}

void flushTime(int t) {
	for (int i = 1; i <= N; ++ i) {
		if (state[i] == 1 || state[i] == 2) {
			if (endTime[i]<=t) {
				if (state[i] == 1) {
					state[i] = 0;
					occupier[i] = "";
					endTime[i] = 0;
				} else {
					state[i] = 3;
					endTime[i] = 0;
				}
			}
		}
	}
}

int main() {
	cin >> N >> Tdef >> Tmax >> Tmin >> H;
	for (int i = 1; i <= N; ++ i) occupier[i] = "";
	memset(state, 0, sizeof(state));
	cin >> n;
	for (int rep = 0; rep < n; ++ rep) {
		cin >> t >> sendH >> receiveH >> Mtype >> IPadr >> endT;
		flushTime(t);
		if (receiveH != H && receiveH != "*" && Mtype != "REQ") continue;
		if (Mtype != "DIS" && Mtype != "REQ") continue;
		if (receiveH == "*" && Mtype != "DIS") continue;
		if (receiveH == H && Mtype == "DIS") continue;
		if (Mtype == "DIS") {
			int selec = check(sendH);
			if (selec == -1) selec = getZero();
			if (selec == -1) selec = getThree();
			if (selec == -1) continue;
			state[selec] = 1;
			occupier[selec] = sendH;
			setT = t + Tdef;
			if (endT != 0) {
				setT = endT;
				if (setT < t + Tmin) setT = t + Tmin;
				if (setT > t + Tmax) setT = t + Tmax;
			}
			endTime[selec] = setT;
			cout << H << " " << sendH << " OFR " << selec << " " << setT << endl;
		} else {
			if (receiveH != H) {
				clearName(sendH);
				continue;
			}
			if (!(1 <= IPadr && IPadr <= N && occupier[IPadr]==sendH)) {
				cout << H << " " << sendH << " NAK " << IPadr << " " << 0 << endl;
				continue;
			}
			state[IPadr] = 2;
			setT = t + Tdef;
			if (endT != 0) {
				setT = endT;
				if (setT < t + Tmin) setT = t + Tmin;
				if (setT > t + Tmax) setT = t + Tmax;
			}
			endTime[IPadr] = setT;
			cout << H << " " << sendH << " ACK " << IPadr << " " << setT << endl;
		}
	}
	return 0;
}

第四题校门外的树 (16:10 -- 16:55)

下午 4:10，我开始看第四题。花 10 分钟看完题目之后，我瞬间想到了一个能拿 60 分的 DP 算法，我花了 10 分钟时间写完了代码，提交之后拿了 60 分。我本想拿了 360 就离场，但我看了一下时间还剩 1 小时，我想：要不再做一会儿？
然后我开始想这题的满分算法。我想了 10 分钟，终于想出来了，然后花了大概 20 分钟写完了代码。我测完前两个样例之后直接提交，然后就通过了。

c++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<set>
#define MOD 1000000007

using namespace std;

vector<int> ans[100001];
int n;
int N;
int F[1024][1024];
int G[1024];
int a[1024];

void init() {
	for (int i = 2; i <= N; ++ i) {
		ans[i].push_back(1);
		for (int j = 2; j*j <= i; ++ j) {
			if (i%j==0) {
				ans[i].push_back(j);
				if (j != i/j) ans[i].push_back(i/j);
			}
		}
	}
}

int cheng(int x, int y) {
	return (int)((long long)x * (long long)y % (long long)MOD);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++ i) cin >> a[i];
	for (int i = 1; i < n; ++ i) a[i] -= a[0];
	a[0] = 0;
	N = a[n-1];
	init();
	for (int i = 0; i < n; ++ i) {
		set<int> temps;
		for (int j = i+1; j < n; ++ j) {
			int len = a[j]-a[i];
			for (int k = 0; k < ans[len].size(); ++ k) {
				int x = ans[len][k];
				if (temps.count(x)) continue;
				F[i][j] ++;
				temps.insert(x);
			}
			temps.insert(len);
		}
	}
	
	/*for (int i = 0; i < n; ++ i) {
			for (int j = 0; j < n; ++ j) {
				cout << F[i][j] << " ";
		}
		cout << endl;
	}*/
	
	G[1] = F[0][1];
	for (int i = 2; i < n; ++ i) {
		G[i] = F[0][i];
		for (int j = 1; j < i; ++ j) {
			G[i] = (G[i] + cheng(G[j], F[j][i])) % MOD;
		}
	}
	
	cout << G[n-1] << endl;
	return 0;
}

第五题疫苗运输 (16:55 -- 17:21)

最后一题我读完题目已经是下午 5:05 了，我写了一个简单的记忆化搜索，拿了 80 分。写完后，还剩下 9 分钟，我就提前离场了。

c++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

int n, m;
int nxt[30][1000001];
bool v[31][1000001];
int dist[32];
int l;
int zd[32];
int sj[32];

void dfs(int cnt, int t) {
	if (t > 1000000) return;
	if (v[cnt][t]) return;
	v[cnt][t] = true;
	if (dist[cnt] > t) dist[cnt] = t;
	for (int i = 0; i < m; ++ i) {
		if (nxt[i][t]/1000000 == cnt) {
			int y = nxt[i][t] % 1000000;
			//cout << y << endl;
			dfs(y / 10000, t + (y%10000));
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) dist[i] = 1047483644;
	dist[1] = 0;
	for (int i = 0; i < m; ++ i) {
		cin >> l;
		for (int j = 0; j < l; ++ j) cin >> zd[j] >> sj[j];
		int t = 0, x = 0;
		while (t <= 1000000) {
			nxt[i][t] = zd[x] * 1000000 + zd[(x+1)%l] * 10000 + sj[x];
			t = t + sj[x];
			x = (x+1) % l;
		}
	}
	for (int i = 0; i <=1000000; ++ i) dfs(1, i);
	for (int i = 2; i <= n; ++ i) {
		if (dist[i]==1047483644) {
			cout << "inf" << endl;
		} else {
			cout << dist[i] << endl;
		}
	}
	return 0;
}

结果

截屏2021-04-20 下午9.10.32.png

总结

这是我第一次参加 CSP 认证，由于经验不足，犯了很多低级的失误。尤其是在做第一题的时候，由于心态过于着急，想着用 python3 快速的拿到这题的满分，反而在写 python3 代码的过程中犯了低级失误，浪费了大概 45 分钟时间。
总而言之，这次比赛发挥的不是很好，还有很多能够改进的地方。

后记

今天晚上，我刚结束了字节的三面，面试官说我应该能够拿到一个实习 offer。看来，CSP 认证还是有那么一点作用的。

背景

准备

过程

第一题 灰度直方图 (13:30 -- 14:30)

第二题 邻域均值 (14:30 -- 14:55)

第三题 DHCP服务器 (14:55 -- 16:10)

第四题 校门外的树 (16:10 -- 16:55)

第五题 疫苗运输 (16:55 -- 17:21)

结果

总结

后记

第一题灰度直方图 (13:30 -- 14:30)

第二题邻域均值 (14:30 -- 14:55)

第四题校门外的树 (16:10 -- 16:55)

第五题疫苗运输 (16:55 -- 17:21)