第二段旅途

· · 个人记录

我的 NOI 游记总体写得比较消沉，不过我不觉得有人能在 UNR 被大爆一次、NOI 被小爆一次后仍然能非常乐观地讲述这些事。但虽然游记中表示出不知道接下来要怎么走，最终我还是决定还是认真把第二年打完：一来是我已经声称 “要再冲一年国家队” 占了 NOI 的一个金牌名额了，打完 NOI 就改口说摆了放弃无疑有点幽默；二来是感觉算法竞赛还是挺有趣，至少比预科课程好玩！有机会的话当然还是要做有趣的事情；另外的想法就是，别的可以做的事基本上未来还有机会去做，但要想在 OI 上再进一步，这是最后的机会了。

当然，我指的认真打完当然和高二下的模式保持一样：就是去读预科然后有空就训训 OI。高强度停课训，谁受得了啊！另一方面我也隐约觉得为有些事情付出太多，反而会越想做到越做不到。所以就保持一个正常的训练量差不多了，再加训反而可能会起负作用。

8 月应该就简单训了会 OI，下旬好像 HEZ 机房又开始安排训练了，于是就去了几次。多来了很多高一的学弟，感觉勉强认了个脸熟……

接下来的问题是下半学期预科的选课，那指导思想当然是少选点课。一开始是打算只选数分高代和一个 “据说很轻松” 的数算和一个基本啥都不用干的信概，把一般其他人会选的计概卖了。结果数分期末好像和英语学考冲突，于是改为把数分卖了，计概捡回来。

期间应该有一些人找我让我出模拟赛或者讲课之类的，但我觉得这学期不能再做太多乱七八糟的事了，于是全拒了。然后听说 shz 接了一堆。

开学之后就正常上课，感觉高代还是学到挺多，lww 讲课喜欢把各种线代其实隐式要用到的基础内容也都讲清楚，感觉这种讲课方式很对。不过缺点在于后半学期为了赶进度，讲课速度疯狂加速，有点魔怔。经常 2h 的课开头讲一个新东西的定义，然后中间讲一堆性质结论，一节课结束这个东西也讲完了，然后我基本啥也没听懂，只能回去看讲义。然后往年期末都不考计算题，于是我也没练，结果期末考一堆计算题我全算错了（甚至算错一个 3 \times 3 矩阵行列式……），直接被拿下。

然后是计概，前半部分讲 haskell，感觉讲课进度关于时间形如：先陡增一下，再走平很长一段时间，重复若干次。于是你在进度陡增的时间会什么都没搞懂，自闭了；在走平的时候发现这些东西都已经搞懂了，困死了。后半部分讲形式化证明之类的东西，感觉本质问题在于虽然他 claim 在一些限制下可以做形式化证明。但一方面限制太紧，感觉复杂一点的东西都证不出来，能证出来的东西证明方法也很麻烦，not practical。期末考证明要求必须写八股文，但我场上八股文没写明白，又被拿下了。

然后是数算，这个课我真懒得喷了。首先讲义中内容大多是 2008 年写的，快 20 年了。然后课程的本质难度就是靠莫名其妙反常识的定义让你看不懂题，从而做不出来。举个例子：一个字符串的 fail 序列的第一项应当为 -1，后面的第 i+1(i>1) 项应为 s[1,i] 的 最长 Border 长度，从而你计算 fail 序列无法得到整个字符串的最长 Border。期末考还有优质好题：用 splay 维护序列，但需要维护每个节点在原序列中的 index，要求 “不使用懒标记”，于是你应该写一个单次操作时间复杂度为串长的算法。

信概就是找各种方向的老师来给你介绍这个方向的内容，但我听了几节课后来就摆了。这门课也没有期末考，只要求交个听课笔记，我就随便写了一下。

最后高代、计概、数算都勉强混了个优秀。信概好像忘记问成绩了，但这是 PF 课，没道理 F 吧？

于是大家应该感受到预科课程有多么有趣了，现在是不是觉得算法竞赛也挺好了呢。总之，接下来还是谈谈算法竞赛吧。

这期间的训练目标当然还是备战 CTT/CTS，但传统弱校（？） HEZ 并没有 IOI 赛制的模拟赛（听说 nfls 联考有啊，很有实力），于是我决定认真打 集训队互测 。起码这个比赛确实 5h 三题有部分分，而且部分出题人应该还是会认真命题的。

