OI 2021

暑假集训

$\text{2021.7.31} \sim \text{2021.8.5}$ 这 $6$ 天内完成了 $55$ 道题目，其中最常见的错误有：

• 审题不仔细导致程序写挂
• 数组开小导致运行错误
• 数组开大导致空间超限
• $\text{DP}$ 边界设置错误
• 将 $\text{DP}$ 贪心化
• 不开 $\texttt{long long}$
• 二分答案边界设置过小
• 常数因子过大影响程序效率

常州集训 Week 1

经过多方面的努力，我们学校的 OIer 获得了前往常州一中集训的宝贵机会。

$\text{Day 1 2021.10.2}$

第一次来常州一中，在无比激动的心情之下大致浏览了校园风貌，随即开始参加模拟赛。

今天的 T1 是一个简单的贪心签到题，T2 是一个稍需一点技巧的贪心，T3 和 T4 都打了暴力。期望得分 $250+$。

但出分之后发现 T2 全爆了，原来是在作乘法的时候没有加 $\texttt{1LL*}$……

下午听了讲评和数据结构专题。

$\text{Day 2 2021.10.3}$

一整天的讲座。由于实力太弱再加上主讲人平均五分钟口胡一道紫题难度以上的题目，因而跟不上节奏而且听不懂大部分内容。只能勉强接受稍简单的部分。晚上结合自身情况刷了一些题目。

$\text{Day 3 2021.10.4}$

相比于昨天一整天的讲座，今天是一整天的模拟赛。

上午的模拟赛：T1 是一个组合数学的签到题；T2 不会，直接骗分；T3 欲用 $\texttt{map}$ 配合容斥维护，但没有调出来。最终得分 $100+10+0=110$。

下午的模拟赛：T1 是一个细节较多的贪心；T2 是一个简单的 $\text{DP}$；T3 是一个较难的 $\text{DP}$，考场上找了 $2 \text h$ 的规律，但宣告失败。最终得分 $60+100+0=160$。T1 因为细节没注意到位而挂掉，T3 交了记搜，但炸了。

晚上把前一天的入门组题刷掉了，但有一道题还是调了十几分钟。看来真实水平暴露出来了啊。

从今天的表现可以看出最近状态不太好，排名都是 $16/36$，还需注意好细节。

$\text{Day 4 2021.10.5}$

上午进行模拟赛：

• T1 是一道贪心，但由于自己语文不好而没有拿到满分。
• T2 是一道数学题，赛时没有想出来，只能打暴力。该题在洛谷上评到了紫题难度，但实际上经过推算也不难做。
• T3 是一道随机化题，赛时打了一个用 $\texttt{map}$ 维护的暴力，本来可拿 $50$ 分。但由于细节再次注意不到位而爆零。
• T4 是一道难度中等的图论题，赛时由于 T2 考虑太久而没有写。

本来得分可以是 $100+30+50+0=180$ 的，但挂成了 $50+30+0+0=80$，排名降到了 $25/36$。

下午主讲人进行了以「OI 中的数学问题」为题的讲座，内容包括最简单的快速幂、线性筛和较难的组合数、欧拉函数、费马小定理等。个人认为这次的内容至少还能够接受，不像前几天那么难，收获还是不小的。

晚上按自己的思路把昨天上午的 T3 调过出去了，貌似方法和其他人都不大一样。具体是对每个字符串跑 $\text{DFS}$ 记录贡献，最后容斥计算答案。

$\text{Day 5 2021.10.6}$

上午进行模拟赛：

• T1 可以反向求最短路，考虑到边权为 $1$ 可以直接 $\text{BFS}$。考场上顺手打了 $\mathcal O(n \log n)$ 的 $\text{Dijkstra}$。本来认为 $n \le 10^7$ 可以通过，但程序常数较多，只拿了 $80$ 分。修改为 $\text{BFS}$ 后才可以拿满分。
• T2 一开始没看出解法，但到了考试最后半小时想出了贪心正解，即离散化后模拟取最大值。
• T3 看出来是一个扫描线，但自己不会打所以只能暴力。
• T4 没来得及做，实际上是一道「多合一」的题。

