秒客网

前言

人的惰性终究是无法战胜的……说好的退役之后就更退役记，却打了好些时候的隔膜，还要给正准备省选的学弟学妹们出把力，于是鸽到了这个时候才开始动笔。

虽然最后还是以很尴尬的位置退役，但 PPT 上展示了几秒的错误国家队名单里有我的名字我就很满足了。我也是前国家队选手！!1

收拾好行囊，向遇到的美好道声别，准备开启新的旅程吧……

顺便有没有 T 的好哥哥带带我打 ACM 啊？（小声

正常加载了 HTML 之后界面右边有导航，所以更新完毕之后摘要删了。无法正常加载的应该可以 Ctrl+F5。

（好像有一个部分的索引会 bug，但是不会修啊QAQ）

我是谁？

OI 做题家 / 三次元肥宅 / 长得挺高但不会打球 / 情商极低 / 自闭青年 / 会过乐器 / 音游小鬼

NOI 2020 Rank 9，CTT2020 + CTS2021 Rank 5，成绩很好看但真相是只会做题

真正去写这个部分的时候又不知道还有什么东西可写了呢.jpg

网站	信息	网站	信息
QQ	2972737475	Email	2972737475@qq.com
OIerDB	UID32949	Luogu	Itst
LibreOJ	Itst	UOJ	Itst
Codeforces	Itst & ltst / Itst_boyfriend（这两个号因为某场比赛的神秘操作被 ban 了）	Atcoder	Itst
Codechef	ltst	Topcoder	Itst
Vjudge	psj	HDU	Itst00
Nowcoder	Itst	Github	Itst00

一般使用 QQ 作为社交工具，不知道上了大学之后会不会有改变。

我的竞赛之旅

和我同届的好哥哥们，我突然发现我的记忆已经混淆很大部分了，所以如果远古部分有误请各位友善地提醒我不要喷 QAQ

伊始——初中

一切的起点是我们初中的信息学奥赛班，回忆起来叫兴趣班或许更恰当。其进入的要求只有数学成绩好。当时数学成绩确实不戳，同时打了六年电脑游戏所以对这些略感兴趣，于是加入了这个班级。说起来这个班级的教练的姓名与某位美国知名文豪很类似，而这个观点是我后来在阮行止学长的博客时注意到的。

印象中，三年来无论是否即将有比赛，除了寒暑假会有略长一些的训练外，这个班都只有周日早上训练一上午，但机房在非教学时间可以去打代码。我们知道的 OJ 只有 NOI Openjudge，训练内容只有 Openjudge 上的题目、偶尔会下发的历年 NOIP 试题和《信息学奥赛一本通》上的题目，IDE 是调试会 RE 的 Dev-cpp，通过竞赛班认识的人除了教练和同级的几个坐得比较近的人和以外，就只有一个初二就拿到了 1= 的学弟了，不过他现在已经退组了，原因似乎是太调皮……

初中三年，班上讲完了《信息学奥赛一本通》，最初的六十来个人中很多人选择中途退出，NOIP2017 时只有十来个人了。我则节假日闲着没事的时候去 Openjudge 上板刷，把前面大概二十个部分的题目刷完了，虽然大部分都是模拟和高精度之类的无营养题，但还是给当时的我不小的成就感，似乎也打下了一定的码题基础。

三年的 NOIP 我都没有缺席，但当时根本不知道有博客这种东西，于是比赛时的细节都记不清楚了。前两次分别是 PJ 2= 和 PJ 1=，初三那次因为没做出 \(a\times b - a - b\) 于是差 35 分 1=，而当时 TG 1= 可以通过教练的神必操作获得直升资格，从而初三上学期就去长郡安心进行竞赛集训。不过好在当时长郡每年会给有直升名额的学校的初三年级办一个叫做“澄池杯”的学科竞赛，拿到决赛特等奖的 25 个人可以直接获得直升资格，然后初三下学期去长郡上高中预科，而我好巧不巧踩线得了特等奖，于是在初三下学期认识了我的高中教练，还是提前地正式开启了竞赛旅程。

过渡——初三下

（注：后来看了看，这部分和 OI 基本没啥关系，因为当时也没学啥东西，但是确实有些经历还是挺有趣的。所以如果你对 OI 外内容无感的话可以跳过这部分内容？）

这段时间因为比较特殊，学籍在初中但在高中上课，所以还是单独拎出来说说。

首先是让我有机会提前半年在长郡上高中内容的澄池杯。这个竞赛只有长郡分校的初三学生参加，其奖项的效用就是在直升判定时获得非常高的加分。初赛和复赛考数学英语和物理，内容都是中考范围；决赛则比较有趣，赛事进行一天，上午讲课，课程内容是高中学科范围内的知识，下午立即考试，数学讲的是导数，物理讲的是抛体运动，内容都是很基础的定义和应用，考的题目大概就是高考基础题合集。第一个学习的数学高中知识是导数也是挺夸张的。不过现在湖南取消了直升政策，不知道这个杯赛是否存活了。

后来是寒假和整个初三下学期的学习，这个时候大部分人还是初见竞赛，所以竞赛不是大头，主要是学科学习为主。最开始一度因为强制住宿不想去，因为初中的时候认为和一群陌生人住是非常膈应的事情，后来还是因为跟提前上学有关就去了。与我一同上课的有澄池杯特等奖的学生，还有对非长郡学校给出的一些竞赛里面招到的外地学生。不过有很多外地学生上课上到一半就被拉到别的学校去了，就感觉很离谱，只有*才会拒绝长郡（？）

当时开了语数英物化生的课，预计要讲高中课内内容。因为我们的数学老师兼班主任由于未知原因时间多能够管这个特殊班级，所以数学课都是照常上的，甚至还各种占其他的课，整个学期下来把五本必修学完了还加了好几场考试；英语课老师也很勤恳地把课都上了，还时不时要求分组表演情景剧课文，大概把前四五本的一些长课文讲了讲；化学课整体节奏也比较正常，除了感觉比课本知识要难 114514 倍；语文课反正也没有考纲之类的东西，先准备把红楼梦讲了，因为必修里有《林黛玉进贾府》，后来直接变成看老版红楼梦；生物课和物理课则是疯狂咕咕咕，一半变成自习一半变成数学课，不咕的生物课还好，物理课听得非常困倦（

上了一段时间之后就有各个竞赛组的拉人环节了，只隐约记得物理组拉人的时候提到过物理组一大优势是长郡东道主，原谅我两年多之后才知道这个优势的真正意义。当然当时我已经铁了心要学 OI 了所以就没有特别在意这个环节。同时班上人渐渐熟悉了之后开始在下午下课到晚自习的漫长的 1.5 h 时间里玩起了狼人杀，我也是第一次意识到我确实是一个永不发言的自闭青年，各位请注意以后语言游戏请主动拉黑我（

过了一个多月，大家的竞赛选择差不多到位之后上课就正式开始。我们学校没有停课的竞赛生的竞赛上课时间是周二晚自习和周六整天，我们当时也一样。第一次上课的时候，似乎是因为班上除了我以外没人搞过 OI，所以班上只有我一个人，能坐下六十多个人的竞赛机房只有一个人在训练，颇感冷清。后来最初准备去物理组的 chd 和准备去化学组的 tr 也莫名其妙地来学 OI 了，还有 sxr，ajy 和 zws，虽然太久不见已经忘掉是这个时候一起开始学的了，但看了下 LG Uid 大概还是那个时候的事情。

当时大家的训练题目来源就从 openjudge 转到 luogu 上了，做题体验相比 openjudge 确实好不少。曾经自己也参照 openjudge 那样做题，按难度排序之后一个个做，做完主题库入门再去做 CF 入门，做到中途似乎因为某道题交了很多次相同代码就被封了 TAT 再后来就有了现在 luogu 的帐号，Itst 也是那个时候取的，也不知道想要表达什么意思。开了新号之后还是觉得刷入门题没啥意思，就去做远古时期还存活的试炼场了。

当然了机房里也不一定只有 OI 选手。在教练给我们争取了每节晚自习做完作业后就可以去机房的权益之后，有些其他组的学生也会跑到机房来，我和某个数学组妹子晚自习的时候一起下五子棋应该是我在机房里的唯一一次亲自打摆（

学期中左右，似乎因为大机房有时会锁门不太方便，教练给我们在小机房安排了座位，如果有时间自习的话可以过去。我唯一一次自习课和 chd 一起跑过去自习的时候打开门发现里面坐着两个人正戴着耳机疯狂敲代码。当时觉得奇怪，只是坐在了旁边做自己的事情，自习课下课之后就溜了，不知道 laofu 和 ymd 当时会不会觉得奇怪，只不过当时要是知道他们是 laofu 和 ymd 的话肯定跑过去要签名了。然而现在还没有他们俩的签名（

时间过了很久，中间也没有学特别多东西，因为 chd 和 tr 是零基础，所以大概就是把初中学过的内容又学了一遍，而且这期间也没什么能去的比赛，所以这段时间也就浑浑噩噩地过去了。再后来，后一批直升的 zyz 来了，JX 合作学校送来的 lsy 也来了。暑假讲组合数学的时候，winlere、gql 等等人都来了，包含初三上学期就来的那部分人，这届 OI 的第一梯队选手大部分到齐了。颇有一种集齐梁山一百零八好汉的感觉（

突飞猛进——高一

暑假

暑假的时候，先是跟着学校把组合数学和概率论稍微学了学。组合数学里确实学到了不少，比如格路计数、母函数、Prufer 序列、Burnside 这些有趣的工具，同时还有后来作为我论文主题的棋盘多项式；概率论那边最初确实对条件概率还有条件概率的两个公式有了一些了解，但后来就用的很少了，对两个似乎毫不相关的事件求条件概率还是想不到贝叶斯……

似乎是同一段时间，学校里也找了不少外校强手来讲课，我们也跟着前几批选手蹭了蹭，只不过听不懂的时候就去做自己的事情了。前几次 immortaoCO 讲了数据结构，似乎当时我们只懂栈、队列、链表之类的东西，于是听得云里雾里，后来我们教练就把我们扯到别的机房去补白书内容了，好像叉姐和 WJMZBMR 也来讲了课，只是因为教练觉得我们听不懂课程内容所以没让去仰慕真人了。同时期还穿插着一些模拟赛，一些很毒瘤的记不太清楚了，只记得有一场最难的题目是找 \(10^5\) 个点的树上的点权异或和最大的路径，其他题都不是很难，然后我把那场 AK 了。虽然当时那场有一半左右的人 AK 了，但这是第一次让我有一种“我还有点 NB”的感觉。

再后来就是高二学长的模拟赛题目了。大概只对 xzy 的某道 LCT + 博弈十合一有印象了……

NOIP2018

2018 年联赛之前，ywj 和 cjk 两个远古学长给我们梳理了一些知识点，讲动态规划的那天因为讲的题目比较多，而基础的 DP 题就只要写个递推就行了，所以一天过了十来道颜色比较好看的题目。后来的模拟赛基本上都没什么印象了，只记得根根当时把某自动机游戏 manufactoria 出了个提答导致我过后一两周都在玩，最后玩通了，压轴任务是 A+B Problem。

最开始我是和大部队一起在大机房训练的，后来某一天我正在做题，我们教练突然喊起我就把我拉到小机房念叨了句“再不把你安排在小机房就浪费了。”，于是第一次认得了之前说过的在初三上学期拿了一等于是初三整年都在长郡集训的前一批选手，其中有 gzy、gcz、xzz、ych、dsl、tjj。作为自闭青年最开始自然是在角落瑟瑟发抖大气不敢出，后来混熟了之后就好一些了。在这之后我算是正式地加入了第一梯队。

NOIP2018 Day1 算是很魔幻的一场。进去打开题目，第一题看着怎么这么像积木大赛？再看了一遍题目感觉确实是积木大赛？又看了一遍好像真的是，于是直接过了。CCF 不愧是你。T2 怎么这么像小凯的疑惑？\(a \times b - a - b\) ptsd 实锤。后来冷静分析了下数据范围似乎只要背包一下就行了。T3 长度最小最大先丢个二分，后来稍微想了想，在树上做个贪心匹配很真实。写完发现自己三个题都过了的时候非常的激动，虽然事实是仍然有很多人都 AK 了……