说到互测，我投给互测的第一道题目其实在 23 年互测结束后不久就已经出出来了。当时命题的动机是 zak 出了一个很有趣的计树题是关于将一个经典树上问题转为计数的形式，于是我也想出一道这样的题。枚举了一会题意之后发现对 Purple Crayon 这题涉及的经典问题转为计数是可做的，而且做法还挺有趣，就决定明年互测投这个题。不过当时给的标算是 O(n^4) 的，后来参考了我给 shz 验题时他从另一个角度得到的 O(p(n)n) 做法发现其实可以优化到 O(n^3)，开大了一点数据范围。但验题时学弟说他 O(n^4) 和我一开始没用力卡常前的 O(n^3) 在 n=300 时差不多快，我感觉不好卡就放过去了。

我的另一道互测题正如命题报告中说的其实是 alpha 给的，感觉也还比较有趣。同时这道题让我也略有收获，虽然学到的系数为多项式的矩阵的牛迭求逆方法跑得未必更快就是了。

然后互测打得其实整体上还不错，R1/R7/R11/R13/R16/R17 未参赛。剩下的场只有 R15 被 fxt 倍杀了，很自闭；其他场应该最多也只比最高分低了 ~40 分，感觉其实还行。R1 我看过 fxt 一开始在 AGC055D 的题解还评论了一句于是被 DQ 了；R7 是撞了高代期中考；R11 我看 C 答案上界可以到 6.25e19 觉得出题人不是很尊重我，于是下班了；R13 是发现打了会不太来得及复习计概期中；R16/R17 分别是验题出题。

互测所有场中印象最深刻的当然是 R2，这场打得无比顺利。我一眼就看出了 B 的简单做法，1h 内就通过了；A 做了几步正确的转化之后猜了个错误的结论但顺利在 3h 通过了题；C 做了几步转化之后搬了 ARC146F 的做法，直接会了！写写写剩 30min 时通过了 85 分，最后要写任意模感觉一点意思也没有，算我 AK 下班了。发榜看见我 285 分大胜剩下所有人，甚至接近倍杀了很多 NOI 排名比我靠前的人时，真的有一种浴火重生般的激动。那天晚上应该在未名湖边逛了两圈，觉得只要 CTT/CTS 上有一场像这样大胜，剩下场全部苟住应该就赢了！毕竟我 CTT2023/CTS2024 拿了三场 rank2，我当时还是挺相信 CTT2024/CTS2025 也能复刻这样的大胜的，虽然事实上嘛……

互测之外的训练一方面是在各个 OJ 上随机做题，一方面是在各个 OJ 上随机打比赛。其实洛谷月赛应该也大胜过几场，还是增强了一些信心的。CF 在 2900 左右上上下下了几次后，Global round 27 打得很顺直接拿了 rk4，而且其实最后一发代码不交就 rk1 了（当然换个角度说最后一发代码不交之前交的过 pretest 的暴力 FST 了就爆炸了），上了 LGM，不过不是很激动因为好像其实没啥用。然后又打了一场掉下 IGM 了，又打了一场上回 LGM 了，其实也都无所谓！AT 方面的话，暑假里打了 AGC067 过了两个比较复杂的数数拿了个 rk5 直接也上到 3000 分了，虽然其实其实是利用了收敛的机制，但算我赢了。之后几场 AGC unrated register 打得都中规中矩，30~60 名的样子。

然后在机房训练应该受到了 wwc 和钱哥的一些指导，虽然我也一下子说不上来指导了点什么，总之感谢一下。

然后不知不觉就 CTT 了，我本来并不认为我会在这场比赛前太过紧张，但事实是我在 day1 前一晚严重失眠，直到凌晨两点才昏沉入睡。这种感觉和 Qiuly 老师曾在 CTT2023 描述过的 别无二致，我躺在床上时也曾想起过 Qiuly 老师的这篇游记，并思考这是否是一种轮回，这就是太过想赢的后果。

CTT day1 我醒来时感到精神有些疲惫，不过好处是困意完全盖过了紧张。进场之后左边是 LHF，感觉还是很有实力。看三个题，A 看上去就不是多项式复杂度的，但 n \le 50 是不是有点太大了，2^{25} 乘不了任何 \operatorname{poly}(n) 了，没看懂；B 应该是找一找性质简化问题然后怎么维护一下的题，肯定要花时间做一下；C 计算几何 + 交互，不是给我做的题。

试着做了做 A 立刻发现了 O(2^mn^4) 和 O(2^{n-m}n^4) 的做法，并发现了固定其他项时答案关于 C 是 n 次多项式。因为 A 的 O(2^mn^4) 很好写就随手写了一下，调对了但其实根本没多少分。此时大概 40min~1h 左右，感觉把 A 手上所有会的做法写完也至多 40 分，于是决定先想想 B。