T1 的失败也警示自己不要拘泥于一些经常打的算法，更不要看到题目就想当然。这次挂了 $20$，下次说不定就是 $100$。

这次最终得分 $80+100+10+0=190$，排名 $12/38$。今天虽然排名有所上升，但依然有进步空间。

下午讲评后，由于第二天要参加月考，因此四点多就出发回家了。

临走前拍了校园内的一些照片和常州一中夜景：

CSP2021 复赛

$\text{Day } -\inf$

国庆常州集训回来之后立刻月考，年级排名 $150+$

$\text{Day -1 2021.10.21}$

晚上在机房与老师一起观看领队会议。江苏新开发出了一个 JSOI Linux 收发系统。其优点是能在服务器上用最接近于评测的编译器进行编译运行，能有效避免 Windows 编译通过而实际 CE 的情况。缺点是评测较慢，但好在考试时可以不依赖它进行调试。

$\text{Day 0 2021.10.22}$

CSP 提高组考试前一天我居然才开始学习单调队列！！！

$\text{Day 1 2021.10.23}$

• $\texttt{[7:25 - 11:00]}$ 学校周六正常上课，所以翘了课去机房刷题。先做了前几天洛谷比赛的一道橙题，然后又敲了一些板子来加深记忆。
• $\texttt{[11:00 - 14:00]}$ 出发前往南京航空航天大学将军路校区。在入场前膜拜了同校的大佬，希望可以增加一些 RP。

• $\texttt{[14:00 - 14:30]}$ 调试过程中先敲了快读。虽然前几次都没有考到，但我还是打算打一下线段树（事实证明这次确实考了），随后打了最短路、最小生成树之类的。同时熟悉一下新的收发系统。

• $\texttt{[14:30 - 14:35]}$ 大致浏览了一下题面。第一眼感觉 T1 像一个二分答案；T2 数据范围较小，但可能不太好做，貌似暴力好写一些；T3 爆搜实现不难，可先骗取一定分数；T4 细节多，估计暴力都难打。决定开题顺序为 $1 \to 3 \to 2 \to 4$。

• $\texttt{[14:35 - 17:00] T1}$

  • $\texttt{[14:35 - 15:00]}$ 开始考虑 T1 的做法。由于浏览题面时感觉可以用二分答案，因此这个实际上错误的思路束缚了我很久。后来发现有国内国际两种航班，虽然单独考虑存在单调性，但同时考虑则失去了二分所必需的性质，也证明了二分实际上不可行。
  • $\texttt{[15:00 - 15:15]}$ 本来以为想到了正解但未遂，这在考场上对自己的心理影响无疑是巨大的。为了有效减小这种负面影响，我决定先打暴力。瞄了一眼题面，发现可以先离散化所有时刻，然后再按时刻从小到大排序所有航班信息。接着外层枚举国内/国际分配到的廊桥数量，内层扫一遍排序后的航班信息统计答案即可。若 $n,m_1,m_2$ 同阶，这样的复杂度是 $\mathcal O(n^2)$，可以先保证把 $40$ 分拿在手里。调了一会儿之后便过了所有样例和大样例。
  • $\texttt{[15:15 - 17:00]}$ 打完暴力之后设法考虑是否能优化。经过一个小时在草稿纸上的思考之后，发现无法找到更简单的方法。于是就把暴力代码打开，把中间计数器输出，猛然发现计数器大小是单调不递减的！因此想到了可以二分并线段树维护，可以将平方优化为 $\log$。怒码 3KB 后过了样例、大样例。但提交了无暴力的程序，事后想想也是十分惊险。

• $\texttt{[17:00 - 17:15] T3}$ 对于暴力，可以用 $\texttt{vector}$ 维护当前状态，然后 $\text{DFS}$。但写完后过不了大样例，于是静态查错了半天，没有发现问题，因此决定先开 T2。

• $\texttt{[17:15 - 18:00] T2}$ 看起来可以搜索，但打到一半发现很难判断当前字符串是否合法。考虑了一会儿发现想不出合适之法，就打了一个乱搞。

• $\texttt{[18:00 - 18:15] T4}$ 发现可以状压，复杂度为 $\mathcal O(2^{nm})$，可得 $10$ 分。但写完后又过不了大样例！！！

