NOI2026 游记

IvanZhang2009 · 2026-07-23 20:52:51 · 生活·游记

感觉比省选简单多了，有感觉吗？

省流：100+100+100+73+100+100+88=661，rk8 拿下！

7.18

入住前发现怎么不和学校同学住，吓哭了。

蟠桃 sxz！！

晚上吃了一下学校的饭，恶心死我了，直接让教练给我送了四桶泡面。

睡觉的时候感觉还行，可能前一天睡得超级晚，比较累了，轻松睡着了。

7.19

五点半醒了一次，偷看一眼世界杯季军赛，发现二十分钟 2:0，吓死了。然后又睡了一会。

世界杯比赛快结束的时候自己醒了，一看群发现两个舍友都三点钟醒着？cjy 声称 ycx 的翻身声音太大了要换宿舍，但是我这一天受到的影响比较小也没说啥。

然后看了一会儿世界杯文字直播，从 4:3 看到了 6:4，彻底懵逼了。

上午开幕式感觉很无聊，dzd 声称让 ccf 管理中国足球。然后四个节目有三个小学生节目，何意味。然后拿到了笔试密码条，是 JS-016 好像是先按省队类型排，再和宿舍一个排法。

中午直接泡面启动了。

下午练习赛，进去发现是 WC 的题，难死我了。笔试感觉每年都有 kill $pid，然而每年我都只记得 killall，好像记忆点是杀死不是 kill，那这个终止估计是 kill，就猜对了（好像不应该这么理解，但是笔试题库只有那两个题所以也适用）。

然后做了半天 WC t1 做到笔试结束，结果还是调不出来。然而今年所有比赛的经验都告诉我试机调不出来题是好事，那我当然是欣然离场。我的 WC 难道真的开挂了？？

然后回宿舍睡了一觉，虽然可能不太应该下午睡觉。醒了之后按家长要求去食堂吃了一顿，这次菜还行，饭还是给我恶心死了。然后在楼下找了半天密码条，结果发现教练早就拿上去了。坐在 C27。

晚上睡觉的时候又想了一遍原始对偶，因为我没写过。然后睡不着。开始一边深呼吸一边数数，以为数不到 100 就得睡着，结果还是数到了 138，然后急眼了不数了。但是自从今年学会了“睡不着就不用睡”的良好心态之后我大赛前全都睡不着，但是完全不影响比赛状态，所以无所谓。于是我直接摆烂不睡觉，开始复习连通点双变换。想了一会会了点双子图计数，然后过了不知道多久才睡着了。

7.20

早上自己醒了之后发现只睡了六个小时，我已急哭。起床看到阿根廷吃一红惜败西班牙，但是常规时间 0 射门确实难绷。我也许也算是个外行的梅西粉丝吧？

但是关于睡不着这件事情我不慌。去吃了个早饭，又回来宿舍，打了几关回忆之旅，然后去考场了。

我说打不过我还想拿银牌？

然后成为了最早进场的一批。我两天都是 rainbow 查的，虽然最后发现其实 rainbow 坏事做尽。

进去还有二十多分钟，感慨了一会儿，一直在叹气。想了半天比赛策略，最后决定就一个一个做，除非一个题上浪费太久。

结果你又不发密码条？？

打开卷子看到 T3 是交互，有点吓哭。

开 T1 的时候发现放了一个必须记录选了几个区间的计数，吓哭了。其实理论上这一年的训练经验都告诉我我最擅长的就是这种题。也许就是如此导致我有点慌。

很快就发现了结构，感觉状态数得是 m^2k，那这个数据范围何意味。这个时候还没想转移，想了半天感觉根本不会转移。急哭了。感觉考虑上 n 个区间，就完全不知道转移顺序，如果状态上必须记两个 m，那 n 到底在哪里枚举呢？那复杂度至少也得是 nmk 啊，这哪能过？？