这个时候可能是开始做题进入状态了，困意倒逐渐消退了，感觉状态至少不算太差。B 做了做很快发现了答案实际上在求什么，然后就单次询问 O(n) 了，写了一下拿到了 45 分。优化只需要拿数据结构大力维护一下，明确了一下具体细节并找了个常数相对小一点的维护方法后直接开始写，2h 左右通过了 B。回过头来看 A，发现用点容斥手法很容易分别去掉一个 n 分别变为 O(2^mn^3) 和 O(2^{n-m}n^3)，把两个做法都写了出来拼起来，然后发现 20 分的 m \le 16 的包过不去，只获得了 40 分，此时 3h。

感觉人有点麻，m \le 16 看上去 O(2^mn^3) 还挺有道理，但考虑到 n=50 好像又确实得用力卡常才能过。想想还是不急着卡，看眼 C 到底什么情况。然后我看了下特殊性质怎么是那个 Stern–Brocot 树的板子，但我不会啊。既然特殊性质都是我不会的科技，该题鉴定为不可得分，于是我回到 A 了。回到 A 先试着给 O(2^mn^3) 卡了几下常，但没成功卡进去。于是我冷静下来决定再仔细看看这道题，好像 2^{25} 不乘 \operatorname{poly}(n) 是有点不太对劲，然后我仔细阅读了一遍题面，发现题意是：只有前 n-m+1 个位置可能被选中执行将从它开始的连续 m 个格子 +1 的操作？？？我一直以为是 n 个位置均可能被选中，但后 m 个位置如果延申到不存在的格子就不加了。然后我代码也写的是读入 n 个权重，但实际上我一直 freopen，代码只读到 n-m+1 个数就默认没读到的后 m-1 个权重均为 0 了，此时刚好题意是对上的？？

读对了题意之后仔细想想，发现我的 O(2^{n-m}n^3) 在这个题意下完全可以是 O(2^{\max(0,n-2m)}C^3) 的，如果 C>n 因为答案是关于 C 的 n 次多项式插个值也完全可以 O(2^{\max(0,n-2m)}n^4)，这样整体就 2^{n/3}\operatorname{poly}(n) 了，看着就很对！ 赶紧开始对后半部分优化，还剩 1h 左右时调对了，但当然也只多过了 n \le 40 的包，现在变为 55 分了。m \le 16 的包因为 O(2^mn^3) 没优化还是过不去。

此时开始上真功夫卡了，加了一堆优化内存连续性和 18 次一取模之类的操作之后终于冲过了 m \le 16 的包，75 分了，此时还剩 40min 左右。想了一下 C 不可能得分，于是只能继续做 A，那么唯一得分的方向是把 n \le 50,C \le n 的包卡过去。发现瓶颈在于 n=50,m=17 时 O(2^{n-2m}C^3) 有点慢跑不进时限（虽然本地好像早就能跑进了，但评测机比本地慢），同样用优化内存连续性和 18 次一取模之类的操作之后发现本地甚至进 1/2 时限了，但交上去还是过不去。我在只剩 15min 左右时决定使用神秘技巧：循 环 展 开，对一个循环八次展开后本地直接慢到时限附近了，但是 交 上 去 过 了。90 分了，很兴奋，最后 10min 看了会 C 的第一个包，但还是不会做。结束时发现 LHF 在调 C 的代码，他想必是会 Stern–Brocot 树的！一问发现是 45+100+20，我在完全弃掉一个题的情况下还稍微高一点，可以接受。

最后 90+100+0=190，看榜发现今天是（并列） rk4，虽然标准分是 lhx 的 260，但因为 C 就他一个人 >20，其实比赛结果相当于把他保送了然后剩下的人中我还是相对领先的。

听讲题，A 的第二个包说是给 O(2^mmn^2) 过的，然后我 O(2^mn^3) 就得卡常才能过了？？但 m 是 \dfrac{n}{3} 左右，好像又确实有点合理。后半部分标算是 O(n^6) 的，那我好像确实没做明白，但我最终复杂度介于 O(2^{n/3}n^3) 和 O(2^{n/3}n^4) 之间，比标算 O(2^{n/3}n^3) 稍微少个 10 分，很合理吧！B 我和标算想的也差不多。C 的第一个包主要是没怎么想，没发现斜率其实绝对值不超过 1，如果发现了应该还是会做的。标算又不知道什么鬼，反正我肯定做不出来，lhx 讲了他的做法，感觉也很外星人。

因为 CTT day1 前一晚失眠，我和李老师说了后他给了我褪黑素。然后我晚上吃了之后又失眠了，感觉可能药效不够强，最后又凌晨两点才睡着。

连续两天只睡了 4h，进场前当然比 day1 前更加疲惫，但比赛还是要打的。进场之后右边是 fxt，很有实力！看三个题，A 这个题意我好像研究过应该是取出度最大的点就一定距离 \le 2，但询问边的方向当然不能用来算出度；B 看上去像是 EI 出的，又是要推很多性质才能做的数数题；C 数据随机，完全没看透。