• $\texttt{[18:15 - 18:25] T3}$ 看能不能逆天改命，把 T3 调出来，最终失败了。

• $\texttt{[18:25 - 18:30]}$ 检查所有程序，防止出错。期望得分 $100+0+0+0=100$，同时幻想弱数据可以让自己多拿几分。

• $\texttt{[18:30 - 19:00]}$ 考试结束后认真聆听旁边的人的交谈，听到了网络流，看来自己会的真的太少了。

• $\texttt{[19:00 - 20:30]}$ 在车上与同校大佬交谈，发现他们 T1 也用的是线段树，但思路与我完全不一样。考虑到后面三题都可能爆掉，因此感觉自己可能没戏了，于是干脆闭目养神。

• $\texttt{[21:30 - 22:00]}$ 在洛谷和 InfOJ 等 OJ 估分，发现 T1 好像能 A，但其它三题一分都没有。

$\text{Day 2 2021.10.24}$

早上起床后觉得这次 T1 真的有惊无险，决定在洛谷上写个题解整理一下思路。下午看新闻发现南航发生了一起严重的爆炸事故。想起前一天刚在那里考试，不禁思绪万千。

$\text{Day 8 2021.10.30}$

在常州一中参加信息集训，晚上通知说 CSP 成绩出来了。查了一下发现真的只有 $100$。

$\text{Day 14 2021.11.5}$

认证名单出来了，分数线只有 $120$。其实只要再稍微努力一下就有国一。这次只能 2= 滚粗了。

CSP 总结

从去年和今年的 CSP 来看，T1 的难度往往不是最简单的——事实证明去年 T2 和今年的 T3 都稍容易一些。因此在考场上要明确开题顺序，果断作出要考虑正解还是打暴力的选择。但最重要的还是要提升自身实力，多学习一些实用算法，避免在考前一天还在学习基础算法。

常州集训 Week 2

这周继续前往常州一中集训。

$\text{Day 1 2021.10.30}$

上午进行模拟赛：

• T1 反向 $\text{DFS}$，途中标记即可。
• T2 打了暴力。
• T3 貌似跟图论毫无关系，用二分答案过了。
• T4 是一道差分约束题目，用暴力拿了 $10$ 分。

最终得分 $100+20+100+10=230$，排名 $15/27$。

下午讲评时，主讲人说 T3 本来是用 $\text{SPFA}$ 过的，但实际上二分答案效率更高。讲评后主讲人进行了图论专场讲座，为我们普及图论相关知识。

晚上练习时自学了模拟赛 T2 的二分图和 T4 的差分约束。

$\text{Day 2 2021.10.31}$

上午进行模拟赛：

• T1 是一道数学题但没想到正解，暴力骗了 $60$。
• T2 是一道组合数学，但依然没有看出来，只能打暴力。
• T3 没来得及做，程序里只输出了一串 $-1$。

最终得分 $60+40+10=110$，排名 $14/26$，并不算很好。

下午讲评才发现 T1 如此简单。而 T3 题目名为 $\texttt{kal}$，实际上考的是 $\text{Kruskal}$，只要配合并查集即可轻松过题。讲评结束后就回家了。

拍照留念：

$\text{Day 3 2021.11.1}$

在同校大佬的指点下，写了一个效率更高矩阵快速幂，甚至可以把数据范围从 $200000$ 开到 $10^{18}$ 以上。这也说明了 std 也不一定是最优解。

$\text{Day 4 2021.11.2}$

在离开常州后的几天之后，常州出现了确诊病例。幸亏没有受到影响。

常州集训 Week 3

由于疫情，这几周都在学校通过线上形式集训，还邀请了扬州中学、华罗庚中学的同学参加。

$\text{Day 1 2021.11.6}$

上午进行模拟赛：

• T1 其实做法很显然，但赛时又没有想到。赛时对 $1 \sim 5$ 和 $6 \sim 7$ 测试点进行判断，实际上可得 $70$ 分。但由于数据较水，实际上拿了 $80$。
• T2 是一道莫队，但赛时并不会，就用 $\texttt{vector}$ 配合 $\texttt{lower_bound}$ 进行暴力。但该题数据依然很水，拿了 $80$。
• T3 打了 $60$ 的暴力。
• T4 打的是 $30$ 的暴力，但挂成了 $10$ 分。