Day2 先开 T1，发现是个枚举环边的 easy；T2 打了一万年的表，只找出了 2 和 3 的规律，于是写了份暴力上去；T3 会平方算法，但因为不会动态 DP，所以一直想着把转移看成矩阵但不知道怎么优化，于是拿了暴力的 52。后来民间数据下来的时候发现写的 T2 挂了，原因是数组初始化的时候把 \(3^0\) 初始化成 \(0\) 了，于是只有一丢丢暴力分。

最后分数是 100+100+100+100+10+52=462，似乎是没有去 WC 的机会，但是踩线有了 CTS 的机会。那年 HN 的前两名分别是没过 D2T2 的 zsy 和没过 D2T3 的 gzy，从 NOI2019 来看 NOIP 的正向筛选水平还是可以的。

THUWC2019

过了联赛之后，仍在停课的竞赛部队成员进行了大量的压缩，只有第一梯队的选手仍然在停课准备 WC，但在外校学生看来人数肯定还是很多的。除了之前提到的几个人以外，之前在大部队的 tr、chd 和 wzx 也留在机房里，同时还有四川合作学校来的高一届选手 Tgotp。

由于很多更提前学的选手也没有学完省选内容，所以当时的安排是大家把省选部分的内容都学习起来。这大概是我第一次感受到竞赛真正的学习节奏，几天之内要去消化一些之前几乎没有涉及的内容并且进行落实。虽然确实有很多内容无法立即记住，甚至很多东西过一段时间就忘了，但至少进行了大面积的扫盲。gzy 由于太强所以在好几个部分上帮我扫清了不少障碍；tr 学习数论部分时研究了斐波那契循环节的纯数论做法，他的博客中包含着普及度较高的一篇带有完整证明的数论版斐波那契循环节的文章。

中间穿插着不少的模拟赛，不少题目都是 laofu 那届传下来的。绝大部分题目也没有印象了，只还记得考过某道形如“给出 \(N \times N\) 的棋盘，要求在上面放 \(N\) 个车，其中有给定的某些位置不能放，同时两个对角线也不能放，求方案数”的题目，我当时拿着棋盘多项式和生硬的递推思路线性复杂度过了没有其他不能放位置的部分分，而其他人都是暴力分。这是我的集训队自选题的起源。因为 THUWC 近几年加入了 Day3 的工程题，所以教练还从不知道什么地方找到了 xyz32768 出的一个形如“给出一段音频，你需要用 beep 实现该音频的音乐效果”的离谱题目……

六校联考也没有断，最开始跟杭二联考了几天，被吊打到自闭，有一段时间每天要么全打暴力要么正解写挂，每天都 40pts 十分精准，感觉非常药丸。

启程前一天的传统是进行一次模拟面试，gzy 因为 THUSC2018 就签了一等所以和教练一起坐在面试官位置上。自我介绍结束之后，教练上来就问“听说你们学校有一个叫 gzy 的同学，你和他相比分别有什么优势？”我内心 OS：???要是 THUWC 面试这么问我还是别去算了。

准备了好些时间后，清华 2019 年的冬令营终于要开始了。第一次参加地位高于联赛的比赛还是非常激动的。早上九点到下午四点的长途跋涉，换完高铁换地铁，从 7℃ 的长沙到 27℃ 的广州，感到虚得布星。晚上跟 Tgotp 和 wzx 聚在一起打了场 Div.2，模拟题疯狂找不出错，最大团也不会暴力求，于是愉快打出 GG。

第二天下午是第一场测试。先看了看 T1 推了推期望式子平方很好实现于是写出 38pts 暴力分，但更进一步就不大会了。之前似乎被问到过 Gym 里的类似题目但没有去做，亏大了 TAT。T2 最开始码了个最短路只过了 Sub 1 的 \(60 \%\) 心态要崩，后来想了想 Sub 2，感觉整体二分过 \(60\%\) 非常现实，写了四十分钟过了这部分，再继续思考了下，似乎只要加亿些判断就行了。似乎写起来很麻烦的样子，于是先看了看 T3，题目名称容斥原理，抱歉我不会计数，写完 10 分打暴力溜回 T2 把整体二分写了。调了一个小时之后，在离场半小时前终于把 \(10^6\) 以外的部分分搞定。pp 分数 38+57.6+10=105.6，出场发现人均会 T1 莫队感觉基本药丸，不过一个不错的消息是大部分选手 T2 分都比较低。

第一场测试后一天上午继续第二场测试，宿舍起床广播是权御天下有点离谱。看到 T3 是计算几何题于是先去看了看，似乎 34pts 写个凸包就行于是先把这个分拿上。接着读了读 T1，改算每条边的贡献后先想了想边分治，写到一半发现是错的，然后开始慌张了，把暴力和简单特殊性质写掉跳 T2。看到 T2 这种树构造题几乎完全没有头绪，先打上 32pts 暴力之后跑路。后面把 T1 和 T3 的一些零散的部分分拿走后一边想 T1 一边想 T2，可是一点思路都没有了。pp 分数 56+32+44.2=132.2。出场听学长说是主席树题的一瞬间立即会做了，感觉自己就是个 zz。

第二场测试同一天的晚上进行的是 THUWC 的特色第三试，主题是图片的编码与处理。先是读了好久好久学习手册，手册里面经常有一些东西讲了好几大段然后接一句“本题中不会出现这种情况”真的是坑人。愉快地根据手册模拟写完 Subtask 1-3，写 4 的时候才真心感觉到细节之多。写了半个小时然后无限调试，用 text editor 打开编码才发现是 IDAT 的最后 8 个字节锅了。我的 ADLER-32 写锅了？？？赶快回去重看发现模数写成了 65536。改完还是错的？？？？？又回去重看，结果 ADLER-32 是要对原数据流计算，一段看错无限见祖宗……改了之后终于能够输出正确结果了，输入几个矩阵就可以输出一张充满色彩的图片感觉还是很有成就感的_(:з」∠)_。写完 4 只剩 20min，Subtask 5,6 很简单但是没时间写了，于是佛系地看完了学习手册。出场发现大众分是前三个 Subtask？感觉赚翻了。

再过一天是面试、讲题和闭幕式，我校进了面试的只有我和 yyb/ycb 学长。自我介绍、数学题和英文阅读还算顺利，后来提问的时候面试官问了个传统问题“解决问题重要还是发现问题重要”我二话不说直接“发现问题重要”然后面试官追问“举个例子说明”把我这种作文素材全靠编的自闭选手打懵了。

下午发协议晚了1h，前面全是讲座。讲座开弹幕好评（破音），基本上全程都在看弹幕。某讲课选手发了一个多选题：

你觉得THUWC2019如何？
A.太简单了随便AK B.太难了希望夏令营简单点 C.Day2+知乎见 D.喜欢Day2+

Tgotp 选了 A 被公开处刑（

关于第三试，当时的工作人员在讲座里表示“出题人本意就是不想让你全部做完，想让你体验一下大学赶 ddl 的感觉”代入感很强已经开始紧张了。他们在后台看成绩的时候发现 1.5h 之后（Tips：时限 3h）有人做完了前 6 个，当时工作人员在讨论他能否 AK，此时一个相关人员蹦出来说：“不可能，后面每个点标算跑 15min 怎么可能做的完！”据说 zjt 写完了前 7 个 sub，确实拥有神仙手速可以神必通过前 7 个甚至 6 个子任务！!1

最后三个都是二等约，条件是正式省队 1=，对我来说算是不错的结局了，毕竟出发前就已经做好空手而归的准备。

HNOI2019

冬令营结束之后，大部队继续被压在机房里进行省选集训，后来 winlere 也跑过来集训了。还是传统艺能的多校模拟，只不过非常离谱的事情是联考两场离不开计数，三场离不开 FFT，计数的好时代来临力！其中好些考试的成绩算上高二的也排在学校里比较靠前的位置了，不过算上其他联考学校还是不太靠前。同时在消化了很多知识点之后每场模拟赛之后的题目交流也渐渐地跟的上了，所以和高二的学长们交流也多了起来。最后几场校内测试里，gxy 的模拟题里面搬了保序回归论文里的 TC 例题，可以说是非常契合 HNOI2019 论文题遍地跑的趋势了，但当时我不太能理解整个算法，只是把算法流程记下来了顺便实现了一遍。完全没有想到这次偶遇会在我一年多后给予我重生。同时 yyb 的“给出 \(n\) 个点 \(m\) 条边的连通图”最后数据范围写 \(m<n\) 的题目开创了我们这届数据范围恶心选手的先河。

同时 HNOI 的时候大家在小机房里经常没有事干，就开始互相飞扑克牌，后来机房的供水系统时常出 Bug 于是买了若干瓶大瓶的农夫山泉，然后就开始飞农夫山泉瓶子的把手，我们这种要学习的只能把伞撑开避免被误伤；到后来直接开始肉搏，甚至回合制。iotang 就在旁边拿着祖传老人机把这些过程录了下来，取名 "gzy fighting arena"，因为从各种意义上 gzy 都是一个打十个。

虽然联考里面被不断吊打，但是绝对实力确实是涨起来了。在 Hello 2019 里面只过了 AB 自闭之后一直停在紫名，直到 EDU62 大涨一波第一次上到橙。因为高二选手打 CF 很少，所以直到 HNOI 前，CJ 现役选手的最高颜色只是橙名。同时平常考试的时候总容易自闭，所以经常在考试过程中拿些别的可做题来做，找计数题的时候找到 HAOI2018 染色，想了两三天想到了计算强制方案数再容斥的方法，当时不知道这玩意叫二项式反演，求 \(e^{-x}\) 写的竟然是对 \(e^x\) 多项式求逆，但觉得自己的做法很厉害所以记忆十分深刻。

HNOI 前几天最后一场模拟赛里出现了一个叫做回文树的字符串数据结构，之前完全没有听说过于是马上补了补，希望 HNOI 不会出现，再去恶补了下 WC 期间网络流剩下的一些习题。然后被 Tgotp 拉过去看了看制胡窜，结果看了一整个晚自习都不会做，注意是不会做不是不会写，省选前智商掉线感觉人要没。后来 Tgotp 教了教我之后梳理了下写了不到 1h 就过了针不戳。后面则是去东看看西看看，先去 FlashHu 学长的博客里复习了 LCT，再去写了写 \(99\%\) 写不对的半平面交。期间 gcz 来问我旋转卡壳求对踵点的正确性发现自己完全不会只能感性理解。深深感觉考计算几何药丸，祝愿不会出计算几何，出计算几何都是板子，出板子都不卡精度。

省选前一天先是打了一早上加一下午的 Cy2，后来想想颓一整天不太像回事，于是晚上写了个 Min_25 筛模板希望能够救点命。

Day 1。先看 T1，woc 计算几何直接当头一棒。不过给了我一种很可做的感觉，套路地枚举 \(D\)，极角排序之后枚举 \(A\)，\(EF\) 可以直接按长度开桶算，\(BC\)……想了 1h 没想到怎么算 \(BC\) 于是写了个三方暴力。然后看 T2，发现可以直接可持久化数组倍增跳 fail 然后……然后发现边界贼多、奇奇怪怪的情况也很多，实现起来非常麻烦，于是直接弃疗写了个暴力，原本准备写 50pts 的，结果写了个暴跳 fail 就变成了 20pts，还没看到要模 998244353。给前两题太多时间了，于是 T3 直接糊了个 20pts 的暴搜上去，\(n=13\) 本机过不了结果评测机过了还是有点离谱。最后看成绩的时候发现 T1 40->10 了，调了一下发现按长度开的桶竟然是 map < long double, int > 然后往里面放了确切长度于是爆精度了，故 10+20+25=55 基本垫底。HN-001 zsy 怒切 T1 虐场啦！！！yyb 也差点过了 T3。大家似乎都挂了很多分的样子，所以总榜也不是很好看。似乎 gcz 和 xzz 写了 T1 的 \(O(n^2 \log n)\) 正解复杂度的算法但是被卡常了。