试着做一做 A，但完全想不出任何有道理的做法，只想到了几个乱搞。到 20min 决定换到 B 想想，题意很复杂，我想了一会发现有 O(n^3) 的方法可以判两颗树是否满足题面所说的关系，决定用第一个 n=8 的包确认是否正确，然后 O(n^{n-2}n^3k) 可能再乘一些杂七杂八的项交上去就 TLE 0 分了，但样例能过感觉应该没错。接下来应该思考了如何简化判定，做不出来；思考了如何做 p=0,k=1，做不出来；思考了如何做 p=1,k=1，做不出来。到 2h 时我只多过了一个 p=0,k=1 且 T 为菊花的 4 分的包，这个包就已经要输出贝尔数……到 2h 时我终于意识到我今天精神状态太差了，虽然我平时显然比起交互题 A 和神秘构造题 C 更擅长 B 这种性质分析计数题，但今天面对这道显然非常复杂的题目，我做不到。

没有办法，我只能回去做 A，又想了一会还是不会有道理的做法，感觉实在没办法了，只能交乱搞了。选了一个我觉得最靠谱的乱搞交上去，一看发现 70 分左右，很对啊！又加了点乱七八糟的优化，接近 80 分了，还剩 2.5h 左右。既然 80 分了，B 我现在的精神状态又做不出来，我只能去试试完全看不透的 C 了。

看到 C 先思考了一下 checker 是怎么写的，不幸的是我状态实在太差了，所以我没看出来…… 10min 后我觉得今天看来是做不出什么有道理的东西了，于是决定转变方向试没道理的东西。简单分析了一下构造何种形态的解一定是对的，发现 C 其实可以对每个叶子任意输出一个 DFS 序，这确实是一组合法解。写了一下交上去发现 ~60 了？？感觉今天乱搞很对啊！于是决定今天继续用力乱搞，沿用之前的分析发现一个菊花其实是很可以优化的，写了下 ~85 了，又加了点神秘优化，~93 了！此时还剩 1.5h 左右，对 A 稍微优化了一下，82 了！感觉 A 和 C 竟然现在都没什么得分空间了，回去做 B 好了。

回去看 B，先卡了卡常把第一个包过了，然后发现 p=0,k=1，T 是链这个 7 分的包其实是输出 n^{n-2}？？现在 B 21 分了，也许是得了很多分人的精神状态变好了，我分析了一会并结合打表顺利做出了 p=0,k=1，又多得了 7 分！最后 40min 对 p=0,k>1 时猜了个做法写了一下，但最后发现并不对。最后又改了一下 C，97 了！结束时发现 fxt 也在调 B 的代码。

最终得分 82.72+28+97=207.72，看榜发现是 rk11，在精神状态这么差的情况下很可以接受了。总榜升到 rk3 了，很好。但 A 拿到了得分前缀最小值，感觉有点不牛。fxt 好像没发现其实 C 输出所有叶子有 60 分，感觉很遗憾。

听讲题，在讲题时我终于发现我一看到 A 时就想起来的 “我研究过取出度最大的点就一定距离 \le 2” 究竟是在何时研究过了：其实是我在做 CF1019C 思考该题在竞赛图上的情况时研究过的，而用 CF1019C 的做法显然该题就可以直接做到期望 2n 次询问了！标算也是这个，听说很多人也一下子用这个做法过了。感觉今天状态太差，平时我应该总能想起来这件事的，亏大了！B 讲题时发现 p=0,k=1 时给出的限制其实就是只有一个边集的子集可以出现，于是 p=0,k>1 时只要把限制交起来矩阵树定理就可以多过两个 10 分的包了，感觉应该平时也能想到啊！C 我写的乱搞好像还挺对的，出题人 siqi 直接证了一下差不多的形式是答案的一个下界，把我写的一个比较粗糙的地方改对就确实取到下界，是正解了。

另外发现 B 的出题人猜错了，不是 EI 而也是 siqi，siqi 太有实力。想了想感觉标准分 248 没什么本质难度，但反正就是没做到。

day3 前我妈听说我连续两天只睡了 4h，比较担心我。同时考虑到其实住酒店家长是可以进的，于是决定特地来北京陪我一会。这天晚上睡得还行，中间醒了一次但断断续续睡了 8h 左右。

进场发现右边是 ylx，很有实力！看三个题，A 是一个关于 上升/下降 的数数，虽然不知道为什么要在环上做，但这个我应该很擅长啊！B 是 n \le 14 题，感觉也没道理不会；C 是猜树结构的交互，感觉看不出来难度啊。