最终得分 $80+80+60+10=230$，排名 $10/45$。由于数据较水相对前几次还是不错的。

下午讲评后进行 $\text{DP}$ 专题，包括对 $\text{DP}$ 的若干优化。结束之后回家进行了一些练习，学习了莫队算法。

$\text{Day 2 2021.11.7}$

上午进行模拟赛：

• T1 是一道数学题，没能想出来。
• T2 是一道单调队列，但调炸了。
• T3 和 T4 直接上暴力了。

最终得分只有 $0+0+10+0=10$，排名 $33/44$。可以见得状态非常糟糕，一道简单的单调队列居然炸成 $0$ 分。

下午讲评了各题做法，实际上 T1 的做法用到了 NOIP T2 上。讲评之后没有进行讲座，留了时间自主练习。

常州集训 Week 4

这周依然在学校进行。

$\text{Day 1 2021.11.13}$

上午进行模拟赛：

• T1 是一道二分答案，但赛时只打了 $50$ 的暴力。
• T2 通过打表发现与斐波那契数列有关，但没有找到规律。因此只打了 $40$ 的暴力。
• T3 没有理解题意，再加上时间紧张，没有拿到分。
• T4 通过朴素暴力可得 $60$。

最终得分 $50+40+0+60=150$，排名 $12/42$。

下午讲评发现 T2 可以直接递归求解。之后进行「数论简谈」、「凸壳」、「线性数据结构基础」三个专题讲座。

$\text{Day 2 2021.11.14}$

上午进行模拟赛：

• T1 是一道 $\mathcal O(nk)$ 的 $\text{DP}$。
• T2 看起来就是背包，但居然没有调出来。
• T3 和 T4 都打了暴力。

最终得分 $100+30+70+20=220$，排名 $20/41$。

下午没有进行讲评和讲座，于是把 T2 和 T3 正解调过去了。

NOIP 2021

$\text{Day } -\inf$

这段时间继续参加模拟赛。考前新学了莫队、$\text{Tarjan}$ 算法，复习了拓扑排序、线段树、$\text{Dijkstra}$ 等。

$\text{Day -16 2021.11.3}$

收到通知，获得参加 NOIP 的资格，那就赶快准备起来。

$\text{Day 0 2021.11.19}$

比赛地点在金陵中学河西分校。由于早上比赛，因此入住酒店。与 CSP 相似，这天晚上受教，打了 $\text{KMP}$ 的板子，但实际上并没有理解，很快就忘记了。所以干脆去打其它的。

$\text{Day 1 2021.11.20}$

• $\texttt{[7:00 - 7:45]}$ 在考场建筑「创想空间」外排队，想起了 NOIP 是最关键的一战，心里无比紧张，但还是尽全力尝试平复心情。
• $\texttt{[7:50 - 8:30]}$ 敲了一些可能用到的板子。
• $\texttt{[8:30 - 8:35]}$ 浏览题面。发现 T1 是一个纯询问且每次询问只有一个的题，又因为数据范围不小，感觉需要一定的预处理。T2 和 T3 一看像数学题，可能存在一些有用的结论。T4 跟 CSP T4 的题面都很长，估计短时间无法突破。确定开题顺序为 $1 \to 2 \to 3 \to 4$。
• $\texttt{[8:35 - 10:30] T1}$
  • $\texttt{[8:35 - 9:00]}$ 先打了最原始的 $\mathcal O(N^2 \lg N)$ 预处理暴力，可以通过小一些的样例。
  • $\texttt{[9:00 - 10:30]}$ 进行一系列的优化。先是发现了不符合的整数没必要继续跑循环，优化后大样例跑了大约 $4$ 秒，还需进一步修改。随后发现只要被标记了就无需继续覆盖，因为后面的肯定已经覆盖完了，这样之后大样例所需时间为 $1.004$ 秒。于是考虑卡常，把快读全部换成 $\texttt{fread}$ 读入，时间降到 $0.6$ 秒。加了快写之后优化到 $0.4$ 秒。虽然复杂度不好证明，但优化后感觉应该不会有什么问题，就先交到收发系统里去了。