开局就敲了个头文件，然后半个小时内啥也没动。再想了一遍转移感觉好像真不会做。然后我冷静一下在草稿纸上写下下 9:30 告诫自己目标是这个时候做出来。

然后我把按左端点顺序插入改成了按右端点顺序插入，这样就变成了对下一个完整覆盖的区间的左端点限制。我去原来可以提前钦定左端点。从这个思路想对我来说会顺利很多。也许是这一年过多的的延迟钦定提前钦定的训练让我在签到题也只能掏出这么超模的做法。

想了一会儿变得完全清晰了，除了一样的区间的处理方法。大概在八点三十几开始写，很快就写完了，但是 k=3 都完全过不去样例。然后我还花时间写了个 n^3 和代码对拍，然后发现问题出在 [1,3],[2,4],[4,4]，先加入 [2,4] 和 [4,4] 似乎我都会算一遍。然后想了一会发现好像可以单独减掉这种情况。

然后 8:52 正确性过样例了，交上去 92，最后两个点顺利 TLE 了。其实我调这个题的速度不慢的，这也许真的是我的优势区间之一：思路清晰之后写代码特别快。

然后开始卡常了。为了方便我的代码里全是 (a+=b)%=MOD; 这种东西。全部改掉之后，又发现数组访问可以优化，如果把 f[i][j] 往 g[x][y] 转移改成往 g[y][x] 转移会快很多。期间我一直以为 TL 是 3.5s，交上去还过了，恰好 2.49s。这个时候已经 9:04 了，但是我实在看不出来还有哪里可以卡常了。虽然已经符合了我 9:30 的预期了，但我不得不开 T2 了。

T2 看上去就不难啊。一定是含根连通块往根走，其它随机。假设含根连通块 |S|=k，那从传送点传到一个连通块内的点的概率是 \frac kn，那期望次数就是 \frac nk。然后加上 \frac1k(\sum_{x\in S}dep_x)。

看上去有点难啊，我把样例的四个分数列出来，发现样例是先减后增的。然后查询单点分数是经典点分治，似乎问题是找到最小值位置，这怎么办。

然后我就去研究差分。设相邻两个分数是 \frac{a+n}{k} 和 \frac{a+b+n}{k+1}，a 是前 k 个点深度和，b 是第 k+1 个点的深度。做差之后分母是 a-kb+n。那显然 kb-a 在实际意义上肯定是单调的，就是看这个值怎么时候变成 >n，所以序列关于深度是单谷的。

那他妈怎么做完 \log^2 了？

感觉点分治和这个二分都比较好写而且是必写的，就开写了。大概 10:00 不到一点就写完了。然后调了半天发现样例 3 过不去，然后我就把点分治改成暴力，还是过不去。然后发现改成暴力不小心把 < 和 \le 写错了，然后暴力就是对的，所以真是点分治写错了。然后我还写了个对拍来调点分治，结果总共又消耗了半个小时，到正确性通过的时候已经 10:28 了。感觉两个题都写的好慢啊。这时候前两个题一起交上去，跑了 96+95。

也就是说我的 T1 还是能在波动范围内跑不过去，而我的 T2 貌似也差一点卡不过去。

这个时候感觉真有点难绷，怎么两坨大的都卡常。

先给 T2 卡常，想了一会发现那个 kb-a 很有东西，似乎至少是 \frac{b^2}{2} 量级了，所以也许二分上限只要开到 O(\sqrt{2n})？然后跑的确实快一点点了，只是我的点分治的 O(n\log n) 还是跑得很慢啊，跟 \log^2 部分差不多了。10:33 交上去 T2 过了，大概跑 2.9s，那可能稳了。

然后去卡 T1。加了个赛前辛苦学习的 barret 发现变慢了，难绷。然后发现加法取模的 if(x>=MOD)x-=MOD; 似乎有点慢，我突发奇想把 int 数组加法取模改成 ll 数组不取模，欸，真的很有效。还把好几个转移的顺序和前缀优化改了一改，最后 10:51 交上去 1.5s，那可能也稳了。

