讨论/技术交流/分享|第 22 次 CCF CSP 认证战记/
分享|第 22 次 CCF CSP 认证战记

背景

我去年 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,我第一题提交通过。

[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)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

int main() {
	int n, m, L;
	cin >> n >> m >> L;
	int ret[L];
	memset(ret, 0, sizeof(ret));
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < m; ++ j) {
			int x;
			cin >> x;
			ret[x] ++;
		}
	}
	printf("%d", ret[0]);
	for (int i = 1; i < L; ++ i) printf(" %d", ret[i]);
	printf("\n");
	return 0;
}
第二题 邻域均值 (14:30 -- 14:55)

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

#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 多分钟。写完后测了一下样例,随后直接提交通过。

#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 分钟写完了代码。我测完前两个样例之后直接提交,然后就通过了。

#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 分钟,我就提前离场了。

#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 认证还是有那么一点作用的。

67

太强了 膜拜字节大佬!

展开全部 38 讨论