【杂文】银色的 NOI2020（退役记）

# **【杂文】银色的 NOI2020（退役记）** [$\color{red}\Large{{\mathcal{M}}\color{#fbe044}{\mathcal{y}}\ \ \color{green}{\mathcal{B}}\color{#46f1e7}{\mathcal{l}}\color{blue}{\mathcal{o}}\color{purple}{\mathcal{g}}}$](https://www.cnblogs.com/Xing-Ling/p/13532770.html) 在这篇日记里记录 $\text{NOI}$ 前夕至考试当天的事情，日期紧接 [**【杂文】$\text{SCOI2020}$ 游记**](https://www.luogu.com.cn/blog/ChenXingLing/post-za-wen-scoi2020-you-ji)，可能会写考后题解，也可能没有。 第三次写“退役”记，前两次都假了，这次不可能再划掉“退役”二字吧。 我很清楚自己与别人的差距，不敢奢求太多，只要运气好拿个 $\text{Ag}$ 就谢天谢地了。 $\text{NOI}$ 的难度一年比一年高，而以我的思维水平连一道省选级别的数据结构都做不出来，难道考场上只能寄希望于死磕字符串套路码题？或许做出一道像[你的名字](https://www.luogu.com.cn/problem/P4770)那样的题能使我的分数不会太难看？ 感觉进省队后反而变得越来越悲观.... ## **时间：2020-6-29** 为了用生成函数解题，发现自己不得不学积分了。 因为停课的原因没有在课堂上系统学习导数，用那点少得可怜的求导基础强行自学积分简直就是找死的行为。 ~~然而我还是直接莽了上去。~~ ~~于是自闭一下午。~~ ## **时间：2020-7-4** 网上买的组合数学、离散数学和具体数学终于到手ing.... ## **时间：2020-7-10** 这两天机房里只有我一个人，旁边教学楼的 $\text{whk}$ 选手又都搬去高三校区了，冷冷清清的....有点不知所措..... 此时得知一直以来膜拜的对象进了 $\text{E}$ 队，上 $\text{noi}$ 官网找出名单一看：初二。 唉...... > 如果一位选手比你强还比你小，那你就打不过他了。 感觉我的心态可能出了点问题，整天对着一群初中起步的 $\text{OIer}$ 唏嘘感叹。 ## **时间：2020-7-20** 在 _【禁則事項】_ 做了套 $\text{NOIP}$ 模拟题，结果 $\text{T2}$ 写挂、$\text{T3}$ 没写完，被两个初中生吊锤几十分，颜面何存啊 o(╥﹏╥)o ## **时间：2020-7-21** 早上和 $\text{pkh}$ 一起做 [$\text{LibreOJ NOI Round 1 day2}$](https://loj.ac/contest/7)（貌似还有 $\text{cxr}$ 和 $\text{yy}$ ？） 冷静分析，发现 $\text{T1}$ 可以新建节点 $n+1$ 作为根，然后连出一颗树，随便上个啥数据结构 $75pts$ 到手。$\text{T2}$ 想了下裸暴力直接走人。$\text{T3}$ 暴力背包+模拟退火瞎调参搞到了 $60pts$ 。 吃完饭回来看了看当年的排行榜，貌似 $rk\ 6$ 了？或许把剩下的 $2h$ 做满还能再往前挤挤？不过要忙着准备 $\text{NOI}$ 报名的相关资料，便丢到了一边。 下午考 $\text{NOIP}$ 模拟赛 $\text{day2}$ 时跑一边刷 [计数水题](https://www.luogu.com.cn/blog/ChenXingLing/solution-p6076) 去了，喜获抱铃awa。 ~~狂刷一周计数题，就只用熟了二项式反演，我彻底没救了。~~ ## **时间：2020-7-25** 努力了一把，继续深入学习多项式科技（虽然连全家桶的一半都没到）。 ## **时间：2020-8-9** 准备齐全，再一次穿上了小裙子，自我感觉良好，心情舒畅（雾）。[](https://www.luogu.com.cn/blog/ChenXingLing/zhei-shi-shui-post) （上一次简直差劲到了极点，甚至坏了一天的心情） ## **时间：2020-8-13** 花了大半天时间填 [广义 $\text{SAM}$](https://www.luogu.com.cn/blog/ChenXingLing/solution-p6139) 中留下的坑。 晚上最后一次整理模板库。 ## **时间：2020-8-16 (day-1)** 最近两天雨下得非常大，两双鞋都湿了，换洗衣服也不好找，只能将就着出发惹...... 早上看了会儿 $\text{Matrix67}$ 的博客，~~被吓得不轻（涩涩发抖）~~。  第一次坐飞姬，之前还担心会晕机，坐上去后却感觉飞姬莫名可爱 awa 座位在引擎稍往前一点（教练特意让我坐了靠窗的位置），能清楚得看到漩涡气流（或许是因为下雨显得比较明显？）。 刚上去时比较热（那种冬天在热空调下的感觉），顿时昏昏欲睡，而姬也因为雨突然下大延后了起飞时间。 也不知道过了多久，突然开始高速移动，被惊醒的我望向窗外，周围的景物移动得越来越快，最后“咻”得一下就离地了，冲向云霄。 坐上去后又好奇姬的降落方式，没想到就是直接贴地滑翔。 贴身感受到了人类科技的威力，有一种说不出的感受，只能用可爱来形容了 qwq 天上的景色非常棒。 这是渣机瞎拍的图片：      > 山田：好棒，太棒了！云层上面永远都是晴天哦，加瀬さん知道吗？ 加濑：嗯...应该知道吧。 山田：即使是不顺心的时候、烦躁的时候、花儿枯萎的时候，在云层上面，也一直一直都是晴天，这么一想，就又有努力下去的动力了，不是吗？ 加濑：嗯，是啊。 ——あさがおと加瀬さん 湖南简直热到虚脱，要融化了.... 寝室比咱学校宽敞，食堂饭菜还行，有各种海鲜好评，有各类蔬菜好评，小蛋糕味道不错，甚至于后面几天都没怎么吃米饭（~~醒醒，你是南方人~~）。 晚上面姬铃，随便瞎聊了一会儿。 ~~我似乎比她高（笑）~~。 ## **时间：2020-8-17 (day0)** 开幕式上 $\text{dzd}$ 说要是盘子里有剩饭就扣 $1$ 分，害怕/fad 和队友们合影了，运算符站我左边...... （这密码条仿佛在暗示着什么 qaq）  昨晚因为床的原因睡得不舒服，教练特意来帮忙处理，有点小感动。 下午笔试水得不行，没啥可说的。  去年某俄罗斯选手参加 $\text{NOI}$ 因为用了 $\text{C++11}$ 语法而抱铃，然后今年编译选项就多了一项：`-std=c++11` 。过于珂怕。 不过对于我来说，开 $\text{O2}$ 才是最良心的。 ## **时间：2020-8-18 (day1)** 昨晚睡了 $8$ 个小时（~~好像是近几个月来睡得最久的一次~~）。 开场半小时看题，$\text{T1}$ 好像不太签到，$\text{T2}$ 多半是整体 $\text{dp}$，$\text{T3}$ 二维区间顺序对（这浓浓的由乃 $\text{OI}$ 既视感）。 $\text{T3}$ 特殊性质比较多，而且是序列上的问题扩展，嘤该比较好拿分，但保险起见还是决定按顺序开题。 $\text{T1}$ 稍想了会儿，发现是个矩阵弱智题，直接扩成 $w$ 倍暴力乘即可。常数略危险，用和 [$\text{NOIO#3 T2}$](https://www.luogu.com.cn/problem/P6569) 一样的套路，预处理矩阵幂次，然后查询时用向量乘矩阵降维，复杂度 $O((wn)^3\log T+k(wn)^2\log T)$ 。一开始以为矩乘会很慢，于是只处理了 $10$ 次幂，但没想到前面快得飞起、后面慢得要死，于是改成 $29$，然后 $n=50,T=10^9,k=80$ 时（由大样例手动 $\text{rand}$ 搞出来的数据）只跑了 $0.5$，感觉比较稳。 此时已经 $2h15min$ 了，准备 $30min+30min$ 思考 $\text{T2+T3}$，然后剩下的时间码代码（大概率是没时间对拍了）。 $\text{T2}$ 枚举哪些路径不覆盖的情况，剩下的边随便选，得到至少 $x$ 条路径不选的方案数 $g(x)$，然后二项式反演得到恰好 $0$ 条边不选的方案数：$f(0)=\sum_{i=0}^{n}(-1)^{i}g(i)$ 。统计哪些没覆盖时可以树上差分维护，复杂度 $O(2^mn)$，能过 $24pts$ 。然后上树剖降到 $O(2^m\log^2 n)$，卡卡常似乎能过 $40pts$（有 $\text{O2}$ 就是可以为所欲为）。 看看时间只花了约 $20min$，于是立刻开码。 然后敲完树剖板子就发现假了。 明明每次考试都在提醒自己三思而后行，$\text{CSP2019}$ 没能做到（但那题过于毒瘤，大家都没分，所以未影响成绩），$\text{SCOI2020}$ 只打了弱智暴力并没有这种烦恼，$\text{WC2020}$ 也没能做到（以为自己能写出 $\text{T2}$，结果写一半发现细节多得要命，最后放弃），$\text{APIO2020}$ 也没能做到（以为树剖啥都能维护，结果还补了棵 $\text{LCT}$，依旧假了）。 到了 $\text{NOI2020}$ 还是犯了傻，甚至犯了两次： 树剖不行，但可以用冰茶姬优化树上覆盖，于是码码码、调调调，始终在跳父亲的地方死循环，调了一个多小时，最后发现这种写法只能用路径压缩，不能用可回退的启发式合并。 于是又假了，如果要继续写的话，就得再套其他数据结构，但离考试结束只剩 $1h$，仅 $124pts$ 是肯定拿不到 $\text{Ag}$ 的，只好丢到一边去看 $\text{T3}$ 。 $\text{T3}$ 果然是最好得分的，前 $24pts$ 直接模拟一下求逆序对就完事了，复杂度 $O(nm\log n)$ 。一维的莫队暴力搞，复杂度 $O((n+m)\sqrt{n}\log n)$ 。最后特殊性质 $\text{C}$ 就 $set$ 预处理出所有逆序对，然后主席树查询二维区间内点的个数，再暴力枚举减掉内部的逆序对即可，复杂度 $O((n+m)\log n)$ 。 没料到的是，最后居然是 $\text{lxl}$ 救了我。往日的序列数据结构基础在 $\text{T3}$ 爆发，迅速打出树状数组、莫队套树状数组、主席树，顺利拿到 $52pts$ 的三个部分分。 离考试结束只剩不到 $20min$ 了，回过来检查了一下 $\text{T1}$，发现没判 $-1$ 和 $T\leqslant 5$ 的情况，赶紧改了改。 然后上厕所，回来坐在位置上发呆。 期望得分：$100+24+52=176$ 。 数据结构场都没能拿到 $200+$，明天要怎么办？ 今天的 $176$ 恐怕只能勉强上 $\text{Ag}$ 线吧。 而且没有对拍，只要写挂一道题我就彻底完蛋了。 奇怪的是，$\text{CSP}$ 时有心跳加速，$\text{SCOI}$ 时感觉心脏都快爆炸，而现在的我心情却异常平静。 $3$ 点看分。隔壁老哥自称来自弱省，说强省 $\text{SC}$ 都是巨佬，在一边疯狂奶我，结果点开一看发现前两道都挂了。$\text{T1}$ 不知道哪儿出了问题，$\text{T2}$ 容斥时 $-1$ 没有加 $P$ 取模，答案炸成了负数。 $\text{tmd}$ 你前段时间那两个月的计数都白学了？连一个取模都能搞漏，考前颓废颓傻了？ 实际得分：$75+16+52=143$ 。 听说 [国集作业题](https://www.luogu.com.cn/training/12#problems) 里的 [$\text{CF671D}$](https://www.luogu.com.cn/problem/CF671D) 稍微改改就是 $\text{T2}$ 。 这题我做过，是个整体 $\text{dp}$ 。 听说今天大众分 $202$，国集大众 $252$ 。 我 $143$ 。 教练说我们学校以往的学生很多都是 $\text{day1}$ 考炸 $\text{day2}$ 翻盘。 可我一个低智商选手还能凭什么来翻盘？数据结构都炸了，寄希望于字符串？凭三道 $\text{day2}$ 数学题碾压众人？ 教练走之后兮水也来安慰我，可我实在是忍不住了，躲进厕所揪着心哭了出来。 该来的迟早会来，从依靠暴力混入省队那一刻起，我就注定了会在 $\text{NOI}$ 倒下。 终归是要一个人面对的。 下午 $\text{matthew99}$ 神仙在 $\text{UOJ}$ 群里@我说 “辰星”=“水星”，不愧为天文巨佬。 晚上听 $\text{lxl}$ 讲题，感觉啥都没听懂，只记得 “$\text{2019-10}$ 时提供了本做法” 和 “用模拟退火、爬山算法、随机重启，跑了一天的迭代，最后弄出来的数据运行效率慢了约 $\text{10%}$”。 看来毒瘤 $\text{lxl}$ 从去年开始就在计划着出这道题了，还丧心病狂地造毒瘤数据。 前 $50$ 名、$100$ 名、$150$ 名、$200$ 名 四个段的分数线分别为 $240$、$203$、$178$、$148$，刚好被 $\text{Ag}$ 线压下 $5pts$ 。 结束后一个人在操场上呆到了九点半，本想躺下看会儿星星，但天上乌黑一片啥也没有，远处的高楼彩灯倒是挺耀眼的。 心情很不好，还是想哭。 尝试叫铃出来，但她顾着水群不理我。 也没有其他认识的人了。 自闭 $\text{ing...}$ 真是讽刺啊，昨天还刚摘抄了一句鼓励积极向上的台词，今天就几乎崩溃了。 希望明天字符串+计数+提答。 希望人没事.jpg ## **时间：2020-8-19 (day2)** >啊哈哈哈哈哈哈，今天的题真简单啊啊啊哈哈！ ——你以为我会这么说吗？ ......说不定还真会（这人疯了）。 开场即自闭：$\text{T1}$ 长得像个网络瘤，$\text{T2}$ 神仙二叉树无限生长，$\text{T3}$ 神仙弦图。 计数呢？数学呢？字符串呢？交互呢？提答呢？ ~~我 tm 翻个寂寞的盘啊~~。 省选到 $\text{NOI}$ 中间那几个月恶补的数学知识都打水漂了。 > 计数爬上王座后屁股还没坐稳就被推倒。 远古势力（图论）带着封建残余势力（数据结构）回来抢占 $\text{OI}$ 主导权。 $\text{T1}$ 想了下发现网络瘤大概只能用来骗分（还是最低档的），贪心构造似乎要靠谱一点，于是开始尝试骗分。 想了很久最后写了个蒟蒻贪心：从权值小到大排序，然后对于每个权值小于 $K$ 的 $i$，往后面找第一个权值大于 $K$ 的 $j$，用 $j$ 把 $i$ 填满，这样一直做下去就会形成一条贡献链。 然后就假了。但 $m=n-1$ 的情况似乎能过，$m>n-1$ 的部分好像也没啥问题（没有细想，不清楚正确性如何），关键在于 $m=n-2$ 的部分没法搞。 但此时已经 $2h$ 了，$\text{T1}$ 只有 $20pts$，还不确定是否正确。顿时感觉凉凉，翻盘是没有希望的了，只有看能不能卡进 $\text{Ag}$ 线。 然后就开始全程自闭： $\text{T2}$ 完全不会（暴力都不会打）。感觉天花板都快掉下来砸我头上了。 $\text{T3}$ 依旧不会。不过 $25pts$ 的性质 $B$ 似乎就是交叉着跑。写出来后发现大样例跑不出来，仔细一想才意识到有可能往回走，这样的话就得想办法跑 $dp$，但....总感觉非常麻烦，于是放弃了。 大约还剩 $2h$，$\text{T1}$ 不知道贪心是否正确，$\text{T2}$、$\text{T3}$ 抱铃。 > 啊哈哈哈哈哈哈，拿不到 $\text{Ag}$ 了哈哈哈！我打暴力混进了队，然后 $\text{NOI}$ 在 $\text{Cu}$ 区垫底了哈哈哈哈！ 反正都要抱铃了，还管那么多干什么？把剩下的时间都花在 $\text{T1}$ 上，说不定 $A$ 掉一道题就不至于那么丢脸了啊。 于是开始硬刚 $\text{T1}$ 。正解依旧没想出来，但用尽了毕生的骗分绝学，甚至还挂了模拟退火（不过这题随机化好像比较 $\text{lowb}$ 所以最后没使用），码了约 $300$ 行，过掉了大样例。 还有一些时间，闲得无聊看了看 $\text{T2}$，发现特判一波似乎有 $16pts$ 。 最后还剩 $30min$，又回过头来尝试证明 $\text{T1}$ 贪心的正确性，$m=n-1$ 的大概能证明正确性。然后努力一波成功用 $n=10,m=8$ 的数据 $\text{hack}$ 了前面写的背包 $dp$ 选大数剩下跑链的做法，错误的原因在于可存在两条链。 差评大样例瞎误导人，使我一度以为只会存在一条链，剩下的一定可以刚好被一个大数填满。 重新口胡了、新的暴力，大约还剩十几分钟，疯狂修改代码。 然后又假了。 早知道应该去写 $O(2^n)$ 枚举其中一条链的做法的... 放弃挣扎，开始收拾东西。 离场时 $\text{dzd}$ 在一边不停地笑。害怕.jpg 出考场听 $\text{pkh}$ 说他也只写了 $40+$ ！！！震惊我妈二十年！！！ 这.... 没想到 $\text{NOI}$ $\text{day2}$ 难度居然再创新高.... 希望不要再挂分。 希望那个愚蠢的贪心能过掉 $n\leqslant 4$ 的部分分（好像这个是卡不掉的）。 希望出题人用脚造数据。 希望 $\text{T2}$ 特判分类讨论没有漏掉情况。 期望得分：$35+16+0=51$ 。 下分出分咕到了 $4:40$，我极度怀疑是出题人在对着 $\text{T1}$ 的贪心代码造 $\text{hack}$ 数据（害怕.jpg）。 在食堂等候时看漫画《一和二分之一》几度发出奸笑，应该没有人注意到吧..... 实际得分：$45+12+5=62$ 。 $\text{T1}$ 第二档 $n\leqslant 10$ 的部分居然都是人工构造的带有特殊性质的数据（即和大样例一样，都是只存在一条链，剩下的用一个大数刚好匹配）！ 感谢出题人放了我一马。 $\text{T2}$ 判挂了链的情况，$\text{T3}$ 那 $5pts$ 好像是是无解输出 $-1$ 。 $\text{pkh}$ 挂了点分，只有 $40$ 。 没翻到盘，只翻了个碗。 $\text{day2}$ 分数普遍偏低，难以拉开差距。 听天由命吧...... 晚上讲课交流，发现今年 $\text{C++11}$ 是丧心病狂出题人要求开的。 出会场后看排名，算上同分是 $\text{rk 172}$，$\text{Ag}$ 算是保住了（如果今年没有扩充名额就凉凉）。 然后就是漫长的等待签约。 滑滑梯学长主动来找我说话，有点小姬动。 由于某些众所周知的原因，今年只有清北两所学校的代表来到了这里。 面试倒比我想象的要简单，老师并没有故意刁难，随便扯扯自己的优势就好了。 结束后和徐校视频了一会儿。 另外，今晚能清楚得看到几颗星星，开心。 ## **时间：2020-8-20 (day3)** 最后一篇日记的最后一天记录？ 又是快乐的国家队答辩时间，让我们一起来看看沙雕队爷们遇到了哪些有趣的问题吧： > （$\text{zyy}$） Q: 如果因为疫情原因彻底取消今年的 $\text{IOI}$，你有什么打算？ A: 学习大学的内容。 >（$\text{lyx}$） Q: 还是和刚刚 $\text{zyy}$ 同学一样的问题。他现在高三，但你还是高二，你准备怎么办？（不要套用他的回答） A: 虽然还是高二，但我报了清华的英才班，所以也会学习大学知识。 >（$\text{zrf}$） Q: 你现在是第 $5$ 名，相比于前面四位同学，你有什么优势？（给我一个换掉前四的理由） A: 我学的早，现在也已经高三了，经历了风风雨雨，我的经历比他们绝大多数人都要丰富，我有着他们所不具备的强大心理素质。（我身经百战，我 $\text{nb}$，我 $\text{txdy}$！） Q: 你的英语口语非常标准，普通话也非常流利，但你的教练徐先友说的是地道方言，请问你会受到影响吗？ A: 语言习惯会随环境而改变，但我周围说方言的只有他一人，同学们说的都是普通话，因此不会出现这种问题。 闭幕式领了块银色的铁牌。 站在台上总感觉有点恍惚。 下午去橘子洲溜达了一会儿（温度最高时 $39$ 度......）。 晚上白嫖 $k$ 总一顿晚餐，顺便留了张合影。  最后.....再补几张照片吧：   ## **时间：2020-8-21 至 2020-8-22** 写完了回忆录：[**【杂文】我们都有光明的前途**](https://www.luogu.com.cn/blog/ChenXingLing/post-za-wen-wo-men-du-you-guang-ming-di-qian-tu-hui-yi-lu-post)