然后开始做这坨超级大的 T3。

这个题也太难绷了。

想了半天质数也不会，怎么说。

似乎要选一个子集让相邻 gcd 两两不同。然后我根本不知道怎么选，感觉能写的做法只有手动干涉第一轮询问。我选择的是询问相邻质数的乘积，这样子可以确定那个质数在哪个区间里，然后把区间里的质数全问一遍。

其实这个做法的第一轮询问已经证明它的上限很低了，要三十多个。但是没办法啊。不会做啊。似乎我赛时也完全没想过让第一轮的个数少一点。

这个做法实现出来之后发现这也太烂了。然后发现质数是不必要的，可以改成相邻奇数的乘积。然后卡卡常，可以从 9 还是 11 开始，最后是 52 个，可以获得 16 分。我在 11:42 交了这个做法得到了 10+16=26 分。哈哈哈。

然后我觉得也就一个多小时了，不得不做第三个包了。那怎么办。刚刚那个相邻奇数乘积的讨论看上去确实很烂，所有非质数不能很好的区分。那似乎只能据此划分等价类。然后后面的策略完全不是我能手玩的，为了尽快获得一个能得分的做法我觉得还是先随机询问吧。然后我写了个第一轮问相邻奇数乘积，然后把候选的数拿出来随机一个子集问，最后再把候选的数全问一遍的做法。这个做法写出来第一版就跑了 122 个。它最优秀的地方在于一切决策都只取决于随机数，我代码里需要实现的部分只要把符合条件的数找出来，所以非常的好写。令人惊讶的是这个做法的初步实现只花了我 10 分钟，我在 11:53 的时候交上去获得了 10+16+36=62 分。长舒一口气，至少算是个好看的分数了。

然后我进行了各种各样的卡常：手动测试第一轮询问问什么，最后的版本是把模 4 不余 2 的数拿出来问相邻乘积，因为这样不会影响相邻 gcd 不一样这件事。也许赛后的一些言论说明可以给所有数都乘一个倍数 p 会让它更优秀，但是我毕竟是没想到，那就不管了。

还有就是手动加入了第三轮询问的随机，让它用满了四轮。我随机子集的方案是每个数以固定的一定概率加入。通过细微的参数调整也让得分稍稍变大了一些。

然后我发现有的我跑的超级烂的点单独拿出来跑效率又很优秀。而时限有很大，似乎这支持我多随机几次找到看上去最合理的方案，而不是只随机一次听天由命。然后我每个方案都改成了随机几百次，取最大等价类最小的方案。

最后我还发现从一个子集中唯一确定的话可以不询问最小的那个数，可以在两个包都省下一次，虽然这没有影响我的 selfeval 分数。中途我还发现似乎它的计算是三个包加起来再下取整。

一直卡到最后的 selfeval 分数是 100+100+75=275。个数大概是质数 51，其它 65。

这个分数到底如何我也不知道，反正前两个题对所有竞争对手来说理应都不难，那就听天由命吧。

出场问到毛花 296，qjm ak，pmd 100+80+100，还有各种各样的消息声称有一大堆 >290。有点难受。虽然大概感受出来很难在队线下，但是这完全不是我预期中的 noi day1。在题目传统没有交互的情况下我理应大幅领先于队线才对。但是今年就是莫名其妙放了两个简单题加上一个超级无敌随机区分题，导致它真的变成一场基本功以上随机区分的比赛，这让我真的十分难受，但是这有什么办法呢？？

和 yrq 打了一个小时电话，聊了一下这一天的感受。

查分还挂了两分，100+100+73=273，因为我的随机是在询问的时候在线随机的，和询问顺序有关。我把固定种子改成 random_device{}() 测了两次，一次 75 一次 72，那就释怀了。

舍友的 T3 分数都很低，看上去希望都不大了。

从出场时得到不低的分数的惊喜到最后发现这个分数其实根本就不高，落差还是很大的。

