NOI 2026 游记

· · 生活·游记

7.6

做了两天用 O(\frac{(n+m)m\log w}{w}) 的复杂度过了 ULR 的 B，信心大增。

7.8

坐高铁前往青岛参加核桃的赛前训练。

7.9

第一场模拟赛 Day 1，三个小时通过前两题，之后做了半天 T3 获得 46，最后 T3 套了一个点的数据获得了 56。

总分 100+100+56=256，rk4/4。

下午补了 T3，又复习了一下笔试，准备明天的 UNR。

7.10

第一场模拟赛 Day 2，一个小时通过第一题，之后做了一个半小时 T2 毫无头绪，花了一个多小时写了 T3 前两个 sub 和乱搞获得 80 分，最后给 T2 打了个暴力并尝试特殊性质无果。

总分 100+25+80=205，rk7/9。

两天总共 256+205=461 分，rk4/4，获得了 50 元麦当劳代金券。

晚上打 UNR 笔试，手速比较快获得了 rk4。

回酒店终于把模拟赛 T2 过了，点减边容斥太难了。

7.11

构造交互专题没去听，打 UNR Day 1。

开场 30min 过了 T1，之后做 T2 很快发现可以枚举每块颜色数并转化为 l_k\le n\le r_k，但是忘记可以写成 [l_k\le n]-[r_k<n] 了，导致想了两个小时也只会对着 l,r 一起 dp 的 a_i=0 的 O(n^6) 做法，并且细节巨多完全调不出来。

然后看 T3 字符串也完全不会啊，只能拼点暴力，最后 100+30+10=140，rk133。

今天确实遇到了两个不太擅长的题，不过策略也没什么问题也没有看错题什么的，该拿的分都拿到了，只能说水平确实如此吧（忘了那个 trick 真没办法），希望明天努努力能打到 rk50。

7.12

UNR Day 2。

T1 卡了好久，想了若干假做法后终于意识到了关键结论，2h 的时候才过。之后先去打 T3 暴力，很快得到了 20 分，尝试卡了卡 n^2 的常数过掉 10^5 失败了，最后留了两个小时做 T2。

思考了一会儿感觉毫无头绪，后来发现可以很容易的刻画出来一个生成树的合法的根的位置，然后就写了个 O(3^nn^4) 过了 n\le16 的 52 分，最后拼了一下仙人掌然后发现没时间了没做出来。

总分 100+52+20=172，我以为打的一般结果似乎还不错？竟然刚好是 rk50！（后来好像变成 rk49 了）

加上笔试是 100+140+172=412，rk66 算是高分 Ag 吧。

感觉 Au 似乎并不遥远，我在 Day 1 爆炸 Day 2 也没得到什么非平凡分数的情况下都只差了 40 分。

不过正赛区分度肯定比 UNR 大很多，应该也不会像 UNR 两天 T1 一样随机区分，只能说顺其自然吧，正常发挥高分 Ag 肯定没问题。

7.13

听说台风好像来青岛了，大家都只能在酒店里打模拟赛。

做了半天 T1，很容易看出是轮廓线 dp，但是以为 O(4^nn) 过不去，一直在想怎么把状态优化成三个，想了两个多小时还是不会，放弃了。

之后做了半天 T2，差不多会了，然后没调完，于是模拟赛获得了 0 分。

下午又尝试补了一下 UNR Day 2 T2，发现我赛时太蠢了，根本没意识到转移是一个连通块，所以我的做法复杂度实际上是 O(3^nn+2^nn^4) 的，稍微优化一下就可以做到 O(2^nn^3)，能得 64\sim82 分，但是卡了一下午都没卡过去。。。

7.14

怎么又能去学校了，专题是 dp 组合计数，题目似乎都非常困难，不过听懂了一部分。

晚上终于把 UNR Day 2 T2 过了。

7.15

第三场模拟赛 Day 1，半个小时过 T1，T2 看错题想了一个小时发现暴力都不会多少分，之后看了半个小时 T3 也完全不会。回来重新做 T2，根据经验，很大概率是看错题了，重读了一遍终于发现只能交换相邻的，然后想了想感觉随便贪心就行了，三个小时多一点的时候过了 T2。

之后又想了想 T3，还是啥都不会，打了个 p=0 的 O(n\sum k) 暴力，不知道为啥 WA 了，只有 20 分。

总分 100+100+20=220，rk24。

晚上打了会儿 qoj 模板训练赛，打完 PAM 就睡了（下下个就是 Manacher）。

7.16

第三场模拟赛 Day 2，T1 想了一百万年才想到 Manacher，将近三小时才过，之后就 T2 T3 都想了会儿，完全没思路，打了点最低档暴力。

最后总分是 100+12+10=122，rk37。

晚上又打了一会儿模板训练赛。

7.17

感觉比较累，就没去听贪心专题，几乎打了一天模板训练赛（虽然基本上都是打一会儿休息一会儿）。