Day1 凉了之后看着当晚有 Global Round 2 想着不进队看看能不能试试打上 GM，结果碰巧遇到手速场，E 过上千 F 过十来个人，半小时过完前五个就没事干了……Rk 47 上了红还抽到了衣服美滋滋。

Day 2。先看见 T2 一道计数题先扑上去，随便推推，推出式子发现不会求……\(n=1\) 的部分分似乎可以直接分治 + MTT？码码码，考场上还手推了万年没写过的 FFT，因为当时只会七次的 FFT 所以常数巨大，最后极限数据要跑 13s……最后还是退而求其次写了个 NTT，就过前 4 个点就好了。T1 只会暴力，T3 想了一会儿也只会暴力……不过还好没有挂分，30+40+30=100。gzy 似乎读过 myy 和保序回归的论文所以上来就会 0+100+50，虽然最后因为 T2 卡常掉了 10pts，不过足够把他送到 A 队了。

HNOI 后，很多学长也就退役了，其中还有些我一直很崇拜的学长。只有队线里的 zsy、yyb、ljl（Fix002：对不起我记错省队名单了，这里是 lwh，呜呜呜我错了），买了 C 的 syc 和买了 D 的 ljq 和 ycb 还在继续准备着 NOI，Tgotp 似乎被 SC 的高精题送走了最后只是个 D。虽然不是自己在经历，但却也是第一次如此近距离地感受到离开自己一年多努力的地方一切清零的伤感啊。我们这届除了 gzy 以外， ych 买了 D，其他人也啥都没有，但还是被教练拉着继续训练。

THUPC2019

CTS 和 APIO 的前几天是 THUPC。我和 gzy、gcz 组了个队，zsy、yyb 和 despair 组了一队。我们队的队名 nmdwsmduliu 来源于杭二的某场离谱联考的三道题题目名，因为确实不会取名字。试机赛没莽出皮配于是木有算导，搞完试机 laofu 带着我们去了 T 的一个食堂下馆子。

第二天正式赛，说好的 9 点开始结果咕到了 9 点半。开场看 J，这不直接枚举 + 分数规划么，后面转成的模型像是一个网络流，但是似乎很不可做？然后去问 gcz 他表示也不会这个模型。接着从前往后开，A 显然不可做，再看 B：这不签到题么，高速码出代码，结果还是比一血慢了 5s。gcz 看 C 觉得很可做，gzy 看了之后表示这不容斥+大施罗德数么，写了一会儿，抢到了一血。1024￥到手。接着看 I，发现模型是小学奥数内容，可以大力线段树搞搞。然后就开始码，被 \(A=0\) 的特殊情况吃了两次罚时。

在我写 I 的过程中，C 的出题人过来送了一个 U 的金色气球，然后采访了一波 gzy，说：你们为了拿 C 的一血竟然没有过 M！此时我们才去看 M：求 1913 到 2019 年每年的母亲节是哪一天……

差不多写完 I，gcz 又去看了一眼 J 表示：分数规划之后不是一定只选一个么？然后秒了 J。所以如果我没有搞错模型应该还可以拿J的一血？团队累赘实锤了。顺便把 M 写了，2h 的时候才过签到题真是感人。接着开大家基本都过了的 D，样例输入 2 3 4，样例输出 2 4 8，先盲猜 \(2^{n-1}\) WA 了两发，后来 gzy 冷静分析过了。最后有一定过题量的还有 F,K,L。大概想了一下 F 和 K 似乎都不太好做，看到大部分队伍都过了 L 又去看 L 结果还是不会做，于是我滚去写 H，用广义马的思路维护的话大部分步骤其实都很好写，2K 就写完了，竟然因为关同步流时混用 puts 和 cout WA 了两发。

最后过了 7 题，Rk18。切 8 题或者罚时少一点就可以进前 12 再拿钱了。zsy 他们 Rk19 刚好在我们下面。下午就是讲题和讲座，1h 企业宣讲、20min 讲题，企业宣讲感觉没什么意思就在下面摸鱼，讲题的结果和平常的讲题差不多，会的还是会，不会的还是不会。虽然有一血颁奖但是因为要去 CTS 报道所以咕掉了颁奖典礼。据场外选手说同步赛从 10:30 咕到 11:00 再咕到 12:00 还一度不能交题。

关于 THUPC 的奖金，它一年多以后才到。

CTS2019

THUPC 宣讲的时候就看见 xht37 在 QQ 空间里发酒店的图，感觉很豪华的样子，到了果然是很豪华，但很离谱的事情是我光荣落单跟一位随机群友住一间大床房？？？我无法接受。最后的结果是原来的大床房神秘 JL 网友跟别人换了，然后又有一系列换来换去的操作，然后就和一个 JS 网友住在一个标间了。我这个云玩家看网友搓炉石还是挺惬意的。早饭都在北师大附的食堂，味道比 CJ 不知道高到哪里去了。

第一天早上到得还算早，大部分选手都在体育馆楼下等，又因为大家都戴着狗牌所以偷瞄身边的人的牌上名字第一次看见了 wxh、rqy、sooke、橡树等一众神仙的真面目。进考场发现右边是 THUWC2019 一试的时候坐在我右边的 GD 女队。

开场看 T1，觉得可以从大到小依次填然后就只和当前出现过的坐标有关，然后就有一个七次方的 DP，可以过 30pts。看起来很容斥但是似乎推不动，所以先跳 T2。T2 看到白云白兔就想到被 HNOI2019 D2T2 支配的恐惧。先是直接将答案用 EGF 表示推了推发现只会平方……推了很久不会之后决定想想容斥，先把 T1 的 30pts 写了准备专心刚 T2，后来想了想之前 HNOI 时候自闭时做过的 HAOI2018 染色的计算强制的做法，丢进去发现 EGF 形式的式子得到了极大的简化，可以直接 FFT 计算所有位置的答案了！当时感觉就是一个爽，然后代码里还是用的 \(e^x\) 求逆算的 \(e^{-x}\) 所以跑起来很慢。最后看提答 T3，有不少乱搞的思路，但是手玩完前 4 个点就没时间了。最后似乎看到旁边选手有在测时间，于是测了测 T2 用时，0.95s，我慌的一批，但已经没时间改了。

不过最后没有挂分，30+100+40=170，最后八个点都是 0.9s+。场上似乎只有个位数选手做出了 T2，感觉自己十分 NB，laofu 也是第一次知道有我这个学弟。最初我对这个做法的理解还只是容斥，后来看 memset0 博客才知道原来这叫反演更合适，再到更久以后才知道这玩意是二项式反演。然而 laofu 在暑假回校给我们讲课的时候才知道有这个二项式反演做法……晚上想着既然 Day1 就有提答，那么 Day2 一定会很难吧，然后我就露出了爆 0 的真面目了。

第二天我的考场换到了一个密闭的空间里，感觉非常的压抑。开场看完题目之后发现 T3 很可做，于是去看 T3。先想想了一种树形 DP，但概率是会变的所以不能够做？想了好久还是不知道怎么写于是先滚去想 T2。T2 想了好久觉得可以枚举 LCP 后大力讨论，讨论着讨论着就头晕了，然后就先把看起来就不可做的 T1 暴力写了，之后一直讨论讨论不出什么所以也写了暴力。然后滚去写 T3，最开始连暴力都不会写，冷静了一下，想到其实可以直接把状态设为还没有被选的点的 \(W\) 之和，这样就可以转移了。看着链的部分分感觉可以把方向反了的边容斥成不存在减去将这条边方向反过来，但是一直认为如果是一个外向森林每一棵树的概率不独立所以就没管了。

最后 30+10+20=60 滚粗。讲题的时候发现 T3 概率实际上是独立的，因为每一棵树只需要满足树根在整棵树中第一个被选而和其他的树选了多少没有关系，当时整个人都要炸了。T2 的标算做法也是一个分类讨论，果然分类讨论还是太菜，zx 的做法当时也没咋听懂……T1 则是乱搞出奇迹，然而我非常不擅长乱搞，只会写写暴力滚粗的样子。

第三天早上是六选四论文答辩。听到 dzd 问 wxh“为什么成七二十几年来没有国家队？”感觉这个问题无比熟悉，因为我们班主任曾经在班上提到过好几遍 CTSC2018 的时候 dzd 问 laofu：“为什么CJ十几年来没有国家队？”。下午闭幕式 wh 的讲话让人记忆犹新，“多样的知识考察”，计数计数提答几何计数计数确实多样，Counting Totaling Summing 2019！恭喜 zzq、wxh、yjz、gjx 入选国家队，第一次也是最后一次见到第五换第四了。最后总分数 30+100+40+30+10+20=230，Rk34，拉低 Au 平均分，我还是太菜了。

APIO2019

紧接着 CTS 的便是 APIO。

第一天上午是 ljt12138 的"Paging and Caching"，内容是硬件的优化，当然除了分块和不要开大小为二的次幂的数组以外没有学习到任何卡常技巧，在掉线和不掉线之间反复横跳。下午是“从集合角度看待 DP”，立意不错但是题目也太基础了，昏昏欲睡中。晚上 lsy 由于未知原因请我和 gzy 吃了顿饭，然后就是外出比赛的日常：搞颓搞颓搞颓。

第二天是正式比赛，发现我们考场是 wxh 监考。开场看完题 bridges 和 lamps 的部分分还是挺显然的，device 感觉不可做？于是先去写 lamps 的 60pts，然后去写了 bridges 的前两个sub。接着稍微推了推 T2 发现取模之后就是 \(10^{18}\) 范围内的区间覆盖了。\(4 \times 10^6\) 的 sort 跑得飞快，于是直接过了。160min 的时候打了 bridges 的归程部分分，剩下的时间没有任何分数产出。最后想用奇怪的线段树合并过掉 T1 的完全二叉树后面发现复杂度是平方的。最后分数 100+43+60=203，出场发现 lamps 直接三维偏序，我是 sb。下午的讲题咕了，后面想了想 bridges 的时间分块，发现分块之后就是 HNOI2016 最小公倍数，我确实是个 sb。某位兔姓选手 APIO 场上使用非代码提交网站外网站却没被竞赛，这是 CCF 的管理疏漏还是 dzd 的良心发现？（雾

第三天早上是渲染算法，好像在 THUWC Day3 的时候就略微听到了，似乎听不懂然后就咕掉了。下午是 LCA 的树上线性算法，喜闻乐见地看到了十二省联考希望、SNOI2019 网络、树上 \(O(n)\) LCA和 \(O(n)\) 并查集。晚上颁奖穿越到教师节离谱，57 人卡 Au 线、68 人卡 Cu 线很离谱，Ag 比 Au 人少特离谱，kcz 和 dmy 是 Ag 最离谱。还好的是赶上了 Au 的末班车。

再到后来 CCF 评级出现的时候，我算了算 CTS 和 APIO，发现自己直接十级了，有点离谱。

THUSC2019

（编写该部分的时候我发现这部分记忆似乎被完全抹除了一样，只剩了些零星的碎片，可能的根本原因是打击太大，直接原因是鸽了游记。）

再回去休整了一会儿，又到 T 抱着 1= 的目标参加 THUSC2019。火车上教练把我拉到一边说 P 也给了 SC 资格，问我去哪边，后来我还是选了去 T。

第一天进去看看 T1。区间修改用线段树，但期望要怎么快速算呢？想了好久好久都没想到怎么算，于是先去看了看 T2，签到题直接过了。T3 是一个魔幻的题，写了点基础暴力。之后还是推了好久 T1 没推出来，于是也是暴力走人。出来之后发现人均过两题，问了问 Tgotp 原来期望的答案就是抽奖次数乘上获奖奖券与总奖券数的比值，我确实是个巨大多 sb。