然后决定先做做 A，发现做连续段 DP 确实可以多项式复杂度，但感觉要记很多个元。考虑到做 CF2018F3 时太急着写记太多元的暴力导致简单做法没看出来的惨痛经历，我想想觉得肯定有什么简单转化，还是别往记一堆元的暴力上面想了。因为 n \le 500 的包有足足 45 分，觉得目标应该是一个 O(n^3) 做法。拆了会贡献之后貌似确实想出来一个，然后就试着写了一下，调着调着发现假了！此时已经过了 1h，我意识到我又犯错了：应该先写一个 O(n!) 暴力确认贡献是否拆对的。感觉人有点红温，决定先换到 B 做一做。

B 感觉做法很显然啊！把这个过程画出来并倒着做，一下就看出来怎么做了！但一开始细节没全编对，所以还是对拍调了一会，还剩 3h 时才过。

回过头来看 A，决定继续找简单转化。在试了很多很多种拆贡献的方法之后我终于发现了一个重要事实：按照顺时针转环，RB 的出现次数总和 BR 相等，而可以拆贡献使得这两种情形的权值分别是 1 和 -1！基于此又想了想终于得到了一个 O(n^3) 做法，赶紧写了一下在还剩 1.5h 的时候拿到了 85 分。显然可以 FFT 优化到 O(n^2 \log n)，但最后要用 FFT 做的问题形式略有点特殊，说不定会有更简单的做法从而标算不是这个。当时没有意识到虽然 n=3000 但其实常数可以分析出是比较小的，同时我只会背效率不太优秀的递归式 FFT 的板子，再考虑到最后一个包只有 15 分，决定还是先不写了，毕竟我 C 现在还是 0 分。

C 看了看发现得到任意定根后的拓扑序就简单了，可以整体二分求每个点的父亲。但我错估了这题的难度，觉得如果求任意定根后的拓扑序也很简单的话这题不太会出现在这里。求拓扑序只想到了一个 shuffle 整个点集后试着加入每个点，如果其父亲也已经被加入那就顺利加入的不牛做法。实际上如果树是链就直接被卡到 O(n^2) 了！然后试了试点分治的角度，发现可以大概 O(ndeg) 次询问对分治中心度数为 deg，一共 n 个点的树按照分治中心切开。拼起来的话直觉上有一个询问次数为根号的做法，此时只剩 1h 了，感觉更迟开始写的话都不一定能写完这个做法了就直接开始写了。剩 15min 左右时拿到了 ~55 分，最后尝试了一些乱搞到了 62 分。结束时发现 ylx C 只有 30 分？

最终得分 85+100+62.66=247.66，看榜发现又是 rk11，不知道为啥大家都 285 了！总榜掉到 rk5 了，但好像离 rk4 只差不到 1 分，还能接受。感觉 A 的拆贡献很不好想啊，但 85 分就像批发一样，完全没搞懂。交互题其实是简单题，我最后可能也隐约意识到了这一点，但也没办法了。

听讲题，A 和出题人想的完全一样！最后一步 FFT 也是对的，主要是我没时间写了。然后听大家吐槽说 O(n^4) 全过 n=500 了？？而且做法是真的就用记很多元的暴力硬优化？？感觉我的策略没错啊，但凡 n=500 改成 n=1000 这些拿记很多元的暴力硬优化的人肯定都寄了，但就是运气不好反而我寄了。B 和出题人想的也完全一样，确实简单题。C 出题人讲了几个奇怪的做法，好像和我想的没啥关系。

疏散的时候 shz 和我说他只会找拓扑序后面不会，我听他说直接问全集去掉每个点就可以知道以每个点为根时其大小最大的儿子，从而确定以重心为根时每个点的子树大小，然后排序一下就是拓扑序了。感觉这个 C 放 CF 上看大家都过了我肯定也会了，主要是没看出难度。想了想标准分 285 也没有本质难度啊，甚至 300 如果时间足够也没有本质难度，但反正还是遗憾离场了。感觉这场运气也不太好，特别是 C 满分要求次数 6 \times 10^5 次，我的做法问 10^6 次在最后一个包就只有不到一半分了，但这理论上都可以被说成两倍常数，如果是我出题的话不太会这样出。

CTT 结束后总榜是 rk5 啊，感觉还是稍微有点难过，主要是 day2 和 day3 都被莫名其妙的理由被爆了 40 分。但其实结果还能接受，当然是要继续的。然后看到一些 CTT 中成绩不太理想的同学也还在训，感觉他们很有毅力啊，很厉害！