后来发现贪心专题十道题我做过五道，那确实没必要去听。。。

7.18

上午又打了几个模板就去报道了，和我校三个高二学长住一个寝室（529），欢迎大家来面基和交换徽章。

下午打了最后几个模板，晚上又随机看了点题就睡了。

7.19

早上六点不知道为啥醒了，感觉很冷，可能是空调温度有点低，过了一会儿又睡着了。

7:20 闹钟响了之后起床，早饭感觉一如既往的难吃，然后在寝室背了会儿笔试就去开幕式了。

路上和场馆里又做了两遍笔试（洛谷有题），一次 126 一次 127（满分 128），似乎都是看题不仔细或者做得太快了，看来下午得认真检查几遍。

笔试 RP++！

笔试成功获得 100 分，试机写了个 10^8 乘法取模要跑 0.46s，又写了个 NTT 好像也不咋快啊。。。

晚上又稍微复习了一下做过的一些题和一些套路，思考了一下明天的策略，22:00 睡了。

7.20

早上三点不知道为啥醒了，感觉热死了（因为昨晚把空调温度调高了一度），过了好久才睡着。

6:30 起来感觉状态还不错，早饭似乎除了馄饨没啥能吃的，随便吃了一点。

Day 1 RP++！

8:05 开题，快速阅读了一遍三道题目，感觉 T1 还算常规就正常先做 T1。

想了十几分钟之后发现可以很简单地刻画出一个 dp，转移分为包含和不包含两种情况，直接前缀和一下就是 O(n^2k) 的，写完之后大概 8:40，获得了 76 分。

之后卡了半个小时常，9:10 通过了 T1。

开 T2 之后发现是一个很套路的东西，很容易将问题转化为求解所有点到某个点的最优期望步数的平均值。将这个值视为变量，所有点到该点的最优期望步数的平均值是一个凸函数，与 y=x 有且仅有一个交点，所以可以直接二分。

然后就推出了一个二分之后判定的式子，需要求出到点 x 的距离 \le k 的点的个数和距离和，思考了一会儿没想出来应该用啥数据结构维护（我怎么忘记可以点分治了。。。）。

然后就决定先写个暴力看看，写完之后在 9:40 就得到了 50 分，然后去上了个厕所换换脑子，回来继续观察有没有更多的性质。

猜了一个相邻两个点的答案差不超过 1，但是当时忘记可以考虑组合意义了所以没有很快想出来怎么证，然后就放弃了这个思路，转而观察答案的大小。

对着式子又看了一下之后，我发现因为深度是连续的所以答案不会超过 2\sqrt{n}，这样直接换根 dp 维护就可以做到时空复杂度 O(n\sqrt{n})。

但是我算了一下空间发现远超 1GB，所以只能得 80 分，但是此时已经 10:20 了所以我有点急，决定先去看看 T3。

看了二十多分钟 T3 感觉基本没有思路，只是对于 sub2 有一定的思考，于是决定先回去把 T2 80 分写了。

写了一会儿，调了一会儿，大概在 11:10 获得了 80 分，但是仔细想了一下之后发现答案上界实际上是 \sqrt{2n} 而非我之前分析的 2\sqrt{n}，精细实现了一下发现可以刚好开的下 500010\times901 的 unsigned short（因为我求 LCA 写的是 dfn 序，占了点空间，本地空间 1022MB），测了一下 selfeval 竟然直接 2.9s 过了！！！此时大约 11:25。

但是理论上用 unsigned short 可能导致 n=10^5 挂分，但是我思考了一下感觉再加 vector 有点太麻烦了，于是决定相信数据直接开 T3。

最后还剩下一个半小时的时间，我先很快得到了 10+3+3=16 分，然后思考了半个多小时比较有道理的做法但是并没有想到比较优美的构造。

最后四十多分钟就开始拼分，写了询问 2\times3,3\times5,\dots,53\times57 之后二分两次，再询问最终的集合获得了 sub2 19 分。然后我也不知道出于什么原因特别想拿到最后一分，就把二分改成了三分，调了好久边界终于通过了 sub2。

最后就只剩二十分钟了，我尝试在 sub3 也询问刚才的那个东西，然后取出所有合法的数之后再询问整个集合，不知道为啥调了好久，获得了 12 分。

然后尝试再利用多出的两次询问问些别的，进一步缩小可能的答案集合，但是好像写挂了，最后还是 12 分。

最终总分 100+100+42=242，虽然 T3 并没有得到比较高的分数，但我感觉还挺不错的，毕竟是今年难得一次在正赛发挥出真实水平。

下午查分前一直很紧张 T2 会不会 WA 或者 MLE 挂分，不过最终没挂，开心。

听说队线在 250 到 260 的样子，那感觉有机会 Au 啊。

7.21

社会实践，去的是上次研学刚去过的海军博物馆。

早上被宿管叫醒，困死了，赶在发车前上了大巴，然后到了之后在车上等了一百年才进去，进去没多久就出来了，真唐。