• $\texttt{[10:30 - 11:00] T2}$ 先打暴力 $\text{DFS}$，能过测试点 $1 \sim 4$，$20$ 到手。后来想搜索有很多重复状态，联想到了 $11$ 月 $7$ 日模拟赛的 T1，通过数学手段进行了一定的优化。测试点 $14 \sim 15$ 的规模大约跑了 $2$ 秒左右，运气好是可以通过的。
• $\texttt{[11:00 - 11:30] T3}$ 先写了一个 $\mathcal O(1)$ 求方差和修改方差值的函数备用。接着写了 $\text{DFS}$，用 $\texttt{map}$ 和 $\texttt{vector}$ 维护当前序列是否已经访问过，然后直接爆搜。想了一下之后发现测试点 $1 \sim 3$ 能过，至少有 $15$。
• $\texttt{[11:30 - 12:30] T4}$ 暴力调了一个小时过不了任何样例，决定不管了。
• $\texttt{[12:30 - 12:50] T3}$ 发现 $n \gt 4$ 的情况运行时间都很长，于是干脆对 $n \gt 4$ 的情况乱搞。具体就是对于每次拓展选择修改后方差值最小的继续拓展，有点贪心的特点，但错误性也是显然的——过不了下发的样例。但与其等着暴力代码超时，还不如对拿不了的分的部分打一个乱搞，同时幻想能多骗一些分。
• $\texttt{[12:50 - 13:00]}$ 检查所有程序，防止出错。期望得分 $100+[20,30]+[12,?]+0=[132,?]$。
• $\texttt{[13:00 - 15:40]}$ 回到酒店吃饭，然后上车返程。期间与同校大佬讨论了 T1 的做法，发现就是类埃氏筛。而 T2 可以打 $60$ 的状压而自己没有看出来！！！
• $\texttt{[15:40 - 16:30]}$ 回到学校之后周六课程还未结束，在备用教室中等待。测了一下洛谷民间数据，T1、T2 得分分别为 $100,30$，符合预期。
• $\texttt{[18:00 - 20:00]}$ 到各个 OJ 测民间数据，其中大部分是 $100+30+28+0=158$，但甚至有一个高达 $100+30+52+0=182$。貌似 T3 乱搞居然能拿分？！

$\text{Day 2 2021.11.21}$

发现 T1 做法不严谨，直接取所有询问的最大值加了 $1000$ 作为类埃氏筛的最大值，但实际上可以轻松被 $2 \times 10^5$ 个询问值为 $7 \times 10^6-2$ 的数据卡掉。虽然好几处 OJ 都没有出现这种数据，但最坏可以直接 $100 \to 50$。

莫名联想到：

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
$100 \rightarrow 60$；
$\text{Ag} \rightarrow \text{Cu}$；
最终，他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。

虽然这并不是 NOI 这么重要的赛事，被卡的概率也不是很大，但一旦分数降到 $50$，后果也是很严重的。这也提醒自己无论是否在 OI 中，都要注意细节。

$\text{Day 10 2021.11.29}$

期中考试成绩出来了，成绩甚至比月考还要不堪入目

看来竞赛真的会让文化课成绩上下波动，搞竞赛的风险也很大，但为了 OI 还是值得的。

晚上回家后发现官方成绩也出来了：

看来运气真的不错——T1 没有被卡，T3 的乱搞还有这么多分。

$\text{Day 14 2021.12.3}$

获奖名单出炉。基准线是 $140$，江苏国一分数线是 $150$，这次终于拿到了国一。这也应该算是自己 AFO 的标志了。下面一定要好好忙文化课，把前面落下的尽快补上去。

竞赛生涯总结

这几个月的信息竞赛虽然给我的学业带来了巨大的压力，但实际上也让我收获了很多。

虽说在五大学科竞赛中，信息可能算得上是与高考关系最小的一门，但它实际上教给了我很多可以适用于平时学习中的经验。从这次竞赛来看，往往题目都很难彻底解决，但有部分分可以获得。与其绞尽脑汁思考一道题目的正解，不如想办法多拿一些分数或者利用剩余时间去检查错误。再者，信息竞赛让我深刻地认识到了细节决定成败的道理。理科试卷中在细节上犯错往往会错掉整个大题；而信息竞赛中一旦出错，可能会白白失去几十分甚至一题从 $100$ 分掉到 $0$ 分。