然后就要写论文了，我论文要写的内容也早就定好了：4 月的时候做出了一个线性基相关问题的更优解法，还挺有趣的，当然要写这个了。写了几天之后发现我的带删前缀线性基怎么只有部分前缀性？随手捏了个例题就做不了了！于是开始思考这个例题到底怎么做，断断续续想了两天貌似得到了一个做法，写了写发现假了！幸好保留整体思路，用力修了修细节修对了，能和暴力拍上了。很激动，决定把这个称为 “具有完全前缀性的带删线性基”。

期间钱哥说 PKUWC 缺投啊，我就把之前做题的时候捏出来的一个感觉还挺清新有趣的题投了过去。过了几天说投中了！但这题数据很难造一开始想让 shz 造，但最后他也说太难造摆了。最后我改了下要求的东西，虽然做法更显然了但不然数据造不出来，也没办法。最后比赛的时候发现最后一个包有没想到的暴力冲过去了，非常遗憾。

然后中间就正常训了训，最后备战了一会期末考，感觉没啥好说的。

期末考完回 HEZ 机房了几次，然后转眼就 CTS 了。CTS 讲课我看了眼发现都不太能听，要么就是太难了要么就是讲的没啥用，第一天 zak 的讲课看上去比较靠谱就去听了一下，然后发现我的论文怎么一道题直接被爆了。幸好后来做出了 “具有完全前缀性的带删线性基”，不然好像论文还真没什么可讲的了。

营员交流的 slide 本来是按照 15min 准备的，结果最后说只有 10min。想想把被 zak 爆的题删了刚好省 5min，结果最后好像稍微短了点，9min 左右就结束了。最后看营员交流分不是很高，但我觉得我的带删前缀线性基很有趣啊！不过只差 <0.1 分也无所谓了。

CTS day1 前换了种更靠谱的安眠药，吃完后不久就睡着了，然后症状变为了凌晨 4 点就醒了。又尝试入睡了两次，每次分别睡了 1h，到 6 点实在睡不着了，发呆了一会。然而比赛要拖到 10 点才开始，中间又发呆了很久，倒也不算太紧张。

CTS day1 进场发现坐在一列的最前面，所以我也不知道附近都有谁。看三个题，A 看上去很离谱，如果没有简单性质的话感觉就很难做，部分分看上去也很不友善，n \le 30，2 分是什么意思呢；B 看上去也需要找性质认真做一做，但要输出 m 组方案感觉更困难了，不好做；C 看上去属于要么很简单要么很困难的题，当然得试一试。

先试着找了找 A 的简单性质，猜了几个结论但画了画都叉掉了，30min 也完全没做出多项式复杂度做法，第一个 2 分的包也不会！感觉不是简单题，B 也暂时不想做，先看 C。C 马上就会了 O(n \max b_i) 的做法，写了一下确实是对的，15 分了。试着对 DP 换了几个形式，很快换到了一个简单的形式，只需要维护 2n 个位置的值，这样就 O(n^2) 了。仔细看了看转移，好像线段树优化一下就 O(n \log n) 了！看来这是很简单的题，先快速写了一下 O(n^2)，35 分了。然后写了下线段树优化，一开始线段树写挂了…… 调了调过了，此时大概过了 1h。

决定试着做一做 B，当然要先做第一问了。试着分析了一下发现按照从高位往低位做很有结论，写了个我也不知道复杂度是什么，但其实记忆化一下就 O(2^n \log a_i) 再乘点乱七八糟的项的做法过了第二三个包的第一问，有点疑惑为什么没有 n \le 15 之类的包。再做了做又编出来了一个 B 特殊限制（B 题 B 特殊限制，是否有点奇怪）下第一问的结论，交上去也确实是对的，34 分了。数了数剩下的没过的但会的分，发现有 4+6+6+6+6=28 分，拼完就 62 分了，感觉还可以就换到 A 了，此时还剩 3h。

又做了会 A，找到了 A 一个比较复杂的答案的形式，据此可以得到一个 O(n^4) 的做法，但只能过前两个包一共 12 分。然后又想了想 k 充分大怎么做，发现此时答案乘上 2^{20} 就已经是整数，二分答案然后 check 就可以 O(n \log \max a_i)，猜想是不是一般情况和 k 充分大时的情况有类似的优秀性质。写了一下 k 充分大时的代码，交上去直接 WA 了！没办法，虽然 O(n^4) 做法很垃圾但也还是只能写了。一开始写成 O(n^4 \log a_i) 还只过了第一个包 2 分，改了改变成 O(n^4) 12 分了。对拍了一下之后把 k 充分大也过了，现在一共 28 分，此时还剩 2h。