赛后得知这个分数其实名次是四十名左右，虽然确实在队线上，但是还是对 noi 的出题感到很难受。也许许多比较会做传统题的高手被这个题反向区分遗憾落幕，但也会有更多的基本功不扎实的，实力并不强的选手得益于这个随机区分题偷到一个超级高的分数。但是题已经出出来了，这又有什么办法呢？noi 就是这样啊，果然不能对它抱有特别高的预期啊。

似乎我引以为傲的手速也失去了作用，不仅前两个题做的慢，我的两个小时做 T3 的时间也没有完美发挥。

然后跟家长反馈了很难睡觉的事情，本来也没抱太大希望，但家长声称会想办法解决，我也没太放在心上。

晚上实在是比较累，比较容易睡着了。

7.21

社会实践上大巴前教练告诉我换宿舍的问题正在努力，她得知同校的某同学也有意见的时候就表明这个问题没问题了。

其实参观挺无聊的。一开始路上他们聊天内容全是江苏 A 队得分总和，队线，和要 705 得出什么题。我声称要是出让 qjm 705 的题也许我就要倒闭了。

中午返程的时候实在困得不行睡着了。

下午赖在床上没敢睡。后来去操场上和爸妈打了个电话。我表达了这个分数实在是不高，领先优势很小甚至接近没有，远远低于预期，让我压力很大，非常难受，也对 noi 很失望。后面甚至忍不住大哭一场，感慨为什么到最后训练了一年，区分题的位置还是随机区分呢？从 day1 的结果上看，似乎训练的一年都毫无意义了啊？

后来被开导了一会儿感觉好受多了。又得知宿舍问题已经解决了，爸妈还来学校送了肯德基和杨枝甘露，心情好多了。

回宿舍的路上我不停的告诉自己，不要让一个区区交互题影响了自己的心态。明明 noi 开始前都对进入集训队感到毫无疑问稳操胜券，凭什么因为上了队线反而变得失落呢？

睡觉前和教练聊了半个小时。感觉心态确实好多了。领到了座位号，是 C13。

晚上睡觉确实清净很多，但是也没睡着。好事情是我的脑子基本上放空了，就算没睡着也算是得到了足够的休息。

7.22

半夜两点钟醒了，我似乎执着的认为我在做一个有关长度为 n 的序列的 dp 题，并且一定得做出来这个题才行。后来迷迷糊糊的坚定了一下，day2 前晚上的任务只要是睡觉就行，才勉勉强强又睡过去了。

这天早饭也没吃，去操场上溜达了一圈。我本来在等 cyx 的包放手机，结果等了这个弱智好久，都把手机给教练了，他才慢慢吞吞和 fyx 挪过来。

进场看到三个传统题差点振臂高呼了，我觉得没有交互题已经稳了。

开场以为 T1 是直接排序输出第 \frac k2 大的，因为能过样例 1，没绷住。然后大概给自己定了一个九点钟通过的目标。

然后对着这个想法大概直接就懂这个题想干嘛了，大概就是让两个合理段相邻嘛。然后分析了一下，两个 1 相邻一定可以，相差不到 2 也可以，那两个段基本上没什么可能了。直接做到线性。写了半天根本过不去偶数，发现要特判 k=2。特判了也过不去，发现各种边界都写的不对。最后大概八点半的时候偶数过了样例，我也没交。

感觉奇数太麻烦了，得两个两段相邻或者三段相邻。我分析了半天发现三段相邻似乎也是每段长不超过 2。两个两段相邻也很简单。也是线性。样例一堆 k=3,5 过不去，后来想想这个好像至少得到七段，那还得特判 k\le 5？没想到什么好方法特判，直接写了个二分 O(nk^2) dp 直接通过了这部分。

8:49 交上去发现没过，再一看原来样例也没过，发现边界写错了。8:55 交上去还是没过，再一看原来样例还是没过，发现边界还是写错了。8:57 交上去过了，但是我很疑惑，明明 k=2 写的扫两边双端 set，k\le 5 写的 O(nk^2\log n)，那为什么跑这么快呢？