第二天进去 T1 是个真 PJ 组题目，不知道 THUSC 是不是也没题出了。T2 求所有区间的信息先套路地枚举一个右端点，然后思考了一会儿把左端点贡献写成直线，然后要求这些直线在某些点上的取值的最大值。想到了这里我竟然没有去上半平面交而是想着平方地求交点之后维护扫描线后的序，不知道我在想什么，于是还是只有暴力分。T3 则是个暴力都不怎么好写的计算几何。出场之后还是发现人均过两题，为啥四个签到我就过了俩啊，自闭到飞起。晚上的第三场体验极差，只记得内容与网络传输有关，前两个 subtask 写了 1w 年调不动，似乎还被卡常了，获得了大众分 72，感觉就像是写了一场 fread 和 fwrite 较核心一点的内容都没摸着，最后一个提建议的题目也没啥想说的。

面试已经忘了干了啥了，最后讲题两个 T3 无限懵逼，工程题建议部分的名句 THU bi ge bi bu zhi dao gao dao na li qu le 出自从这一次才换到 T 的 iotang。最后因为之前就是 2= 所以奖都没有发，心态原地上天。lsy 虽然学的时间没有更长，但是拿到了 1=，虽然有年级加成，但是还是凸显出了我的弱小。后来还是好好地琢磨了下为啥发挥如此不稳定，感觉是 WC 的时候学东西太多太快，导致地基不牢，所以签到题会签不上。

NOI2019

虽然我们这届只有两个人能去 NOI，但还是基本整组都被压下来训练。模拟赛题只记得 HZEZ 出了个卡常战挑之后 CDQZ 立即回应出了个挑战指令集多项式，还有 Joker 出的用二进制读入加速读入的某牛客题加强。

同步赛第一天家里蹲。先看了一圈题目，发现 T1 非常可做，二次函数因为对称轴在 \(x<0\) 的地方所以有跟一次函数类似的单调性，搞个单调队列维护一下似乎就可以了。大力码码码，过了大样例就没管了也没有拍。然后 T2 和 T3 感觉都很难。T2 迷迷糊糊地想到了根据最大值分开进行动态规划，状态看起来不多于是大力 map 记搜，本地跑了跑好像过不了 300、10000？然后 35pts 滚粗。然后晚上粉兔告诉我先把状态搜出来就可以过 50 pts 了，自闭。T3 感觉很模拟费用流，先想了想把费用流模型搞了出来，然后就去吃饭了于是没有去想怎么模拟费用流，本来以为能过 64 结果只过了 44，比暴力 DP 多过了一个点。最后分数 100+35+44=179。晚上从家里跑到学校的时候认真地想了想情况，发现对这个费用流图模拟增广实际上挺简单的，亏死了。回去在 LOJ 上落实了下，先是用 set 写疯狂 TLE，再是改成懒惰堆还是 T，最后把最开始选择 \(K\) 对变成 sort 选才过。

同步赛第二天跑到学校去打了，去学校的另一个原因是修一修出的模拟赛。看到 T1 上来就是个二维线段树然后发现空间 128MB，出题人 ***。看了看部分分，72 pts 应该问题不大，此时 winlere 在我旁边喊 “这不是 K-D Tree 吗？”然而我当时并没有想过这玩意，觉得应该不太能过吧。后面两个题也只会暴力，体验极差所以鸽了去修模拟赛去了。预计分数 72+40+36=148，正式选手中好像进了前 100，切掉了 D1T3 好像就能踩队线，果然还是智商不够。gzy 和 zsy 进队了 orz

当年自己一个人坐在机房里瞎想的写在游记里的闲话好像不太好合并？那就直接放这儿算了。从这段时间以来，确实有很多时候会突然从机房走出去然后在走廊上徘徊好长一段时间，有的时候在想题，有的时候则去思考人生哲学去了，希望各位后来人不要向我学习。

半桶水晃着晃着一年就给晃完了。聚聚散散，高二只剩下了队爷 zsy，高一也只剩下原来的一半。
去年此时，刚开始学栈和队列。拿着 NOIP 的 462 分一路停文化课，THUWC、HNOI、CTS、APIO、THUSC、NOI，感觉自己经历了不少，又经历得太少。
还有一年路要走，却感觉自己的实力还是远远达不到标准。
已经走在独木桥上了，已经没有退路可言，风暴将至，唯有迎风前行。

生死决战——高二

暑假

暑假正式开始的时候，我就正式成为高二学生了，紧迫感便汹涌袭来。首先是维系 IOI2018 时的合作关系，把 ASDFZ 和 SXYZ 的若干学生拉到我们学校来集训，当时官方名字叫做三校国集联训，我们瞎缩写就把它叫做三国联训。三个学校的集训队年级分布很神奇，都恰好是一个高二、一个高三。第一次见到杯爷 zyy 的真面目，在他们将走的那天加到了 zyy 的 QQ，某种意义上的追星成功？也是第一次见到大家都叫仓鼠的知名选手。同时 18 年的四个国家队也回来讲了一两次课，命制了几道模拟赛题，同时每个学校也命了几道模拟赛题，做了一次好题分享。模拟赛是 OI 赛制，但因为我做在 tjj 旁边，而他有管理员账户，所以有好几场把 OI 赛制直接打成 IOI 赛制，成绩就还比较好看。

最后一场是我的题目，当时 T1 从 CF 上搬了个垃圾数据结构，T3 是从 CC 搬的一个有点构造的题目，为了卡乱搜的暴力，\(n^2\) 读入直接开了 \(n \leq 6000\)。当时 wzp 和 zyy T3 乱搞过了前八九个点，和他们一个学校的 cqz 直接用标算过了，不过他好像后来没有进集训队……T2 则是我的自选题的一个类似版本。当时的标算是我的自选题题解里给的错排推递推式的做法，后来 SXYZ 的几位和 zsy 表示在 OEIS 上搜到了，才知道了原来有用棋盘多项式+生成函数推导的优美做法。

再后来 gzy 和 zsy 安排了几次讲课，还有好些学长回来讲了讲课和准备了模拟赛题。很多的讲课内容也吸收得很彻底（低情商：很模糊，高情商：吸收得很彻底），只记得 wfj 讲了线性代数，第一次听到对角化这个概念，似乎可以对特殊矩阵做到高效的矩阵快速幂，还有 lst 讲了讲他们大学课程里的纳什博弈。

暑假里 CCF 把 NOIP 取消了，因为教育部不准竞赛收钱，我直接好家伙。顺带一提，CCF 在 noi.cn 发布取消 NOIP 的时间 20190816170251 是一个大质数。后来它的替代品 CSP-JS 就出现了，还是一样的收钱。

CSPS2019

正式开学之后就是无尽的模拟赛。虽然有些题目很难，但是很多时候排名在我们学校甚至联考范围里面都能排得很靠前，特别是最后安排的几场几乎场场提前 AK 离场，所以就有点飘了。我命的模拟题放在了很早的位置就考掉了，当时 D1T2 是我把 AGC015E 看错之后造的题目，当时觉得是比较简单的，但是结果是我们后面梯队里面就过了一两个人，D1T3 的很多部分分也是教练准备过的题目结果绝大部分人都没分，当时给把我气死了，果然人与人之间的难度简单还是不能一概而论，所以原来 D2T2 是个跟 NOI2015 寿司晚宴差不多的题，就换成了一道送分，于是就出现了 D1T2 过个位数 D2T2 过一片的迷惑情况。

zsy 造了一场模拟，当时我较早地就把题过了，然后把拍放在旁边，同时由于教练的特殊需求这场有五个题。然后 zsy 在巡视的时候就把这美妙的画面记录了下来。

最后几场里面 wch 和 winlere 的某场让我很有印象，因为当时 T1 是某 NOIP 题，很久以前还写的是贪心的线性做法，结果当时就只会树状数组做法了，真是越学越愚蠢。还有 T3 大概是可以处理之后高维前缀和，结果他们就赛时加大数据范围卡了，重点是加大了我就不会做了，然后就心态崩掉。当时就感觉自己对考试的心态不太对劲，但觉得应该也没啥，毕竟实力摆在这里。CSP 前一天晚上在 LOJ 写了一大堆 NOIP 的 T1，不知道在想什么。

当时因为班主任有给班上同学过生日的习惯，所以后来在训练期间统计了大家的生日，给好几个同学过了，说是过生日基本上就是唱唱生日歌，不过总比啥都没有好。

第一天由于密码的给出时间早过开考时间，于是我们就提早看到了题面，看到 T1 直接模拟，于是在开考前过了个题目。然后看 T2，dfs 的时候维护个栈似乎就可以了。很快地写完，大样例看也没看直接测就过了，觉得和 NOIP2018 一样稳可以 AK，就没写拍直接刚 T3 去了。T3 贪心字典序很显然，但是讨论了很久也不知道怎么去维护，看了看部分分菊花还是比较简单，但是没有想到把菊花的部分分进行拓展；链的部分分也想了一段时间还是不会，只好去写暴力。先把代码交上去，写了个 gen 测了一下发现菊花那儿数组没清空，顺手加了个 memset 然后忘提交了，于是只有 \(n \leq 10\) 的分数。最后发下来代码去牛客自测发现 T2 只有 35pts，当时就开始紧张了，调了好久好久才发现栈空的时候加个右括号就会出 Bug，噔噔咚。后来觉得不合理，大样例为啥能过啊，结果他们说大样例是 ()()()() 这样的一条链不会出 Bug 就彻底自闭了。绝大部分人都过了 T2，只有我 235->110，下午和晚上跟要死了一样，就差去上吊了（？）。

被 D1T2 弄傻了，所以第二天打得非常收敛，再不写拍我是狗。T1 看到限制条件，条件反射地容斥一发就是个背包，不过感觉 T1 是容斥题还是有些离谱。T2 DP 做法很显然，先写了 64pts 的平方算法，写完顺手写了个拍，想着应该有决策单调性之类的东西，准备有时间打下表。T3 一眼 \(O(n^2)\) 先写了，后面大概往换根 DP 上去想了想，然后想到跟希望差不多毒瘤的一个玩意，正准备写可回退化数组的时候发现复杂度假了，幸亏不是写完了才发现复杂度假了，当时时间不是很多就开始慌了，一时也没有什么更好的思路，就直接打了一场的暴力，顺便给所有部分分之间写了拍。为了写 T3 暴力花了很多时间就没给 T2 打表了。最后检查了下常数，T1 好像比较卡常？优化了下取模大概能进去了。出来看各位要么 T2 88 要么切 T3，T2 果然打表就找到规律了，亏死。下午往牛客丢没有挂分，100+64+75。

总分 100+0+10+100+64+75=349，HN Rk30+，当时想着要是真的这个分数就要准备后事了，那两天大家都在改 CSP 的题目，只有我一看到 CSP 题目就趴桌上哭只好先去做 JOISC，这就是 ptsd 吗。这之后后面一批的学生就都回去搞学科了，前面一批的则仍然留在机房里，我也准备成绩出来再决定去留。

过几天 CDQZ 邀请我们和 ZHZX、ASDFZ 去他们那儿集训，我自然是跑过去了。期间 gcz 跟我说 D1T2 出题人表示大数据造了特殊性质，我的代码刚好不会出 bug，稍微让我的情绪好一点了。CDQZ 集训期间很神奇，好几场被虐场，还有好几场虐场，rushcheyo 和 dxy 的题直接把我弄自闭了。同时还有一些讲课的东西。我们也是从 O 那儿那个时候第一次接触到拟阵交、超现实数这类很高级的知识。CDQZ 九点半下晚自习是真幸福啊，下完晚自习就跑回酒店和 iotang 搞颓，我打 Cytus，他打万象物语和 Polytone。说起万象物语我在某次讲课的时候看到妹神在桌子底下打开了这玩意，抓摆现场（雾）。集训完那天下午还没有放学，于是大部分人就在 CDQZ 机房里 SuperTuxKart。

CDQZ 集训完了之后 CSPS 成绩出了，D1T2 真如之前所说后十个大点都满足不弹空的特殊性质，所以变成 60 分了，其他分数没有变，总共 100+60+10+100+64+75=409。感谢 D1T2 出题人的给了我继续 OI 的机会，如果 D1T2 小于等于 10 分的话就不知道还会不会在竞赛组了。某位我校初中附属学校的学弟不知道想什么扣了个 HN 省队名额，结果某中学教师直接给 CCF 提建议变成了扣除名额定向到集团，我谢谢您嘞，所以教练就让 gzy 直接放弃资格留给我们这些没进过省队的。