然后又等了一百年才等到大巴车，一点多才到学校，感觉又饿又累。

吃完饭回到宿舍感觉有点头疼，疑似是起的太早+轻微中暑，就躺床上休息了一下午，晚上吃完晚饭又睡了一会儿，终于不疼了。

晚上又复习了一下，22:20 睡了。

7.22

6:40 起的，这次睡得挺好晚上没醒，不过似乎又有点头疼，但是应该问题不大。

Day 2 RP++！

8:00 开题，发现没有交互了，也没有我擅长的构造，那就还是正常做。

T1 是比较常规的题，很容易想到二分后转为判定问题，但是要分讨很多情况。思考了一会儿我决定写个 dp，多记一维 0/1/2 代表减少了几个 -1 段，写了一百年终于过了小样例，但是大样例似乎在 k=2,3,5 的时候都不对。

此时大约 8:50，用 selfeval 测了一下发现 k>5 的两个点 WA 了一个，感觉可能是写错了一些小问题，但是调了半天没调出来。

之后我决定直接把 k=2,3,5 的情况都改对，可能 k>5 就也对了，但是改了一百年似乎没改明白，于是决定写个 O(nk) 的 dp 拼上去。

调了好久，终于在 9:30 调了出来，然后 selfeval 测了一下发现获得了 85 分，发现是刚才改 k>5 的 dp 改错了没有完全还原回去，又改了一下变成了 95，只有 k>5 的 16 号点 WA 了。

又调了十几分钟，还是没发现哪写错了，决定放弃这 5 分开后面的题，这时候大概 9:50。

开 T2，被 Prufer 序列吓住了，想了半个小时感觉毫无思路，决定去看看 T3。

T3 倒是很显然是树上 dp，想了一会儿暴力发现连 O(2^n\text{poly}(n)) 都不会。之后尝试把集合变为转移时的两种决策，发现实际上可以记一个两维的状态，dp_{x,j,k} 表示 x 子树内有 j 种颜色需要与祖先匹配，有 k 种独立的颜色不需要匹配。思考了一下发现因为不同状态要么 j+k 不相等对应子树内颜色数不相等，要么 j 不相等对应祖先匹配的集合不同，所以不会算重。

然后我分析了一下转移，发现实际上是要转移到 [max,sum]，可以用二维前缀和优化，很快就大概想出了一个 O(n^4) 的做法，写完之后调了半天，发现样例输出 5。

但是这个时候我已经有点急了，发现实际上根本没想清楚，因为即使不在集合中的点也可以与祖先匹配，然后我就加了一种转移，但是这样就算重了。

此时可能已经 11:50 甚至 12:00 了，我非常着急，但是尝试了半天仍然没有找到修正的方法，于是只能放弃这个题去拼一点暴力。

T2 暴力 20 分是简单的，写了个 O(nm\log n) 的 priority_queue 还原树直接过了，想了一会儿发现 a_i<1000 也不难，但是需要分好多种情况，写了半天发现 WA+TLE 了，但是没有样例所以根本没法调。

这个时候已经 12:50 了，我意识到今天彻底爆了，完全慌了神，最后尝试把 T3 的 dp 改成 O(2^nn^4) 发现也不对，然后写了个 n\le8 的暴力也没写完，于是就 95+20+0=115 遗憾离场了。

出场后发现确实爆了，很伤心，不过 Ag 肯定还是没问题。

下午查分发现 T1 挂成 85 了，最后总分就是 100+100+100+42+85+20+0=447，获得了 RDFZ 倒数第一。

晚上出榜了，总榜似乎是 170 多名的样子，去不了 CTT 了 /ll

7.23

早上九点多才醒，洗漱完之后到文艺汇演就 10:10 了，不过还是看到了很棒的节目。

下午颁奖，看到很多平时模拟赛没有我厉害或者和我差不多的人都获得了很高的分数，也看到很多 Day 1 比我低的人最终都获得了 500 分以上的分数，但是又看到高二学长 fast_photon 和 bunH2O 因为 Day 1 的失误遗憾获得银牌，不得不承认 OI 很大程度上就是一个抽奖游戏。

这两天我一直在思考如果我不去做 T3 而是拼 T2 暴力或者冲 T2 正解会怎么样？似乎肯定会得到更高的分数，甚至可能接近或达到 Au 线。

很难过，但是场上我就是那样决策的，这已经成为了事实。可能目前我在遇到难题的时候确实还没有办法稳定得到自己应该会的分数，很容易就会被吓到或者像这次一样被 T1 影响了心态。

这次 NOI 的题目似乎都不是我擅长的，但是真正的金牌选手应该做到不管考什么类型的题都能得到较高的分数，所以在接下来的一年里，我应该补全我的短板，尽可能做到这一点。

这个赛季结束了，我为这个赛季画上了一个不完美的句号。还有一年，我也将成为正式选手，我还有很多任务需要完成……

下个赛季继续努力！