然后试着 assert 了一下 O(n^4) 代码输出的答案只有前 O(\log a_i) 位可能为 1，直接 assertion failed！不是，那这题是人能做的？直接放弃去看 B。想了 20min 第二问怎么求，但我第一问做了一个很不方便的转化，虽然对做第一问有帮助但导致做第二问更麻烦了，于是没怎么想出来。有点担心这个转化其实求不出所有解，于是用这个转化试着把之前记忆化后 O(2^n \log a_i) 的代码改到能输出解，然后改完交上去 WA 了，一看发的样例都没过，找出来的解太少了！感觉人有点麻，仔细想了想发现之前对转化的认知其实是有点问题的，又改了一会终于把二三个包给过了，期间顺手把 m=1 的那个包也输出了正确的方案，现在 B 52 分了。因为重新思考以及重新写代码浪费了一些时间，只剩 1h 了。

纠正了对转化的认知后发现输出方案可以搜，但我似乎只想到了一个 O(mn^2 \log^2 V) 的做法，就算上一点手法优化也只能 O(mn \log^3 V)，看上去还是不能多拿分。考虑到 A 性质会一个比较麻烦的做法还要额外拼，如果能做出整个第一问是直接多得 2+6+4+4=16 分，决定换去想整个第一问。做了做会了然后写了下，在只剩 25min 左右的时候对了，现在 B 68 分了。最后尝试写了一下 O(mn \log^3 V) 的做法，但感觉不可能多得分也来不及了就没有特别认真写，最后写完了没调出来，补了第一个包的输出方案 B 70 分了。

最终得分 28+70+100=198，看榜发现是 rk6，虽然排名比之前好但还是和前面的几个人差了 ~30 分。但总榜因为 CTT 结束时的前四爆了两个下去，现在回 rk3 了！但和 rk4 和 rk5 的差距 <1 分，还是要看最后一场定胜负。看到 zhk 过了 A 100+48+100=248 标准分感觉很有技术啊。另外好像我对 A 的难度估计有点错误，其实 41 或 61 还是比较可做的。

听讲题，但是 A 根本没讲！不过听说 A 正解非常难写，std 写了 7k，zhk 过了写了 11k，感觉确实在正解意义上挺不可做的。B 发现我的转化做的不好，导致后面浪费了很多时间，最后其实是把我没写完的 O(mn \log^3 V) 做法再加一个结论就 O(m \log^3 V) 正解了。C 和标算想的一样，就是个简单题。

感觉今天最后 2h 打得偏保守，所以最终得分不是很高。不过 B 转化不好再快速找到正确的方向可能确实有点困难，A 可能连部分分也放弃掉有点太鲁莽了。确实策略上是存在一些问题，不过也还好。

CTS day2 前一晚吃了安眠药之后变为凌晨 5 点醒了，睡到 6 点实在睡不着了，又发呆了一会。因为是最后一场了进场前还是有点紧张的，有点成败在此一举的感觉。

day2 进场发现坐在一列的最后面，但因为是前后的关系没注意旁边有谁。看三个题，A 题面里怎么有线段和极角的，这是我能做的题吗；B 通信，这是我能做的题吗；C 交互，给你两个随机数生成方式让你猜用哪种生成的，这是我能做的题吗。

好好好，这样玩是吧。我直接释怀了，看上去今天的题不是很想让我进啊！看到三个题我就感觉今天怎么打都进不了了，倒也不紧张了。但这毕竟是我的最后一场 OI 比赛啊，还是要认真打完的。

先想了想 B，感觉比较简单的策略是让每个节点都知道一个子集的节点的精确值，然后每轮拓展这个精确值集合，最后每个节点都知道全集就合法了。但毛估估一下，如果希望给节点 u 传 S 子集内节点的精确值，感觉得有 2^{\left \lceil \log |S| \right \rceil} 个节点同时知道 S 子集内节点的精确值啊。这样算了一下，好像能做到的结果很差。此时大概过了 20min，想想还是决定换回 A。

看到 A，先背了一遍极角排序并写了个 2^m \operatorname{poly}(m) 的暴力确认了一下题意，交上去顺利拿了 16 分。然后分析了一下树的情况，拆了拆贡献发现，怎么一个点上的贡献只与以其为一端的黑白边数量有关啊？那输入的坐标感觉根本没用啊。做一下简单树形 DP 貌似就能做树的情况了，试着写了一下调了调交上去多拿了 23 分，此时大概过了 1h。然后考虑仙人掌，好像就经典考虑一下额外的非树边然后讨论各种情况就能做了。感觉这题应该难度是最签到的了，虽然仙人掌上讨论各种情况很恶心，也不得不写。于是开始硬写硬调，在过了 1h40min 时调对了交上去拿到了 70 分。最后 30 分的优化好像就是做经典的重量 0,1,2 的背包，想了想利用答案 \bmod 2 的凸性做最好写，写了一下 2h 时通过了 A。