正式赛还是要保持谨慎，平常模拟赛倒是好好写拍，到 CSPS 就开始瞎搞了……不要贪切题，打好暴力、蹭一些特殊性质，拿稳分数才是重中之重。

THUWC2020

后来再和合作的学校来了几次冬令营联考，网络流题突然变多，大概是因为 NOI2019 D1T3 是个模拟费用流，还有不少有趣的题目。开赛前一天到了西郊宾馆，西直门超长换乘通道再放送。和 winlere 住一间，晚上看了看 OI-wiki。为什么密码条上账号是 THUWC2020_46 但狗牌上写的是清华大学 2019 年冬季体验营？

第一天进去定睛一看，T1 想了想维护一下每一个状态之后变成谁就行了。最开始直接 20 个 set 暴力搞，TLE70，但令人害怕的是我可以看到 system test 的分数。然后倒着搞变成在单调栈上二分就快多了，看到 Accepted 之后就拿着暴力拍了若干组就没管了。再看了看 T2 ，感觉正解是 LCT 维护基环树之类的东西？不可做先跑路。T3 是一个数连通块题感觉可做，盲猜了个 bfs 序结论，交了个暴力，此时就看不到 system test 的分数了，过了 4 分 Pretest，这也太不友好了吧。拿常用的 Trick 套一套，上一个点分治之后可以先三维偏序预处理出 \(n\) 个点的信息，每次再二维数点算答案，复杂度 \(O(n \log^3 n)\) 怕不是 \(10^5\) 都过不去，还极其难写，要死。然后看了部分分，\(X \leq 4\) 可以 \(O(X^2n \log n)\) 预处理，\(X \geq 299900\) 可以 \(O((n−X)n \log n)\) 预处理，链可以少两个偏序变成 \(O(n\log n)\) 预处理，然后就码了一大片部分分码到 68 跑回去再看 T2，最后还是无法理解 \(X=299900\) 有 16 分而其他只有 4 分或 8 分。先写了个 T2 暴力，期望一条边的 sub3 都不能过就离谱。然后准备把不删边和树的情况写了，最后三分钟才 debug 出树剖有个地方少减了东西，过于刺激心脏病要犯了。pp 100+41+68=209，似乎是个不错的分数。

第二天 T1 \(n \leq 15\) 和允许 __int128 让我感受到事情不太对劲。写了个只维护最大最小值的状压 DP，过了 Subtask 2,3,4 却没过 Subtask 1，感觉这个 Pretest 并不简单。后面发现有可能最小值在 \(0\) 处取到，就要维护最靠近 \(0\) 的值，就要维护最靠近零点的值，就要维护最靠近零点的零点的值……然后作死写了个暴力用 vector 把所有状态存了下来，状态太多把电脑内存卡爆了，于是换了台机器还获得了 5min 加时，拖延时间的好方法同学们学废了嘛？（bushi）拿暴力拍了拍，只维护最大最小值 Subtask 2,3 是可以过的？拼了个暴力 55 分赶紧看后面的题目。T2 先找一下每个点经过返祖边能够到达的最浅的点，再从子树线段树合并求一下子树最浅深度，询问离线下来就行了？看起来很对，写着写着发现边不一定是返祖边，也可以从别的杈往上跳。写了个倍增拼上后又发现可以一次跳很多条返祖边，就拼了个拓扑排序，总算是算对了。T3 题目名序排泡冒有点东西。先观察了下答案，check 合法显然，方案数似乎就是把最大 \(k\) 个删掉之后得到的序列的前缀最大值中每一个会贡献 \(k+1\) 的系数。写了个暴力过了 13pts。当时想的做法是先倍增求一下路径，再点分治单调栈二分求系数，看着就很难写还只能过 \(10^5\)，瞬间不想写。发现链的只要把点分治换成序列分治就行了，倍增还不要判边界，分数还和点分的分数一样，二话不说开始写，调到最后五分钟终于把边界抠对了。pp 100+100+48=248，不过 T1 多半会少 45。出场发现有些选手把 T2 看成了支配树之类的东西还没有过，感觉比较稳。

工程场内容是 Cache 实现。T1 为什么在放在学习手册最后还跟后面的题目没有任何关系？幸亏先翻了一遍题目要不然就被前面的内容拖了。半小时写完模拟题 T1，T2 要模拟 7 个 Cache 读丢失策略，写 7 个还是有点离谱。不过有些名词和实现在 APIO2019 讲硬件优化的时候就有所了解了，还有好几个本质是一样的就换下优先级就行了，所以写起来还是相对顺手的。写完之后还剩 1.75h。T3 需要实现只读 Cache，因为之前的七个策略是用 namespace 套起来的，这里又要开每种策略对应的若干个 Cache，调整起来还是很麻烦。试了 struct 套 namespace、class 套 namespace、struct 套 class、class 套 class 全部 CE，只能单独写了个 Cache 的通用 struct 然后把七个 namespace 改成 struct 再继承。大概花了 25min 调这个东西，后面就在做交互库适配和理解它给的内存地址的实际含义，做完之后剩 45min。T4 是读写 Cache，幸亏封装得好，很多部分只需要小改，在父 struct 里面只需要加上 write 相关的函数就行了，然后在 FIFO 里 write_allocate 的时候忘把指针 +1 了，调了 1w 年。调完交上去期待着 AC，结果是 Subtask 1,2,3,4 AC，而前四个 Subtask 的并 Subtask 5 WA 掉了。当时就懵逼了，最后十分钟也没找出什么错。pp 192，似乎很多选手只写了 T1T2，大概 100 分左右，又赚翻了。

显然进了面试。这一次备考室没有禁用电子设备，不阻止去上厕所，甚至连身份证都没有查，相比 SC 管得不是一点半点的松。坐在备考室的时候偷瞄了前一排的人，发现我前面正好坐着 ouuan 和 xht37，就在 QQ 上调戏了下 xht（雾）。面试官比较和气，数学题先是把长度为七的金条分成三份这样的经典问题，后来我觉得就这就让他们换了道题，好家伙换成了高中数学的组合计数，那我也不好再去换题了。英语阅读有些难，不过瞎 jb 拼，然后再用关键词猜猜意思也就没有踩什么雷，幸亏没让我用英文回答奇奇怪怪的问题要不然怕不是要挂了。下午发奖，全 员 一 等，P 那边似乎也是这样子，所以考好了点就开始拉低标准了么，体现不出这次发挥的水平了（？）。

HNOI2020

THUWC 之后，学校里再进行了几次冬令营模拟，叉姐也来给我们讲了两次课，先讲了讲字符串科技，Compacted SAM 的内容和 cz_xuyixuan 2020 年论文高度一致，Lyndon 和 runs 相关的理论听懂了不少。后来就是一些神奇题目选讲。其中例题就有 Gnutella Chessmaster，我的论文里面的例题，也是我第一次了解到下降幂棋盘多项式分解定理这种东西。大概过年前几天学校就要静校了，因为保安要回家过年，当时班上还安排着要在外面找地方自习，OI 组还是比较特别因为要找电脑，不过放假前几天突然学校里开始爆发流感，高一的第一梯队当时好几个甲流乙流，为了安全起见还是把计划撤消了。

后来发生了什么大家也知道了，疫情爆发导致我们好几个月都只能待在家里集训，冬令营也无限延期。不过二月出现的 JOISC 同步赛很好地填补了疫情初期的一些空白。具体的细节也有很多记不清了，大概过了 D1T1/D2T2/D3T1/D3T2/D4T1，D2T3 有一个部分分做法但是细节死活想不清楚就鸽了，D3T3 也基本想到了 94pts 就是哪儿脑子抽了没想清楚，D4T2 加个随机化跑一跑也有很高分数，但是就是只写了个贪心匹配，总之各种自闭。

后来就是从二月初到六月中的疯狂联考。最开始我们校内在腾讯会议上交流题目，有一次 CDQZ 的考试的某计数题看题解看不懂于是就出现了我在会议里面通过 winlere 和妹神在 QQ 上聊天问问题的魔幻情况。后来我们跟教练说了之后，联考考试题目就有了视频讲题，后来还有若干学长和选手讲课的环节。印象深刻的是 yjz 先是讲了万能欧几里得，后面还讲了完全动态图连通性。同时还讲了好多好多的题目，所以那段时间完全没有题目荒。板刷掉 JOISC 之后还感觉自己的脑子进行了升级。自从三月的某次模拟赛线段树分治模板题不会做之后，开始深刻地反省自己知识点基础运用上的疏漏，于是创建了个 LaTeX 开始记录自己做题时遇到的各种经典的或有意思的结论和知识运用以及各种傻掉的地方和细节坑点，顺便做了个 OI 知识列表，这样翻出来看看还是可以避免很多因为知识点接触太少导致的突然忘掉的 bug，题目不会做的时候还可以拿知识点一个个套。

由于 iotang 把 lemonlime 的通信题功能造好了，我和 iotang 便往联考丢了到 JOISC 的通信题，同时 xzq 问的一个之前联考的问题被我拓展出来拉到了联考里面，标算写的分块 FFT，结果大家人均会实现这类特殊的分治 FFT，于是被踩标了 TAT。iotang 则往联考里丢了他之前在三国联训里就准备出的跟 AT678 类似的图像识别题，我当时验了大概一周的样子手动人工智能分析数字特性做了八十多分还要 iotang 多次削弱数据，结果有选手直接搬库拿了接近满分我直接好家伙。

学校复学之后大家终于又能聚到一个机房集训，不过每天要拿 84 给机房消三次毒，每个人都戴着口罩感觉距离一下被拉得好远。最后 gzy 给了一些题目留作梳理练习，确实在不少知识点上点了多一些技能点，同时还跟一个新的联考组合进行了几次联考。省选前最有趣的事情莫过于给 CCF 捐款报名省选，由于有捐款证书，某些家长突发奇想可以把这玩意上传到高中综合素质评价里去。

因为 CSP 的大劣势，自己无论在家里还是在机房里都相当拼命而专心地搞 OI，不自禁感到时间如白驹过隙，一下就来到了省选赛场。

第一天，T1 icefire 看了看题，要求两边总和的 min 那显然可以二分，有加入撤销那显然可以拉个线段树二分，再看了看数据范围……\(Q\) \(2 \times 10^6\) 你认真的吗？虽然知道机子是 8700K 的少爷机但写线段树还是感觉相当作死啊，于是写了个树状数组上二分，然后调了半小时左右才过大样例，上了拍。T2 把 \(f(k)\) 换成 \(k^i\) 再熟练地拆一下下降幂推一推就会做，感觉做过这类题目的应该都比较熟练吧，不太懂这道题的筛选意义，然后写了个拍。T3 线性无关最小权最大权子集是个拟阵最优化问题可以贪心，那么就只有大小关系了，所以就是要求给定大小关系后最优化结果函数的问题，函数还是个二次函数，woc 保序回归，感到脊背一凉。不过去年省选的时候 gxy 出过模板，还记得做法是整体二分加上最小鸽，大概是要么选 \(mid\) 要么选 \(mid+1\) 保持原来的大小关系然后分治，于是就开始想代价是多少，错了好几次之后终于算对代价了，过了大样例，感觉浑身清爽，补了个拍。最后还剩半个小时给 T1 卡了卡常数。出场发现好像我校只有我和 gcz 过了 T3，旁边还有好几个 T1 写线段树的老哥，是不怕死吗？虽然最后好像写线段树也过了，少爷机还是你少爷机。