也算勉强实现了九点通过的目标吧。

然后看 T2 题意有点吓哭。回忆了一会 prufer 的还原才想起来是正着扫。我记得 oi-wiki 告诉我这个做到线性的方法是小于指针的叶子个数最多只有一个。

那这个题看上去只要求一个点作为叶子挂在哪个点上就行了。那我似乎又可以把值域变成 01，只看小于它的叶子有几个。看上去一个点变成叶子的时刻是最后一次在 purfer 出现的时刻。那看上去得变成扫描线右端点单点修改了。

看上去原题维护 pq 相当于现在维护一个 cnt。每次都弹一个叶子，--cnt，然后如果这一位的 a 是小于 x 的点的最后一次出现就 ++cnt。那看上去这个就有单调性了，可以直接二分，只要求单点修改序列 a，求前缀 \le mid 的点的个数。

我去，才做多久就做完了？这他妈不是动态二维数点吗，noi 出这么大的？？？

我决定先写平方，最后写了二分里暴力。很舒服地就写完了，O(nq\log n)，在 9:32 获得了该拿的分。

然后我开始写树套树。原因有几个，首先空间只有单 \log，而且我也不会别的，其次就是这个线段树套平衡树我在正赛写过两遍（虽然两次都被卡常了，但是我似乎忘了这个事情）。

终于来到了我的优势区间！写代码的手速终于迎来了它应有的效果！十几分钟写完了线段树套平衡树。

最搞笑的事情是我在 1.cpp 里调代码，但是不小心在 kapok.cpp 里写的树套树，导致我测了没改的 1.cpp 的正确性是对的，还以为自己一遍写对了。这个时候是 9:48 写完的。

然后很难绷的事情是我调代码又调了很久。看上去我每个题都莫名其妙调了一万年。10:09 才调对正确性交上去 64，这也太他妈难绷了，什么分都过不去，不是我 \log^2 连 2\cdot 10^5 都过不去吗？？？怎么我每个题都要卡常？？？

好像本机随机数据 q=0 跑了十秒。然后做了这些改动：一开始不把所有节点都加入树套树，单独拿一个 treap 出来存。线段树二分只要左子树的 treap 信息，所以如果一个点是根或者右子树那我就不 update。加完这两个就快多了，虽然本机随机数据 3.6s，但是交上去直接 1.5s 通过了。偷过去了，那就不管了！！算你过！！这个时候是 10:28。也就是说我在这么个弱智题上又总共浪费了一个半小时。

然后做 T3。一开始把限制看成了存在一个祖先颜色不同，还以为限制本质上是什么含根连通块，后来发现看错了。

然后看了眼部分分，发现可能得会 \text{poly}(n) 才有救。想了想特殊性质，发现链简直就是弱智（不知道为什么赛后大家都不会），我都懒得写。链的本质就是可以贪心，我们只关心有几种颜色的点的限制没满足。如果新根的颜色和子树都不同，那一个限制都没法解决。否则可以解决一个限制。然后取决于自己有没有限制去加一。

然后去想二叉树。画了一下发现限制的形式是同一个颜色不会是祖先后代，而出现多次因为祖先状态都相同，只要记一次。那似乎也可以贪心最小化，也是只要记子树内的色数和不符合限制的色数。

考虑一下合并。我们记两个子树的色数是 a,b，限制数是 x,y，根的色数是 c，不考虑根的限制的限制个数是 z。忽略 x=y=0 的简单情况。可以发现只有 c=a+b+1 的极端情况是根是新颜色，z=x+y。否则根一定可以解决一个限制，就只要看限制怎么合并了。颜色合并的次数是 a+b-c，所以 z=x+y-min(x,y,a+b-c)。

我去好像二叉树做完了，暴力就是枚举 a,b,x,y,c，复杂度 O(n^5)，好像过不去 200。我 11:10 交上去通过了除了最后一档二叉树的所有链和二叉树。