参加信息竞赛源于我个人的兴趣。我从小学开始接触 JavaScript，学会了如何制作最简单的动画程序。虽然这在现在看来简直微不足道，但实际上培养了我对编程的兴趣。进入初中，我在初一和初二甚至连普及组复赛都没有资格参加。在面临选择是否继续的关头，我还是决定坚持下来。到了初三，我利用几乎整个国庆的时间着手准备初赛，最终才得以进入复赛。复赛中我如愿以偿，获得了普及组一等奖和提高组二等奖。

到了高中阶段，学业更为紧张，竞赛的功利性也更强。从暑假开始，马老师就带领我们大量做题。高中的竞赛相比于之前的一大区别是有了与高手交流的机会。有一个优秀的交流伙伴，既能分享心得体会、交流解题方法，又能相互竞争、共同进步。在这样的环境之下，我成功地进入了 CSP 提高组的复赛，获得了后续的参赛资格。CSP 的复赛我只拿到了二等奖。虽然 CSP 成绩并没有 NOIP 联赛含金量高，但每个机会都要尽可能把握住。

信息竞赛知识的积累可以视为制作珍珠项链的过程——通过做题探索并学习新的算法，从而不断完善知识体系。在准备联赛的过程中，马老师多次带我们去常州一中集训，也不辞劳苦地陪伴我们在学校机房做模拟题。集训和平时模拟中难免会有题目考查自己掌握不牢或完全生疏的内容，而这些题目不仅有助于引出新的知识和算法，而且比单纯学习给人带来的印象更为深刻。同时，集训过程中的交流机会也变得更多。我与同校高手进行交流之后深深感受到了巨大的差距。在认识他人和认识自己的过程中，我更加明确了自己的不足。

在这样的自我提升之下，我怀着紧张的心情，踏入了 NOIP 联赛的考场。这次相比于 CSP 复赛的 $4$ 个小时，多了 $30$ 分钟的考试时间。我决定先利用前一个小时的时间把第一题做完。第一题难度不是很大，于是在思路明朗之后就进入了下一题。第二题自己没想出正解，但进行了合理的“骗分”。值得一提的是，这道题的思想在联赛前一个月的模拟赛中曾经出现过。当时那题自己没有做对，从而导致印象深刻。以至于到了赛时，那道题立马从我的脑海中浮现出来了，让我从原来的 $20$ 分提高到了 $30$。第三题仍然采取写“暴力”程序“骗分”的做法，期望得分是 $12$ 。第四题本来可以通过“暴力”拿到 $24$ 分，但没能成功。这时我作出放弃第四题而完善第三题的决定，通过随机的手段多拿了一些分数。最终得分是第一题 $100$ 分，第二题 $30$ 分，第三题 $40$ 分，第四题 $0$ 分，共 $170$ 分，超过了国一线。拿到国一这个奖项，其实并不完全在于自己对知识和算法精通的掌握。考试技巧的合理运用也尤为关键。正如马老师所说，只要把会做的题目做对，再“骗取”一些分数，就离国一不远了。当然，客观来说，这样的策略是有很大的运气成分的。真正想有稳定的成绩，还要增强自身实力。但是在思路实在无法打开的情况下，进行一些合理的尝试也是可取的。就像前面所说，这一点在很多其它场景中也是适用的。

一等奖对于很多竞赛生来说绝对算不上是终点——他们有着冲省队、争金夺银的宏大理想。拿到一等奖也绝不等同于已经在这一方面有了很深的理解和认识。考虑到自身实力的不足和高中学业的紧张，大概我的信息竞赛生涯就要到此结束了。这段时间里，我想感谢始终鼓励自己的父母、辛勤付出的马老师和学校的大力支持。一起参与竞赛的校友也一直陪伴着我。他们既是我的知心朋友，又是我的潜在竞争者。没有了他们的帮助，我绝对不可能把这一兴趣坚持到现在。

希望自己能把耽误的功课尽快补上去，在后续的高中生活中取得更大的进步。同时衷心祝愿一中的各科竞赛在未来取得更为丰硕的成果。