第二天，T1 \(m \leq 23\) 还有 \(21\) 和 \(22\) 的部分分铁定是状压 DP 了，做法也比较显然，一个个选过去就行了，当时还愣神说为啥 \(O(2^mm)\) 开 \(m=23\)，后来发现 \(O(1)\) 预处理转移贡献要开 \(2^mm\) 的数组时才意识到这是一道卡空间题，不过由于贡献只和集合里的每个元素相关，所以劈成两个 \(2^{12}m\) 的数组就可以了，上了拍。T2 看了看如果要维护子树结果的话，似乎要进行全局 +1 求异或和的操作，这考前刚遇见过，Trie 树从低位往高位插入就行了，再加上个 Trie 树合并美滋滋通过，写了个平方暴力上拍。T3 先反演掉 gcd 变成算权值，生成树权值用 matrix tree，但是好像算每个边权的贡献都要重跑一次，似乎要 \(O(n^3md(w))\) 不太能过的样子？但当时也不会生成函数和转乘积的 Trick 只好硬着头皮写，加了几个求行列式上的优化，比如先求一次行列式把消掉前若干行之后的结果记录下来，如果修改某个位置就可以直接从最高的被修改过的行开始消，优化了一波常数，不过本地测了测极限还是要 4s 左右，不管了上了个指数级暴力的拍。出场发现 gcz AK 了 orz，好像大家都会生成函数和转乘积我又自闭了。

期望 100+100+100+100+100+50=550，实际 100+100+100+100+80+100=580，出成绩的时候发现有个 80 觉得是 D2T3 没过问题不大，后来再看了一眼发现是 D2T2 80pts。去代码里看了看结果发现自己 Trie 只插了 20 位，而 \(525010>2^{19}\) 于是链的部分分就挂了。不得不说 CCF 的评测机还是优秀，不过 D2T3 这玩意确实常数挺小，时限也很大，不太好卡掉。

似乎除了我和 gcz 以外 HN 没有人过 D1T3？lk 和 xzz 都是 D1T3 60pts，huhao 则不知道挂哪儿了，我校其他选手也是有比较大程度的发挥失误。于是凭借着巨大的省选优势我冲到了 HN-004，gcz 和 xzz 则是交换了位置，lk 再考差点 CJ 就前三了。最后 dsl 买了 C，因为 ych 已经有了 NOI2019 的 D 所以他也就没买了，留给了 winlere 和 czf。到这里，我们组里就剩下了六位 NOI 的选手，还有为了 CTS 准备的 zsy 和 gzy。

WC2020

在省选之后，CCF 终于把被世人遗忘的南半球 WC 办了。退费还收 30% 就离谱，真就恰钱恰到没有原则呗。因为有几天要打多校所以把几堂课咕了，比如 laofu 的课。据说 laofu 原来是不准备来的，后来是因为 CCF 约定如果 laofu 来讲课，申请 C 就能过，于是把 laofu 拉去了。杂题选讲还是有收获，一些理论向的东西还是不那么容易吸收。虽然没去过线下 WC，但终究线上 WC 还是没有线下面基那味了，只有 of the money, by the money, for the money 和改掉 CCF 图标这种有点新意。还有比较有意思的部分是营员交流，xyx 的任意匹配因为有看 noi.ac 所以写过，只不过当时写的是一个 Dijkstra 维护 KM 增广树的鬼畜做法，常数也挺大，不如 xyx 给出的做法优秀；yhx 展现了新人类念 PPT 速度极限；panole 直接把 nmd，也就是我们 THUPC 队名那场毒瘤联考的 T1 拿出来讲了，现在看起来网格图挖点哈密顿路这种东西还是毒瘤。

然后就是冬令营测试。先看了看题目，看起来 T3 就非常的可做，没限制的时候就把每种学分拿出来凸函数 min 卷积一下，有限制的时候限制很少那么枚举一下就行了，但看了看条件，\(12\) 个限制岂不是要枚举 \(2^{24}\) 种情况，人傻了，于是写了个暴力。再看了看 T2，这题目是真的难看懂，不过看懂之后还好，好像特殊处理下 gcd 不是一的情况之后只要算个阶就行了？数据范围小到随便暴力，感觉这种题目难度有失水准啊，写完上了个拍。T1 很快地抽象了做法，但是好像不是特别会一个 \(\log\)？大概可以用 simple tree 那个分块做到根号，但是好像不太好写，所以最后还是去写暴力了。最后应该是 45+100+40=185，非集训队 rk 14。T3 最后数据锅了，真正的条件是条件涉及到的点数 \(\leq 12\)，那不是随便做？导致只有写退火的 skip 过了。T1 还是很厉害的 DS 题，给 myy 点赞。后来似乎是 gzy 跟我说实际上 T3 原问题可以一个个加被限制的元素然后只状压和没加入的有关系的元素，这样就可以 \(2^{12}\) 了，有点类似插头 DP，果然我还是不行 QAQ。

NOI2020/CTS2020

基本的训练内容就是联考+多校，多校确实有几场有不少有意思的题目。有一次 HSEFZ 往联考里面搬了个 IMO 的构造题场上过了十几个。著名的“简单的普及组计数”也是这时候的产物，考完这场因为要讲题但看不懂这题题解，似乎是拉格朗日反演之前 GF 的推导跳步严重，我和 gcz 就去 QQ 上缠着 djq 问，结果问着问着 djq 似乎表示自己也搞不清楚了，反正最后这个题不了了之。然而到退役前我都不知道拉格朗日反演是啥玩意（

我自己组的 NOI 模拟赛 T1 是之前看了 dreamoon 的从枚举到 k 短路 之后有感而发自己造的一个二分搜索题目，大概是给了一大堆条件的图上 k 短路查询，不过最后好几个人用最短路套上主席树的大工程做法过掉了；T2 则是喜闻乐见的棋盘多项式，收录在我的论文的禁区排列问题部分，不过还是有不少人是拿着矩阵快速幂优化 FFT DP 过的；T3 则是 Gym 里搬的一道 SAM 套 LCT 的题目，似乎 Isonan 之前做过所以就他一个过了，gcz 表示暴力给了 50pts 谁去写正解……

然后就是 NOI。在长沙办终究是好的，半个多小时就到了一中新华都，自然是我和 xzz、gcz 住一间。要是新华都的日常伙食和 NOI 时候一样好的话，我就要开始怀疑为啥我当初选双语了(doge)。笔试没啥好说的，试机题里有交互，还开 -std=c++11，总算是跟进了一点时代。面基到了兔，准确来说是兔来面基我。

第一天看了看题，T1 没有美食节就矩阵快速幂一下，有美食节就把那几个时间拿出来特殊处理，再用向量乘矩阵的平方做法压复杂度就成了，比较简单，写了个拍。T2 题目真长，似乎可以记录下子树里面所有链延伸到的祖先平方 DP，但怎么优化呢……先想了想常数优化，如果链数很少的话似乎状态也很少，那么可以只维护这些状态，拿个线段树合并之类的优化一下……估了下复杂度发现这样非常正确，和平方写了个拍，还剩 3h。然后就又开始过两题后传统艺能疯狂刚 T3，不过看了看题目严格强于区间逆序对还是相当危。四维莫队很快就想到了，容斥了两下也有了个三维莫队，但是当时太贪了疯狂想分块想不出来，于是只剩一个多小时的时候开始码暴力，感觉三维莫队算的东西太多码不出来于是就开始写特殊性质。A 的分块写了好久好久才写完，B 感觉就是很无聊的 part，构树结构不太好写就跳过了，C 还比较简单。出成绩时发现 C 数组开小了于是愉快 GG，好多人写了暴力把 B 过了，无语。最后分数 100+100+40，晚上讲题的时候发现三维莫队有八十来分，四维莫队也能蹭到好些分数，亏爆了。

第二天还是正序开题，T1 先想了想 \(m \geq n-1\) 发现咋样都合法，再看了看 \(m=n-2\)，如果把一道菜看成一条边的话大概会有两个连通块，所以大力猜了一波划分成两个集合分别合法，看起来就很对。再想了想如何 bitset DP 的时候还原方案，似乎再倒着选一遍就是了，写了个非常弱的拍。这个 T2 题面咋还是这么 long long 啊看得头疼，不过确实把该交代的内容全交代得很清楚，非常好评，不过只有最开始以为有一个儿子的点可以再长一个儿子。然后直接开始莽 100 分，如果是树判定的话可以考虑递归，只有一边有儿子的情况好办，两边都有的咋办呢？然后就开始大力分析，然后忽然灵光一现，发现左子树和右子树分别都要是完全完备的，那就好办了，把左子树是一个点的和右子树是一个点的树的另一边子树拿出来递归判定就行了。把所有大样例都过掉的瞬间感觉针不戳，不知道怎么拍于是没写拍。T3 弦图题保持警惕，但又开始贪，之前学了个叫 clique tree 的弦图上数据结构，丢上去讨论讨论，于是讨论了 1w 年还没讨论出啥东西，最后只有时间写暴力，特殊性质 A 就是最短路，B 感觉是 DP 但写不完了，于是只写了 A 的暴力。过了一段时间大家都回宿舍的时候，gcz 因为没过 T2 并且似乎从 U 群得到形如“T2 过了半场”的言论，原话应该是 zx 在群里说他问了十个人里面 T2 过了六个人，就以为进不了队狂暴状态了好一会儿。下午的时候看成绩鸽了好久好久，在外面溜达的时候又碰见了 xht，他终于见到我真人了（雾）。没有挂分，也没有什么挂分点，100+100+20，后来讲题发现 D2T2 才过二十来个。当时我们三个一致认为集训队线应该在 490 到 500 左右，结果出成绩的时候，好家伙队线 450 都没有，xzz 和 gcz 都是二十名左右，我则莫名其妙进了前十，dsl 拿了 Ag。NOI2020 就这！（雾）

第三天是六选四论文答辩。顺了几本论文，问了下后面的录像老师说官方录像不会外传，就只好我坐在靠前的位置拿着手机录，录到手机疯狂发热。142857 还是和之前营员交流时一样有点结巴，yhx 继续机关枪，印象比较深刻的有趣问题大概只有对 zrf 的“你们教练口音这么重你是怎么说好标准普通话的？”和对 yhx 的“你和 lyx 里面只能选一个你觉得应该选谁？”。最后国家队成员还是前四 zyy、142857、lyx 和 wzp。看着 yhx、myh 和 wzp 捧杯的时候想着如果两天 T3 不去贪正解的话我大概也杯了，还是被 AK 迷失了双眼。

佛系养生——高三

暑假

到暑假就开始了集训队的集训了。暑假里科学馆装修，于是我们带着电脑一起搬到教师之家挑了个小办公室集训。先做的事情是把近几年的轮文给看了一遍，没有高数基础所以圆上面积并看不懂，nimber 从 nim 积开始就不懂了，网格图构造题就是毒瘤，还有前几年 LCA 的 DFT 论文也是基本懵逼看完，其他的基本上都看完了，杨表和 Dyck 路还是很有意思，我永远喜欢组合计数！很多论文看起来确实难受，写小水题就更加难受了，不过通读过之后还是点了不少高级技能点。

然后就是把 laofu 和 ymd 当时的训练题丢出来给我们考，然后发现了 ymd 论文题和模拟费用流以及一些远离时代的题目。可能是我们教练也有可能是 laofu 曾经跟我们说 ymd 论文的灵感就来自于这个题，解方程可以算期望但是很难算方差，但是 laofu 直接上了 pgf 锤过，于是 ymd 学了一遍 pgf 写了论文。由于只有我还有不少去年集训队作业没动，于是与此同时开做去年集训队作业，里面的题目质量真是很高。

百度之星 2020 决赛

先于 CSP 的是百度之星的决赛，进了前四十想着能报销不去白不去，xzz 在后四十不过也氪金去了。在酒店和百度科技园之间穿梭的大巴上经常会听到身边诸如 zyy、panole、zx、myh、lyx 之类的人在讨论各种各样的东西，我就在旁边瑟瑟发抖。在酒店里我有时写写作业，有时打打雀，xzz 则在旁边 dark souls。

考试那天旁边摆了一大堆零食和饮料，我大概随便蹭了点东西，不过看起来好像有人就是奔着蹭吃蹭喝去的(doge)。题目内容是量子计算，学习手册看了好一会儿才有比较好的印象，上午就是一些量子计算的基础实现比较简单，写完之后封装了一下。下午 T1 还是正常题目，后面两个题目就开始 challenge 起来了，完全不懂乱搞的我就在那里乱随，看到榜前面都是 200+ 选手自己的 T2 还是两位数心态就差不多崩掉了，就开始各种调整刷分，结果还是没上三位数，到最后就开始欣赏刷榜，自闭到爆炸。大概四十多名的样子。后面听了听 EI、yzr 等的分享感觉我就是个巨大多 sb，AFO 算了。