感觉过 A 的速度还可以，但剩下两个题没准会坐牢牢死，其实也没什么用，所以还不算太紧张。试着实现了一下 B 之前想的做法，直接对每个节点枚举大小最大的可以一轮内可以收到的 S ，有多个就随机取一个。写出来发现效果确实很差，最后一个包只能拿不到 1 分！因为差太多（k=6 好像只构造出 n=10 左右的解）感觉这个思路不太靠谱，此时突然想起来有个 CF 题（其实是 1705F）好像是要猜一个 01 序列，每次可以问一个子集和，其实有一个 O(\dfrac{n}{\log n}) 次询问就问出长度为 n 序列的做法，那把这个做法搬过来试试没准会有效果。努力想了 20min 终于回忆起了做法，但算了算 k=7 还是只能构造出 n=15，就算用一点手法算了算得分也只有 35 左右，感觉也还是不太牛。

此时还剩 2h，因为 C 完全还没做，感觉还是应该试一试 C，如果 C 有更好的进展可以考虑放弃这个 35 分做法不写（因为纯暴力都有 11 分）。C 最显然的做法当然是直接算一算生成的随机数的 0/1 占比，如果和 1:1 偏差很远显然不是均匀随机的，交上去过了 5 分。然后仔细思考了一下这个问题，发现 x 序列其实很重要，如果不利用 x 序列不会有比算占比更好的做法。想了想我觉得如果是均匀随机的，基本不可能解出每个 y；而如果是另一种随机方法则应该可以？按照这个思路写了一下，发现完全不对！均匀随机时也可以拟合上很多个 y，另一种随机方法也很难解出更多个 y，此时只剩 1h 了。

那只能回来写 B 的 35 分做法了，写了写在只剩 25min 的时候调对了。最后又试了试 C 的算占比，但没有多得分。

最终得分 100+35.85+5=140.85，看榜发现是 rk8，但这已经不重要了。看了个偷跑的民间榜，因为总排名前排的人今天基本都没打好，前五没变，我还是 rk3！感觉不太会描述那种激动的心情，反正大家想象一下就可以感受到了！

听讲题，A 反正就是那样，和出题人想的没区别。B 是 siqi 出的，好像主要错在我觉得要给 u 传 S 子集内传所有点精确值，需要有至少 2^{\left \lceil \log |S| \right \rceil} 个节点同时知道 S 内所有元素精确值了，但其实可以任意将 S 内元素排列为 a_0,a_1...a_{k-1}，\forall 0 \le i < k，只要有任意 2^i 个节点知道 a_i 的值就可以了。然后我在这里失之毫厘差之千里了，加上这个优化直接就是正解了！C 好像确实想的没一句真话。

感觉今天果然被交互和通信题爆飞了，但可能其他前排选手压力太大也没打好，所以最后苟住了。

day2 晚上背了很久自我介绍。第二天答辩，自我介绍应该背得还挺顺利，论文答辩事后来看因为有点紧张语速太快了，导致最后讲得也太快了没恰好贴到时限。提问环节被问了一个奇异搞笑问题，但我没听懂他想问什么，最后有点尴尬。最后没有意外 1234，进了。

稍微谈谈这场国家队选拔的结果吧。首先当然是有一些想进的人最终由于种种原因没进，感觉名额只有四个，确实是如果水平没有明显超一流的话说到底要看运气。感觉我理解中（或者说我认识的）的很有实力的人就远不止四个啊！但也没办法了。不过既然也都是集训队了，其实没进倒也不算是伤筋动骨，既然有书读了，未来的机会还很多（比如 xcpc，或者也不局限于算法竞赛），肯定可以赢回来的！另外我还注意到今年也有很多现在高二的同学在几场比赛取得了非常好的成绩，但其他几场或许是因为经验不足打得不太行，感觉有点像是去年的我。那么，这是否又会开启下一个轮回呢？

然后再来谈谈我的未来吧。我写到这里时发现本文介绍比赛的内容实在有些太多了，说白了这是因为现在我去回忆过去，只有比赛的记忆仍然无比清晰，别的都已经模糊了。虽然我去上预科的一部分目的也是觉得把精力全都放在一件困难、失败了就几乎没有收益的事上，会导致压力太大反而做不成，但最后结果还是事实上我对这件事无比看重，以至于其他的回忆相比之下都褪色了。我曾觉得我对什么事都称不上太 “热爱”，但或许也未必。

未来会是什么呢？最近的最明确的未来是首先得把 IOI2025 打完，然后得学学预科的课。或许这两件事就够我忙的了，再远的未来可以等到以后再想。

但当然，这个等待不能是永远，我也不可能打一辈子算法竞赛。但应该，先往前走走，我会逐渐知道答案是什么的。没什么好担心的，日子还是像以往那样，不会太好也不会太坏。