OI 2021 退役记
Published:
引言
这篇游寄从 12 月 4 日（其实也不算早了（雾））就开始写（shui）了，但因为准备会考艺术节等等各种各样的原因，一直咕到今天才完成。
坐标江苏，今年高二。不出意外，这应该是我OI生涯的最后一年。
初赛日
考前“预习”了主定理（学了四年多连主定理都不知道的我是屑）和计算机常识（为什么信息学史也算是“常识”啊）。
疫情原因，今年考点与往年不同，但监考老师却全是熟悉的面孔（）。
好耶，第一题是新鲜的Linux题！
好耶，前四题都是送分题！
好家伙，第五题不是历史悠久的历年原题（要求 \(2n\) 个数组成数列的最大值最小值，最坏情况下需要比较多少次）吗，原谅我只会暴力求解，错了 2 分。
然后甚至错了智障的第七题（无向图至少有多少个点），第十二题（递归求斐波那契数列的时间复杂度）。数学不好组合计数题直接废掉（）。
阅读程序第一题，说实话看着挺蒙，我甚至都不知道 acos(0.5)=pi/3，准确地说，我连 acos 是什么都不知道（但我知道 \(\arccos\) 是什么东西）……连猜带蒙，竟然做对了每一题（尽管我知道它是水题，但终究还是吃了数学不好的亏）。
之后的两段阅读程序，可以说直接开摆，几乎属于是完全看不懂。对于第二段程序，赛后看到巨佬发言说是“《LIS 的两种经 典 求 法》”，身为只会二分和 DP 的小蒟蒻只能瑟瑟发抖（）。第三段程序倒是看懂了，但并没有想到阴间的 CCF 会给一段错误的解码程序……
完善程序 T1 直接水过去了，但也花了挺久，比往年的 T1 阴间了不少（）。T2，我只能说，四毛子，笛卡尔树，Euler 序列我是一个没听说过，只能完全靠蒙（）。
最后得分：\(68.5\)
CSP-S 2021
SCP 之前三周内做了几套牛客的模拟赛，提前感受到了被完虐的感受（）。
考试前两天学校开运动会，这种活动当然得直接翘掉了啊（），复习了 Tarjan、快速幂等几个很水的模板。
10 月 20 日晚上教练开了线上会议，JS 终于有了船新的提交系统！检查数组越界好耶！不用自己建文件夹好耶！Windows 下的 VSCode 好耶！
10 月 23 日上午到达南京，吃完午饭看到 J 组的试题，看到 J 组的题那么水，就预言 S 组会很毒瘤（）。
到达南京航空航天大学，试机，立刻找到了 VSCode 并试图调教它。我想先写一个编译 bat 脚本，但似乎机房的 PowerShell 版本和我平时用到的似乎不太一样，所以导致我都不会在脚本中读入。但那个 VSCode 似乎支持自动查错（就挺好），所以我在那一场比赛中就选择了使用 VSCode 写代码，然后手动输入指令编译……
发题。开 O2 好耶！（）
4小时以后，面对收代码的监考老师，AnicoderAndy将会回想起只做了一道题甚至还没做出来的那个遥远的下午。
——《四小时孤独》
看到这样的 T1，立刻能反应出这是一道思维题，然而也就只能反应出这是一道思维题（，在草稿纸上画出来几条线段大概知道贪心策略是要尽可能使每架飞机到达靠前的廊桥。于是立刻想到要用优先队列维护，每次取出当前结束时间最早的廊桥，如果它可以接纳当前到达的飞机则更新它的结束时间，否则新开辟一个廊桥。然而很快样例 3 就打了我的脸，但当时并没有发现问题所在，于是看 T2 。
T2 题面很好懂，但就是看不出来是什么算法，（当时的我甚至不知道计数题可以朝DP的方向去想。开始着手写暴力，但写着写着又意识到问题不对劲了起来——对于本题，因为对于“超级括号序列”的定义过于复杂，暴力的 check 函数可以说是相当不好写，所以直接放弃了（）。于是赶忙看 T3，立刻能反应出这是一道思维题，然而也就只能反应出这是一道思维题（梅开二度），在草稿纸上推了半天也没有得到什么有用的规律，在急急忙忙之中感觉为了稳得赶快回去再看看 T1。
对于原来错误的做法，显然并非只有结束时间最早的廊桥有可能接纳当前到达的飞机，还有次小、次次小的等等都可以尝试，于是我就走上了负优化的不归途，不断取出最早的廊桥，看是否能接纳当前飞机。至于那些不符合要求的廊桥……我选择了建立一个栈临时将它们存储起来，在整个过程之后把它们一个一个地塞回原序列……调试的时候依旧出了问题，所以就写了一个纯暴力的程序做对照，最后把这个奇奇怪怪的做法调出来了，并且过了那个水得不行的大样例。我不会算它的复杂度，所以姑且认作 \(O(玄学)\)。
for (int i = 1; i <= m1; i++) {
if (!u1) u1 = 1, l1[1] = in[i].b, s1[1] = 1, pq1.push(make_pair(-in[i].b, 1));
else {
pair<int, int> xx; xx.first = -1, xx.second = 0x7f7f7f7f;
while (pq1.size()) {
if (-pq1.top().first > in[i].a) break;
if (xx.second > pq1.top().second) xx = pq1.top();
stk[++top] = pq1.top(); pq1.pop();
}
while (top) {
if (top == 0) break;
if (stk[top] != xx) pq1.push(stk[top]);
top--;
}
// cout << -pq1.top().first << ' ' << pq1.top().second << ' ' << in[i].a << endl;
if (xx.first == -1) {
l1[++u1] = in[i].b; s1[u1] = 1, pq1.push(make_pair(-in[i].b, u1));
} else {
int pos = xx.second;
l1[pos] = in[i].b, s1[pos]++, pq1.push(make_pair(-in[i].b, pos));
}
}
}
}
而至于其他几题，我就直接摆烂了，T2 输出 \(0\)，T3 直接输出了 \(T\) 个 \(-1\)，T4 甚至连题目都没读懂，直接输出了 \(0\)。
CSP-S 出分日
各家平台 T1 测出来都是 40 分，但仁慈的CCF给我的做法以 \(55\) 分的好成绩。正当我以为我这次能以 40 分总分滚粗的时候，仁慈的CCF竟然给输出 \(T\) 个 \(-1\) 的程序 \(16\) 分的好成绩。所以总分由民间测试的 40 分变为了 \(71\) 分，获得了人生中第二个 CSP-S 的二等（）。
备战NOIP
这次赛前我们学校一直在跟着常州一中做模拟赛，同样且不出所料地，我一直在我们学校处于接近垫底的水平。不得不说常州一中的题目质量还挺高，至少钱没有白花。
期中考试一直考到 11 月 17 日上午 9:00，考完后立刻进入了完全备赛状态。因为发现我的记性确实很差，好多算法都只是记得自己曾经学过，于是采用了一种奇怪的复习策略：在洛谷上先把模板切了，再在纸上把代码框架默写下来。而 11 月 17 日也成为了近期单日 AC 数最多的一天（15 题）（）。至于那两天做的题，除了模板题以外，似乎还做了一点字符串的题目，以防像去年那样出现字符串完全没思路的情况（）。
11 月 19 日上午，基本上没做什么题（准确地说，应该是那一天一题都没做）。同学找到了一个非常好玩的 io游戏，于是整个机房几乎所有人都颓了起来（）。午饭后，稍作整理，顺好了书包，带齐了准考证身份证，在机房随便拔下了一副有线耳机（上车后才发现光拿了耳机没有拿线），在学校门口的便利店买了两根士力架、一个肉松面包、一瓶咖啡，便跟着同学一起上了大巴车。到达南京酒店，和 cn 巨佬住在一间。关上房门，房间里的气氛就蕉灼了起来（大雾）；我们聊天的话题似乎全是些八卦的东西（此处不宜展开）（雾）。吃完晚饭后，我躺在床上翻了翻几天前默写的代码框架，中途试图出去买耳机但便利店并不卖。为了保证自己能有充足的精神（雾），我在 21:40 就关了灯（舍友同学去别的房间打音游了）。但已经习惯了每天凌晨上床的我显然不会那么容易就睡着。在床上翻来覆去，思绪万千，有次日就要奔赴考场的紧张，亦有次日就要退役的怅惘，还有与我”并肩作战“的队友们也一一在我脑海中闪过。直到 23:00 我的舍友回来，我还没有睡着。睡着后的中途还醒了一次，那一刻我依旧认为我自己竟然还没有睡着（）。那个早晨，也是难得的没有被闹钟叫醒的一个早晨，5:44 分我便已睁开双眼思考人生（大雾）。总而言之，那晚我睡得很糟糕（）。
OI生涯的最后一役
起床后经过简单的洗漱，我和舍友一同前往餐厅。毕竟是退役赛前的最后一次早餐，我试图对那次的饮食非常重视。但我不记得班主任曾安利过的《考试脑科学》中说早饭应该吃什么了，只记得要吃一些消化快的，于是便吃了两片面包一杯牛奶跑路。出发前我也保持迷信，循环播放着音乐老师曾经安利过的《D大调双钢琴奏鸣曲 K.448》——据说是能短效地提升智商（大雾）。我们的教练也属于是不紧不慢，带着我们向金陵中学河西分校走去，荣幸地成为了全场最后一个到达的校队（）。
吸取了上次的教训，这次比赛我还是决定老老实实地用 Dev-C++。试机时，打开了 C++14 和 O2，打了半个树状数组、半个线段树（都是打了一半觉得肯定用不上，怎么会是忘了呢doge），以及一个Tarjan（显然也用不上）。
考试正式开始，T1 没怎么想就觉得应该是个筛子。用埃氏筛预处理，二分找下一个，简单实现之后就过了所有样例。但最后一个点在本地足足花了将近980ms，虽然有点危，但我愿意相信CCF的机器能过（毕竟大样例并不水）。提交到 JSOI Linux，长舒一口气。但没过多久，\(\color{red}运行错误\)四个大字便使我顿感阴间。起初我还以为是虚拟机空间不够，正当我准备放下 T1 去看 T2 时我才发现：数组访问越界了。属实是，JSOI Linux 救我一命！我不再敢冒然往下做，便仔细检查起了 T1 的代码，也考虑到 1e7 的下一位的问题，但我的代码本身就预处理到了 1e7+9，所以之后并没有发现任何问题（）。
const int X = 1e7 + 10, N = 8e5;
bool nop[X];
int li[N], cnt = 0;
bool c7(int val) {
while (val) {
if (val % 10 == 7) return true;
val /= 10;
}
return false;
}
int main() {
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
// cout << (double)(X / 1024.0 / 1024.0) << endl;
for (int i = 1; i < X; i++) {
if (nop[i]) continue;
if (c7(i)) {
nop[i] = 1;
for (ll j = 2; 1ll * i * j <= X; j++) {
nop[i * j] = 1;
}
} else {
li[++cnt] = i;
}
}
// cout << X - 9 << ' ' << nop[X - 9] << endl;return 0;
int T = read();
while (T--) {
int x = read();
if (nop[x]) printf("-1\n");
else {
int pos = lower_bound(li + 1, li + 1 + cnt, x) - li;
printf("%d\n", li[pos + 1]);
}
}
return 0;
}
接下来就是按部就班的读题，发现 T2 果然又双叒叕是道 DP。先在纸上划了半天，最后得到的似乎还是很显然的结论，然后就考虑状压，但竟然连状压应该怎么做都没想出来（）。\(k=1\) 的情况也挺复杂，所以经过若干思考，最终决定：大暴力（）。
一开始写的暴力似乎效率极低，即 DFS 枚举每一个可能的 \({a_i}\)，然后判断其是否是合法序列，时间复杂度 \(O(m^n)\)。这个算法只能过掉样例1（\(n=5,m=1\)），然而第一组测试数据就达到了 \(n=8,m=9\)，经过测试，我的程序跑最小的点也得花四五秒钟。当时骂 CCF 的想法立即迸发了出来：寄！CCF 汝母打暴力都没分吗！于是就想到优化这个暴力程序：序列 \({1,1,2}\) 和 \({2,1,1}\) 可以只算一次，只需 DFS 枚举出所有不降序列，检验其是否是合法序列，乘以对应的排列个数即可。设 cnt[j] 表示 \(j\) 在序列中出现的次数，考虑每次合并两个序列，简单计算（所谓简单计算，对我这种数学菜鸡来说依旧是个大工程（雾））得到这个个数为
看到这个式子，想必各位读者已经血压高了起来，关于这个式子的优化在后文会提到（）。
不考虑组合数的计算，时间复杂度 \(O(不会算)\)。事后我校巨佬算到复杂度为 \(O(C_{n+m-1}^n)\)。
代码片段（省略了部分函数的实现和语句，注释都是事后添加的）：
void dfs(int now) {
for (int i = a[now - 1]; i <= m; i++) {
a[now] = i;
if (now < n) dfs(now + 1);
else if (cnt1()) { //cnt1()函数线性时间内判断当前枚举的序列是否是合法序列
memset(cnt, 0, sizeof(int) * (m + 1));
for (int j = 1; j <= n; j++) {
cnt[a[j]]++;
}
//cc表示上面提到的组合数之积，tmp表示序列的权值，comb(n,m)是组合数函数
ll tmp = 1, cc = 1, dd = 0;
for (int j = 0; j <= m; j++) {
cc = cc * comb((dd + cnt[j]) % MOD, dd);
dd = (dd + cnt[j]) % MOD;
tmp = tmp * qpow(v[j], cnt[j]) % MOD;
}
ans = (ans + tmp * cc % MOD) % MOD;
}
}
}
int main() {
//（输入输出、return 0均已省略）
f[0] = 1;
for (int i = 1; i < M; i++) f[i] = f[i - 1] * i % MOD;
//如下是赛前学到的线性求阶乘数逆元的方法，inv[i]表示i!的逆元，qpow(a,b)是快速幂函数
inv[M - 1] = qpow(f[M - 1], MOD - 2);
for (int i = M - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % MOD;
}
dfs(1);
}
看了两眼 T3，又看了两眼 T4，不想做数学题的本能让我直接开始搞起了 T4 的暴力。
首先考虑存矩阵的方式，因为觉得每次考虑四个方向太麻烦，所以最后建了一张图。接着就直接考虑纯暴力的方法，对于每次询问，跑 DFS，看能到达的点有多少个。因为细节太多，我的做法是跑两遍 DFS，第一次找出 \(opt_i=1或2\) 的情况（这两种情况本质上都只能往一个方向跑，所以可以合起来考虑），第二次找出 \(opt_i=3\) 的情况。这个代码就毫无含金量可言，完全属于是大暴力解决问题。调了好长时间，终于过了小样例。至于大样例，跑了个四五秒答案没出来就直接 kill 了（）。
又臭又长的代码（省略快读板子和头文件）：
const int N = 2e5 + 10, Q = 1e5 + 10;
int n, m, q, ver[N << 4], nxt[N << 4], head[N], cnt = 0, lv[N], cv = 0, ans = 0;
bool col[N], vis[N], vis2[N], u[N];
short opt[N << 4];
char s[N];
int cal(int x, int y) {
return (x - 1) * m + y;
}
void add(int x, int y, short z) {
ver[++cnt] = y, nxt[cnt] = head[x], opt[cnt] = z, head[x] = cnt;
}
void dfs(int now, int ini, int tmp) {
// cout << ini << ' ' << now << ' ' << tmp << endl;
vis[now] = 1, ans++;
if (u[now] && now != ini) return;
for (int i = head[now]; i; i = nxt[i]) {
int to = ver[i];
if (vis[to] || (u[to] && (col[to] == col[ini] || lv[to] > lv[ini]))) continue;
// cout << "//" << to << endl;
if (opt[i] == 1 && tmp == 0) dfs(to, ini, 1);
if (opt[i] == 2) {
if (tmp == 0) {
if (to == now + 1) dfs(to, ini, 2);
else if (to == now - 1) dfs(to, ini, 3);
else if (to < now) dfs(to, ini, 4);
else if (to > now) dfs(to, ini, 5);
} else if (tmp == 2 && to == now + 1) dfs(to, ini, 2);
else if (tmp == 3 && to == now - 1) dfs(to, ini, 3);
else if (tmp == 4 && to < now && to != now - 1) dfs(to, ini, 4);
else if (tmp == 5 && to > now && to != now + 1) dfs(to, ini, 5);
}
}
}
void dfs2(int now, int ini) {
// cout << ini << ' ' << now << endl;
if (!vis[now]) ans++;
vis2[now] = vis[now] = 1;
if (u[now] && now != ini) return;
for (int i = head[now]; i; i = nxt[i]) {
int to = ver[i];
// cout << "/" << now << ' ' << to << ' ' << vis2[to] << endl;
if (vis2[to] || (u[to] && (col[to] == col[ini] || lv[to] > lv[ini]))) continue;
if (opt[i] != 3) continue;
dfs2(ver[i], ini);
}
}
int main() {
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
int T = read();
while (T--) {
memset(ver, 0, sizeof ver);
memset(nxt, 0, sizeof nxt);
memset(head, 0, sizeof head);
memset(lv, 0, sizeof lv);
memset(col, 0, sizeof col);
memset(u, 0, sizeof u);
memset(opt, 0, sizeof opt);
cnt = 0;
n = read(), m = read(), q = read();
// cout << n << ' ' << m << ' ' << q << endl;
cv = cal(n, m);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= m - 1; j++) {
int now = cal(i, j), to = cal(i, j + 1);
if (s[j] == '0') continue;
else add(now, to, s[j] - '0'), add(to, now, s[j] - '0');
}
}
for (int i = 1; i <= n - 1; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j++) {
int now = cal(i, j), to = cal(i + 1, j);
if (s[j] == '0') continue;
else add(now, to, s[j] - '0'), add(to, now, s[j] - '0');
}
}
while (q--) {
// cout << q << endl;
int s1 = read(), s2 = read(), s3 = read(), s4 = read();
int now = cal(s3, s4); col[now] = s1, lv[now] = s2;
u[now] = 1;
memset(vis, 0, sizeof(bool) * (cv + 1)); ans = 0; memset(vis2, 0, sizeof(bool) * (cv + 1));
dfs(now, now, 0);
dfs2(now, now);
printf("%d\n", ans - 1);
}
// for (int i = head[8];i;i = nxt[i]) cout << ver[i] << ' '; cout << endl;
}
return 0;
}
距离考试结束还有 45 分钟，我没多想就直接开始搞起了 T3 的暴力，但根本想不到这题的暴力思路，随便写了一个 DFS，但又出现了灵异事件——一进入 DFS 变量 \(n\) 的值就会变成 0（，来不及思考，于是直接摆烂，输出了数列的原方差。。。
int main() {
freopen("variance.in", "r", stdin);
freopen("variance.out", "w", stdout);
int n = read(); cnt = 1;
for (int i = 1; i <= n; i++) {
a[i] = read();
}
ll sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
}
double ave = (double)(sum) / (double)(n);
double fc = 0;
for (int i = 1; i <= n; i++) {
fc += (ave - a[i]) * (ave - a[i]);
}
printf("%lld\n", (ll)(fc * n));
return 0;
}
摆完 T3 的烂还剩十几分钟，再次检查了每一题的文件输入输出、提交的文件版本等等。然后又仔细翻了翻每一题的 Subtask 有多少分。
终于，伴随着 13:00 监考的一声令下，我的OI生涯就此结束了。
站在电脑前，脑中回忆着刚刚所做的题，心中满是怅惘。根据之前的测试，T2 可能只能拿到前 4 个点，也就是 \(20\) 分，而 T4 撑死了也就只能拿下前六个点，也就是 \(24\) 分（也许第 \(3\sim6\) 个点都拿不下）。而那个跑了 0.9s 的 T1，哪怕就是运气爆棚，真的能在最后卡进 1s，加起来也不过 \(144\) 分，还不到去年江苏的一等线，而今年的试题又显然比去年的简单……也许，又忙活了一年，最终也不过只能得到这样的结果吧……
在考场楼前，留下了退役后的第一张照片（）。同是高二的同学一同高喊着“退役快乐”，而我站在其中，只是和他们一起笑着，一言不发。
最终成绩&赛后总结
民间数据做好之后，我才知道我的 T2 做法能还能过第 \(6\sim7\) 个点，也就是能拿到 \(30\) 分（）。在跑的过程中我也发现在评测平台上我程序的效率比考试机的效率要高得多，T1 三百毫秒以内便能求出结果。可能我考场上 O2 没开好？可能考试机的配置真的太渣了？不管怎么说，这对我而言必然是一个好消息，也给我点成绩带来了很多“变数”。而这次最大的变数就在于 T4：
| 洛谷 | 小图灵第一版 | 小图灵第二版 |
|---|---|---|
| \(44\) | \(84\) | \(24\) |
心随着小图灵预测分数线的波动一同悬了一周，我一直在祈祷：T4 水一点，T3 骗分有分。果然 CCF 还算有良心（），最终成绩：\(100+30+4+32=166\)。在接下来的一周内，则是更为煎熬的等分数线的一周。小图灵的数据依旧在上上下下地波动，我甚至测了全省的代码，但又不知道哪些不占有一等名额。
最后分数线放出的是那么突然，江苏线意外地又是 \(150\) 分。
虽然代码当中还有很多可以优化的地方，就如 T2 暴力要求的组合数，稍微想一想就知道其实是一个多重集的排列数，而那个式子稍加化简也能得到多重集排列数的计算式，本身薄弱的数学功底、微薄的算法储备也限制了我能想到“多重集”（事实上这东西我背过，但也仅限于背过，而且考试的时候都忘了）的可能；T3 因为经验不足（大概），DFS出现 \(n\) 变成 \(0\) 的原因竟然是把 \(n\) 设成了局部变量（）；T4 如果时间充裕甚至可以搞一搞第 \(9\sim 10\) 个点。当然，从结果上来看，我的退役赛，终于可以说是不留遗憾了。
结语
初入竞赛圈之时，便在不停地想象退役时的场景；而在退役之际，又在回忆出入竞赛时的每一刻。2017，我记得我是怎样跟着初中的教练误打误撞混进了 OI 的圈子；我记得我是怎样在一个只有5个人的考场拿到普及初赛的 \(21.5\) 分；我记得我是怎样不懂二分，不懂递归，逻辑等号怎样写成赋值等号。我记得我曾单纯地把信息看作爱好，佛系的做题方式让我的洛谷AC数一直不超过 40；我记得我曾分不清信息技术和信息学，一直用工程的眼光去看待竞赛题目。
我也不会忘记 2018 年我第一次走入南航校园，更加彻底地了解了所谓自主招生，见证了史上最难的一次普及复赛。自那时起，头脑中更常地会闪过一些好似梦幻的事物——人群、聚光灯……我更不会忘记 2019 年参加的夏令营——让我融入了 OI 的圈子，感受到了信奥选手之间那独有的凝聚力。
CSP-J 2019，240 分，压线一等。——但凡少了一分，我可能都没法进入现在所读的中学。
2020 年，初入高中的我请掉了所有能请的假来训练，最终还是以我校近乎垫底的成绩拿到了 NOIP 三等。
\[\displaylines{ 2017.10.15\sim2021.11.20 \\ \text{1497 Days in all} }\]做过的题目并不多，好多题最终都半途而废；好多场 CF 都打得心不在焉，也有好多算法没有学过。既然退役了，那也只能放下了。
颓废过，自责过；拼搏过，失落过。是终点，亦是起点。
\[\Large 高考\mathcal{rp++}！\]AnicoderAndy
Dec4.2021 - Jan24.2022