后来参观百度也没有很多好玩的，智能车有点意思，在智能家居体验那里似乎是 xtq 喊了句“小度小度，恢复出厂设置”给我笑 yue 了（Fix001：小可爱 lk 表示是他喊的，我确实也记不太清楚了）。后来百度宣讲那里发现大家都围着量子计算研究所那儿，就去旁听学习了一下。闭幕式的时候坐在后面和 myh 和 zx 聊天，然后抱了两个熊回去。下午不知道怎么地把狗牌弄掉了。晚上的团建最开始以为很尬，但后来大家都进入状态之后就好多了。最后面基了 yzr，问了问他往模拟赛里丢的题目数据怎么造的，因为他往 CSP 模拟丢的题目我正准备往 CTT 模拟里面丢。

回来的火车上在写作业，xzz 最开始在 dead cell，后来也来写作业了。

CSPS2020

我们的学弟学妹们在准备 CSP 的时候我们一直在准备 CTT，所以最开始两边的考试是分开的，后来我们教练发现杭二的题目实在是钛毒瘤辣于是叫我们也去考下，顺便给他们讲讲题目，于是就跟着考了几场，确实有好几道题目挺难的，还是 ZJ 选手水平高。

然后就是 CCF 的广撒网摇钱树 CSPS，进考场的时候发现身边是 huhao，瑟瑟发抖，而且似乎因为开考之前好几天都在划水，所以状态极差。T1 模拟题，最开始还想把关键位置弄出来的，后来想想还是用程序把有特殊情况的日期先弄出来，再用循环节算年，这样特殊情况少一大片，很快就写完了；T2 sb 题一下就过了，灵敏地察觉到了数据范围的 \(64\) 于是加了特判；T3 先看了看感觉不会做？多想了一会儿，在 DAG 上 DP 两次算一下贡献好像就行了；T4 先用个双队列把一直做不停的情况弄出来之后再反向决策一下好像就行了，很快写完，再写了个暴力上了个很弱的拍。出场的时候发现好多人 T1 写了好久？虽然我不太喜欢模拟题但是筛选一些代码思维比较好的人出来也未尝不可。之后 EI 似乎说直接双向队列是有锅的，想了想确实在 id 的排序上有一些问题。最后分数 100+100+100+50，这个 T4 分数还没有用堆写高，亏死。xzz 和 gcz 都挂了些莫名其妙的地方。

小米 ICPC 邀请赛 2020

CSP 之后 duls 不知道在哪个群要 xzz 去验小米决赛的题，于是拉着我们一起去了。为了在三机上模拟一机我们当时写题就要喊一句“我要写 xxx 了”然后再开始动。

先开场把数据结构 B 过了，然后他们俩一个开出了 G 一个开出了 K。后来 xzz 开 M 觉得很可乱搞于是开始码，gcz 开 I，我去开了 L，发现按照编号顺序搞一搞可以 DP，状态数似乎不多，于是抢了 xzz 的机开始写，1h 过了。然后我再开了 H，推了推每个点权值一定是相邻两三个的平均值，然后单组询问可以树上高斯消元。而且根节点权值是所有叶节点的平均值也是可以推出的。再然后一次修改只会涉及到树上 \(\log\) 个祖先的修改，那么其他部分的子树如何处理，似乎对每个节点维护它的值与子树贡献的二次函数就行了，修改看起来也很方便，于是又抢掉 xzz 机子开始码，2h 时过了。当时 jiry 和 duls 看起来很兴奋的样子，都在那儿奶过 10 题，还在那儿喊 A 和 F。xzz 又改了好几次乱搞水过了 M，期间 gcz 好像把 I 的 DP 推出来了，但不太好写的样子，我跑过去给它改了改，虽然只要 set 了但还是很难写。然后 gcz 把 E 推给了我说看起来讨论两下就行了，然后推了推，幸亏想到了 a*10+(0~9),a 这类特殊情况，然后推了一会儿过掉了。中间 gcz 疯狂写 I 调不出，后来和暴力拍也拍不出了，自闭。看 C 也不会，D 也不会辅助序列只会三个 \(\log\)，结果三个 \(\log\) 能过直接亏死，J xzz 说是物理题于是错失签到。第二天拍了拍 I 才发现标算假了（）然后把数据范围调成了 \(a_i \leq T\) 两个算法就是一样的了，据 duls 赛时跟踪发现 dmy 当时只会 \(a_i \leq T\) 于是把他们送到了 9 题。最后过 8 题，和 jly 一个人五五开，什么时候才能有 jly 的实力啊 555，不过如果在正式赛的话应该能跟榜过 J，这样就和 dmy 队五五开了（确信）。有意思的是 jly 和 300iq 验题的时候都过了我们没过的 jiry 的中档题 C 和 D，而我们过了 jly 和 300iq 都没过的 duls 的中档题 H 和 L。

CTT2020

十月份开始联训也开始了，作业也发下来了，论文也读完了，然后就开始疯狂地每天写作业。今年作业相比去年质量低了不止一点半点，一堆模拟题和好几道细节极其毒瘤的计算几何，古老的 WF 题目找不到题解于是 WF2014 J 完全不会证明复杂度。不过里面确实有不少有趣的题目，比如第一次遇见了最小树形图的应用，还有五子棋题之类的有趣问题。自选题选了一直以来很喜欢以前也出过的棋盘多项式题，当时只准备把 OEIS 上的做法写在题解里面而以前自己递推出来的做法不写，后来妹神的写法好像不太一样跟他交流了下发现之前的递推做法有简洁一些的推法，于是还是加上去了。百度之星闭幕式的时候偶然地站在 EI 身后发现他正在看我的自选题，我直接瑟瑟发抖。

然后就是联测，因为 CTT 是 IOI 赛制，所以联测丢到 NFLSOJ 上了。我还是发扬了传统，丢了道 IOI2010 的通信题，但我不会在 UOJ 系统上通信，于是缠着 wzy 学了一天终于搞定了，于是在学校内部的 UOJ 上加了个 A+B+C。后来测试的时候发现评测应该不是把三个程序绑在一起编译，这样可以某个文件是空的另一个文件实现两个函数，正确的做法应该是分别编译运行。lemonlime 好像是绑起来编译的，但是联考里大家都素养很高没有作弊，为大家点赞。赛时发现数据范围可以暴力草过于是直接赛时该数据，然后比赛被 down 爆了 TAT。

在我们去北京的飞机的前一天是复生了的 NOIP2020，但是 NOIP 前一天作死半裸睡于是感冒了，还是怕耽搁 CTT 行程，于是到了考场外面之后就又打道回府了。上午补了一觉之后还是发烧，于是下午去医院看了看，幸好前几天做了核酸检测所以预检分诊进度很快，不过因为同时还有些心悸所以去急诊科看，然后在急诊科看到了一些不好的事情，不过这个和 OI 关系不大，留到后面再说。NOIP 题目质量确实不错，字符串和构造题第一次在联赛亮相，不过后面一届还有小朋友没拿 1= 是咋回事，SPJ 题将每个点输入改成样例输入能过又是怎么回事。

CTT。去北京的飞机做到大兴然后做了两个多小时出租车直接自闭。北大食堂还可以，酒店还不戳，和 hzk 住一起发现他在卷线代。Day 1 前一天晚上看了看自己的 LaTeX 笔记，顺便和 hzk 聊了聊。

第一天先看了三个题，T2 是比较传统的 DS 先开了。用 dfs 序实现区间 LCA 之后问题变成了单区间在前面加一个点后问答案。先上了一个二区间分治然后左右可以分别用前缀答案和单调栈维护。一个小时过了。T1 是一个 k 进制线性基。反应了一下 m=1 的部分分，可以裴蜀定理，感觉直接拓展到高维上就开写了，不过高维线性基有可能出现一个数更新线性基上多位的情况，就是在当前插入的层直接用当前层互相加然后把当前位加到 0 的情况。最开始没怎么想好怎么处理就先想了会儿 T3 把暴力分拿了，最后想了一想这种情况因为可以任意加所以只需要把倍数最小的情况往下传就可以了，复杂度也是对的。写完就到 11 点了。然后一直想 T3 的 sub1 没想出来，最后几分钟就在趴着自闭睡觉 Zzz。100+100+10，Rank 7。讲题发现 T3 sub1 完全 sb 掉了，主要问题是没有想怎么一步找集合内父亲，而且也没有特别想清楚剥叶子的细节，sub2 没听懂 TAT。宽宽好像把 T2 看成了不可做题于是没签上到，默哀。

第二天 T1 猜了一下从大到小放尽可能让大的贡献更大的思路，稍微判了一下特殊情况，上个主席树就过了。T3 想着用度数序列处理出缩点结果和所有反转之后改变答案的边然后讨论。最开始以为这些特殊边反转之后答案只会 +1 但实际上拍了一下才发现有可能出现其他情况，于是开始了对图结构的大力讨论，最后在大量对拍中搞定了。实际上 T3 直接用度数序列算答案会方便很多，还是我 naive。T2 是积分题所以不太敢动，把 n=2 的部分分拿到之后就不会了，败了败了。100+5+100，Rank 11。讲题鸽了。T2 想到了转切比雪夫，但没看出来转换之后是经典问题，而且这个经典问题之前也都是拿指数级做法过的，亏死。

第三天 T1 看到排列和逆序对想到了行列式，然后就想到了用行列式算偶数减奇数的答案，偶数加奇数就是全集大小然后就做完了。T2 想了一会儿转化了结论。之后先写了个 KDT 但写完发现跑得比暴力还慢，KDT 一生黑。然后卡了卡暴力发现也进不去，想了一个 \(O(n \sqrt{n} \log n)\) 的分块做法但这复杂度也不太敢写。当时时间不是很多了，所以先把 T3 20 分暴力解决。然后尝试写 T2 分块，调正确之后把线段树的建立和拍标记改成了非递归形式之后 3900 ms 压线通过。最后给 T3 的时间不是很多肝不了正解，所以尝试写了下 40 分，还是没有调出来。100+100+20，Rank 6。讲题时才发现 T2 只需要维护有没有 1 就行了不需要拉个线段树做，zyy 表示 bitset 做法锤爆了分块。T3 果然是 lxl 的 lct 大模拟，zx 似乎专门肝这题肝了接近一场才过，不过 zyy 表示这已经是能够放的题里面最清新的了，还有两个候选是 lyx 论文题和比这更难写的 lct……

第四天 T1 看到数据范围先愣了一下，22 感觉不能 \(2^nn^2\)，然后发现 \(s,t\) 两个点是没用的。感觉是集合幂级数 exp 但不是太好写所以先写了个暴力，确认正确性之后补了 exp 通过。T2 矩阵树之后就是一个循环矩阵行列式，想了很久准备用各种方法实现但都不太行，最后想到了这是一个循环卷积的线性变换所以想到了乘范德蒙德矩阵，但是当时只有 80min 同时 T3 类似提答就开始慌了，推都没推就去写 T3。最后 T3 前两个 sub 用鸽巢原理容易解决，sub 3 乱构造一通，sub 4 和后面的部分就没想出来了。100+60+25，Rank 21。讲题也鸽了，后来看题解实际上乘范德蒙德矩阵就是正解，还是不太自信所以不敢继续做了，亏了个国家队。

不得不说这个 CTT 每天一道 NOIP 难度签到题就离谱。最终剔除掉非集训队的神童 djq 排在第八，xzz 和 gcz 还是二十几名的样子。

THUPC2021 初赛

（差不多忘光了）

THUPC 2020 变成了线上的初赛，很离谱。先是取队名的事情，发现我们完全不会取队名，xzz 不知道从哪儿听说网站对用户名长度的限制只在网页前端存在于是开始魔改 js 代码尝试突破这个限制，后来发现登录也会判断用户名长度，于是自闭，望着“用户名长度应大于等于 3 且小于等于 20”我们陷入了沉思，于是直接把它拉过来当了队名（

CTT 结束后一天就是 THUPC。开场我还是与去年一样先开 J 发现事签到，于是把 J 一血抢了，xzz 把 G 的一血抢了，gcz 过了永远的签到题 M。后来看 B 发现不是很容易做诶，然后就跳了过去，后来 xzz 过了。然后他们俩就一边看 D 一边看 L 一直在自闭，只剩我在疯狂签到……先过了签到的 E，再好好想了想 F，构造方式有点意思；然后就开始看 K，最开始猜了下没有环或者只有一个环，后来随了随好像假了，于是开始想 bfs 删叶子，如果删不了叶子就暴力枚举状态把所有状态都存下来，但就是不知道哪里写错了疯狂 WA，调不动了之后把简单的 A 和 H 过了，A 比较毒瘤的是把最重要的数据范围放在了最后；最后还是调不出来 K，直接删掉改成 dfs 枚环边，没调几下就过了，果然老年选手没有智商没有码量。写完 K 还剩半个多小时，也没啥输出了。过 9 题，Rk10，建议煞掉两个演员。有多个一血就送多本《深入理解计算机》是什么鬼？

CTS2021/WC2021

CTT 结束后不久 xzz 就跑路了，机房里就我和 gcz 两个人。论文我已经想好去写 rook theory 了，但 gcz 一直不知道去写啥。我原本让他写 Lyndon 的，后来想想感觉今年论文数量这么大应该会有 Lyndon 吧，果然 huhao 写了 Lyndon。之前 gzy 往联考里搬了个 clique tree 题，我说要不找些资料写弦图和 clique tree 相关的东西，原本他是拒绝的，但后来确实没啥其他的好写的东西了，于是他就直接去写了。我找 rook theory 的论文也找了好久才找到足够，还有好多 q-analogue 的内容没看，一看到 q-analogue 论文里一大摞的式子我就烦躁，于是直接跳了。从找资料到初稿完成大概花了一周时间。后来 nealchen 在集训队群里喊了喊要办民间胡策。我先是把论文里那个排列降低计数的原创题丢给了 EI 看了看，他来了句“这不小 Q 的序列吗”泼了我一身冷水……后来想了想小 Q 的序列的计算确实和下降幂棋盘多项式定理意义上是一致的，也就是给小 Q 的序列这类 ODE 题找了个组合意义，虽然又是一次组合意义的败北，但还是对这方面的理解加深了。后来直接把论文最后一部分拉出来造了模板题丢出来。看起来小 Q 的序列问题还不是很 well-known，所以场上只有 lyric 姐姐写了 30pts，Isonan 和 maroonrk 写了 20pts 的 DP 之后为啥不改成小 Q 的序列？为啥 Isonan 写过小 Q 的序列还不改？导致这题最高分最低，气死我了。赛后把辅助序列 SAM 和高维 FFT 写了写，nealchen、EI nb！我就只会当翻译官。

CTT 之后先把具体数学啃了啃，数学确实有意思，后来就是联考。WC 联考难度严格低于 CTT 是怎么回事？不过这很莫名地契合了 CTS 难度大幅降低的趋势也是十分的奇怪了。年底的时候 pb 来问我前几年论文有哪些有意思的，给他推荐了一些。pb 卷王！

CTS。房间分法玄学，和 zjc 哥哥住在一间。zjc 哥哥睡觉睡得好早啊，弄得我睡觉也比平常早了不少。为啥上网课还要集中起来上？为啥 WC 还有 Miller-rabin？杂题选讲还是比较有意思。第一天晚上把员交开火车开完了又被喷 HN 口音自闭了，dmy 哥哥的调整算法听起来还是比我的舒适到不知道哪里去了，Lagoon 哥哥讲话的腔调很有意思（那→确↓实↑很难写），zx 的半在线半掉线，据说当时网比较卡于是出现了魔幻电音？不过当时在场的听起来还是没啥问题的。因为不会骑单车所以我几天去计算所都是走二十多分钟路去的。

Day1。左前方是 myh，正前方是 jly，瑟瑟发抖，不过 myh 绝大部分时间都在考场外随机游走。T1 先染色证有没有哈密顿路，再对着 \(n=1\) 构造一发，再想想怎么做 \(n>1\)，似乎对 \(4k+1\) 维绕一绕 \(n=1\) 的情况就行了，模拟起来稍微有点麻烦不过很快就过了；T2 好像可以三分，原本想直接套 \(n\) 层的，后来想了想似乎把每个后缀的答案求出来之后三分就可以直接枚举到后面来 check 了，\(O(n^2 \log w)\) 不到 100ms 就过了 \(n=3000\) 是什么鬼。T3 把暴力写了就开始疯狂卡常数，结果怎么卡也卡不进第二档，直接自闭。最后 \(100+100+55\)，不过没有人过 T3 也没有人卡进去了 Sub2，所以半数人都是 255。zx 哥哥没过 T2 默哀，myh 哥哥病了默哀。晚上 zjc 回去就在他的 MO 书上翻到了 T1 的原题，结果他自己没过……于是冲到了第五，与 dcx 差一分多。

Day2。左前方又是 myh，正左方是 dcx，正前方是门。开始时数据还没造好，感觉非常危。T1 弦图题吓了一下，后来发现求一下完美消除序列之后贪心选数量少的就行了，感觉这题十分智障，交上去提交编号 1 很满意。jly 后来说他乱随两下就过了。T2 想了好久还不会，于是先看 T3，用点分治二分，再把树上每个节点的到达时间看成一段区间进行合并？看起来很正确，这时候有一些人问 T3 题意，当时看到一条边经过人数不超过 \(a\) 确实也很迷惑到底是单向还是双向总和，不过感觉这么写就应该是双向分别不超过 \(a\)，于是开始码。中途 zjc 出去的时候踢了下地上电线，然后我电脑黑屏了，于是多了五分钟加时。点分到一条边的情况巨难合并，写完好几次 WA0。后来写了个暴力还是 WA0，大概这时候 yhx 和 skip 就离场了，我吓得不轻。最后问了问发现是双向总和不超过 \(a\)，公告也不发一个？？？据说最开始 gwy 也认为是双向分别不超过 \(a\) 所以给某些提问选手错误题意？？？好离谱，真的好离谱。于是把点分合并稍微改了下，65pts，然后再疯狂卡常卡常终于卡过了。此时 pb 也离场了，还有一个多小时，我开始紧张起来。最后看了看 T2，在紧张的时候大脑竟然变得灵活起来，突然开窍发现 \(a \rightarrow b\) 和 \(b \rightarrow a\) 同时是或同时不是，这样就可以并查集合并了，之前一直以为不是这样的，我是大 sb。很快写完 \(q \log^2 n\) 就 AK 了，当时看了看 dcx 发现他还在场上，当时感觉很稳。最后下去吃饭的时候发现 dcx 才离场以为他没 AK 内心窃喜，结果后来 myh 说 dcx AK 不离场我白高兴一场。喷 IOI 赛制 AK 不离场人。dmy 似乎因为 gwy 传达了错误题面给了一两个小时加时，但有的给错的没有？很神必。不过把加时得分去掉之后排名也没变化就是了。

Day2 晚上营员交流，EI 的内容半小时讲完谁听得懂？？？？？Cyanic 的自动机倒是挺亲民的，但上了预科的我表示这似乎就是《形式语言与自动机》里的内容。Day2 后面一天是 WC 赛，从 zjc 那看到题目之后感觉题目挺简单的，T1 = CTSD2T2 是什么鬼？早上练了几次面试，因为 dmy 凌晨要考试所以早上在睡觉，于是 EI 就跑到了我和 zjc 的房里来干活，然后我和我教练下来找消失的硬盘，期间我教练就和 EI 聊了聊，我在外面瑟瑟发抖。最后发现我硬盘在大衣口袋里。dbq EI TAT。中午和 gcz、slz 做了核酸，似乎双十的教练把我名字的姓打错了于是要重新挂号，迷惑。

Day3 面试。不得不说穿了西装之后感觉到了颜值巅峰，虽然长得还是很挫。放个照片纪念一下。

提问内容再现去年“你和 xxx 只留一个留谁”和“你会换掉前四中的哪一个”这种送命题，还有对去年第五 zrf 的口音题为啥又落在我身上了，这是第五传统吗？看起来 dcx 准备不是很足的样子，《中国计算机协会》。dzd 对我问了个“长郡在外界看来是给的压力很大、作业很多的学校你怎么看？”我不假思索回答“老师布置的任务不是很多，只是大家比较卷自觉而已。”我好歹也上过一段时间学科，这也确实是我的亲身感受。dzd 接着说“以后有人这么说学校还是要辩解一下。”心中是真切的感动，为学校争光对于我这种平凡的学生来说已经是很大的荣幸了。最后就是名场面：wh 宣读的国家队是前四，结果 PPT 上进队的是我，不过过一会儿就被改掉了。发扬阿 Q 精神，四舍五入我也是国家队！!1 最后 dmy 哥哥执意要我和 jly 哥哥的签名，似乎因为我们 cf 分很高？最开始我觉得第三要第五第六的签名怪怪的，后来 jly 提议互换签名，于是每个人就有了另外两个人的签名。

Day3 下午就跑掉了，在飞机场的时候似乎 dzd 在我们教练发的朋友圈下面回复了一句“面试不错，以后讲课可以考虑一下。”当时我还没太在意，结果

噔 噔 咚

最后把集训队时期的产出（自选题题解、员交 PPT、论文和六选四 PPT）放这里留给后人阅读。

旅伴

教练

OI 路上最重要的总还是教练。前期教练会带着学一些内容，不过教练确实懂得也不多，除了白书内容之外大概还讲了 tarjan、miller-rabin、莫队、树链剖分之类的内容（教练会 miller-rabin = 教练会 WC 第一课堂内容 = 教练会所有 IOI 题 = 教练 AKIOI），不过有次我给小学六年级的小朋友造题的时候造了个离散化树状数组我们教练就不会了，当时问了考得最高的表示他完全会这玩意。不过确实是学校老师在学校*内还有很多事情要做所以没有时间提升专业技能，而且确实没有很大的必要提升。在模拟测试和正式比赛之前教练也会经常重复一些考试的经验和策略，同时重要的考试之前教练都会与学生进行沟通，不知道其他人沟通效果怎么样，我个人还是比较信任教练，所以会跟教练聊比较多的东西，可能甚至要比家人聊的范围要广一些。同时因为教练有带集训队经验，所以进了集训队之后的学习节奏也有了很好的把握。进了集训队之后机房人数迅速减少，和 xzz 也不是特别聊得来，gcz 的交流能力也不是特别强，同时由于高一高二在机房训练的时候对自己要求很高要求自己不去摸鱼，导致待在机房的时候没啥话可说就状态很压抑，很频繁地跑到走廊上随机游走，一走就是一两个小时。后来教练找我聊了聊之后接下来一段时间的情绪就会放松很多。如果没有教练的话可能 CTT 和 CTS 之前会闷死在机房里。

本校

laofu 和 ymdragon 应该是这几届比较熟知的 cj 学生中最年长的了，不过我和他们本人的交集不算很多，也没有给我留下很深刻的印象。不过我的教练倒是经常提起与他们以及更早的学长有关的事情，也算是在他们的遗宝之中成长起来的。他们的下一届接触的也不多，主要是我实在是太自闭了。Anson 给我们讲过很多次课，也在我快速成长的过程中造了不少的题目助了一把力，给我带来了不小的启发和知识（套话.jpg）。那年集训队作业中知名的单位根反演题 复读机 是他的作品。似乎他的 CTT 排名很高，但 WC2019 产生了很大失误于是没进前 15，有些遗憾。另一个集训队 goldgenius 早期也给我们讲过几次课。

我们上一届的学生的交集则相对较多，因为有较长的共同学习时期，但其实也忘得差不多了。

• 唯一的集训队 zsy 为啥上带学就有人追啊，虽然最大功臣似乎是助攻仓鼠但还是酸