NOI 2024 游记

省流：$5+100+100+100+64+90+100+20=579$。 一年前，我在 NOI 赛场上折戟沉沙，一年后，我在我跌倒的地方爬起。我已经不再是以前那个我了。 #### UNR DAY0 笔试，好多坑啊。 差点就 $99$ 了，还好听到有人在叫，于是检查了一遍，查出来了。 #### UNR DAY1 看完 T1 觉得很抽象，会不了一点，然后简单思考了一下，发现只需要操作长度为 $2$ 的区间即可，然后简单感受一下，直接从后往前用一个堆维护一下即可，$7min$ 通过。 然后看 T2，刚开始转化错了，转化成了 $(x^{-1}+x+(a_i-2))$，然后觉得不可做，还好发现及时，于是变成了算 $\prod_{i=1}^{64}(x^{-1}+x+(2^i-2))^{a_i}$。 直接爆算 $\prod(2^i-2+x)^{a_i}$ 复杂度是 $O(n^3)$ 的，考虑利用 $2^i$，发现式子可以写成 $(x^{-1}+x-2+2^i)=(x^{-1}(x-1)^2+2^i)$，从大到小乘复杂度就是 $O(\log^2 p)$，前半部分再写一个线段树，复杂度 $O(n\log n\log p)$。 于是写写写，交上去发现 T 了，原来是线段树常数太大了，思考了一下，果断换莫队，然后就过了。 然后看 T3，简单观察一下，显然是建 DFA，然后暴力跑匹配，现在需要做的是加速匹配。 然后发现钦定重链是最上面那个元素往前走的状态即可，这样不用显示建 DFA，链剖之后是一棵树，所以还要求一个 $k$ 级祖先。 复杂度 $O(2^nm+qn+SA(nm+L))$，为了方便，我先把除 SA 的部分写了（其实并不长），此时过了 $3$ 个多小时，然后开始写 SA， ~~结果不出意外的写了 40 分钟，果然我是 shaber。~~ 终于在 $4$ 小时过一点的时候通过了 T3。 一看：人均 AK 场啊，大家多太恐怖了。 突然发现自己的 SA 太慢了，跑极限数据有概率被卡常（没想到吧，我 SA 写的是倍增完两次基数排序的那种），想再交一发，结果一看，发现再交一发我罚时就高了，就不是 Rank 1 了，~~于是心一横，干脆不交了。~~ 不过 DAY1 官方数据还是 AK 了。居然只有两个人 AK，据说 T3 一堆假做法，标算是 $O(n^2m\log m+SA(nm+L)+qn^2)$，不过实质是差不多的。 后来想了一下，发现我建 DFA 的时候可以暴力进行第一次匹配，这样子复杂度就变成了 $O(\phi^nm+qn+SA(nm+L))$，其中 $\phi=\frac{\sqrt 5+1}2$，不过不重要了。 最后只有我和 hos AK 了，看来不能太信任 pretest。 #### UNR DAY2 看完 T1 果然还是不会做，于是想了一会儿打算先写一个暴力试试，结果还没动手写，想了想 dp……咦，好像会了。 于是速通了，整个过程大约花了 $20$ 分钟。 然后看 T2，第一眼想到二分，加点剪枝 pretest 能跑 $80$ 分。 然后看 T3，想了一下，感觉挺可做，突然想看一下榜，发现有人 T3 已经 $100$ 了，又想了一下，想出了一个 $O(q\sqrt{n\log n})$，看看数据范围，好像能过！？ 于是打算开冲，突然想想 T2 这会儿还没拿到比暴力高的分，要不再想想。 于是想了一下线性的做法，想了好久，突然发现四分树查询好像是 $O(C)$ 的，其中 $C$ 是周长。 那是不是可以四分树上二分解决？但很快就叉掉了，但很快又想了一个，先倍增，然后 $2^i$ 分一块（为了方便，不妨假设 $n$ 是 $2$ 的整数次幂），然后每次把可能的那些块加进来，然后把 $i$ 减小，可以证明复杂度是 $O(n)$ 的。 然后写了一发，结果常数贼大，不过能过 $n=8\times 10^4$，有 $60$，算了不管了。 然后到了大型唐氏现场，我并没有去思考倍增能不能换成常数更小的分治，而是直接把 $n$ 不断增大直到其为 $2$ 的整数次幂，于是常数就原地起飞了。 然后去写 T3，此时其实只剩下了不到两个小时，不过好在我 T3 思路十分清晰，大致就是询问分块，然后大力单调栈处理，细节很多，写了很久、调了很久，但总算在比赛结束前调完了。 于是拿下了，看到 T3 有一堆 AC 的，我以为大家都秒了。 赛后发现，只有我 $100$，FXT $70$，其余的都 $\le 40$…… 去问标算，标算居然是 $O(n\log^2 n)$ 和 $O(n\sqrt n)$，~~不过没关系，我实际跑的比标算快。~~ 然后去看了看 T2 题解，发现我只要把倍增改成两维交叉分治就行了，感觉自己糖丸了。 最后居然混了个 UNR RK1，~~是不是我 NOI 要没 RP 了。~~ #### NOI DAY -1 报道日，居然下午才拿到徽章，差评。 定了一百个徽章，一天之内换出了 $\ge 30$ 个。 （好像还欠了 by_chance 一个徽章） 下午跟 ZJ，FXT 打球，观看 ZJ 大战衢州二中 OI 教练。 #### DAY 0 开幕式，又是喜闻乐见的 dzd 讲话时间。 > 我已经牺牲自己女儿好多次了。 > > 我杜子德被全国人民吊打。 差评：怎么没有波特表演。 下午笔试。 嗯……出现了一点类似 Zayin 的行为，据说是去年对应编号的选手的作答（我还以为是 std），不过我很素质，全程是自己做的，据说有人被误导了。 pzr 笔试不是 $100$，没关系，差 $1$ 分而已。 qbf 也没满分，据说就是过度信任上一届的对应选手导致的。 不知道谁在说 xqw $98$，最后 xqw 亲自在我面前辟谣。 然后又去跟 ZJ，FXT 打球。 晚上居然没有失眠。 #### DAY 1 早上 $5:20$ 醒来，然后睡不着了…… 快进到进入考场。 我的策略是：先用尽量短的时间拿下 T1，然后后两题自由发挥。 结果一看 T1：咋办啊，根本不会啊。 想了一想，$p_i=j$ 当且仅当 $i$ 在 $A$ 中的位置集合 $=j$ 在 $B$ 中的位置集合。 于是哈希一下，外层用一个 map 维护即可。 然后写写写，很快写完了，过了大样例，然后又到了喜闻乐见的差评时间： 打开 Self Eval，测了一下，结果…… CE。 于是举手向监考员求助，监考员来说是我个人的问题。 为了验证自己的猜想，我先挪走了 set.cpp，然后此时显示找不到文件，然后新建了一个 set.cpp，内容为 `int main(){return 0;}`，结果交上去还是 CE。 于是又向监考员求助，终于，过了一会儿，传来广播：Self Eval 配置错误了。说真的，当时想骂人。 不管了，先去看 T2，怎么是交互？ 刚看完：直接分治不就行了。 再看一眼：怎么只能拿 $20+$ 分啊。 于是先想一下交互库应该如何自适应，发现相当于找出每次询问的点集的一个最大独立集，然后递归下去。 于是一种想法就是每个连通块都是一个团，这样每个连通块的最大独立集都是 $1$。 想了一想能不能 $>1$，想了半天都没构造出来。 于是直接写了个划分 dp，写完一看，发现距离 $100$ 的次数差得挺小的，大概只有 $\le 50$ 次，再一看……只有 $70$ 分左右，瞬间火了。 这个时候 SelfEval 能用了，于是去测了一下，wtf T1 只有 $80$ 分！？ 思考了一下，可能是 map 常数太大了，换成 unordered_map 就过了。 其实当时我还有一个备用方案：把每个的哈希值随机映射之后加一起，看两边是否相等，但既然哈希表能过那就不用管了。 于是又去给 T2 调调参什么的，搞到了 $91$ 分，此时还差 $3$ 次。 然后我开始胡思乱想了，感觉是要构造一个最大独立集 $>1$ 的图，结果想了半天都没想出来，又想了一下，发现好像优化出来了，小的时候枚举划分成多少组就行了，跑了 $O(1)$ 秒就跑出最优划分方案了。 于是前两题都拿下了。 此时还有两个多小时。 然后看 T3，第一眼：这不是差分约束的板子吗？随便写写就可以得到 $O(n(n+m))$ 了，拼一个 B 可以获得 $64$ 分。 然后就 GG 了，虽说差分约束可以轻松拿到 $64$ 分，但该做法无法优化到低于 $O(n(n+m))$，于是就 GG 了。 于是开始想怎么优化，果然，想了好久都没有想出来。 还剩一个小时的时候我 T3 还是 $56$ 分，其实这时我并不想去写 B 性质，只不过不想睡一个小时，于是就把 B 性质写了。 还剩一分钟的时候突然感觉我 B 性质有个地方写错了，心想：算了，就 $8$ 分而已，不要也罢。不过最后还是过了（后来想了想好像没问题）。 出场之后突然感觉 $256,264$ 天差地别，刚才谁说 $8$ 分不重要的来着？ 刚开始说队线 $264$，我也感觉周围有一万个 $264$ 的和十几个 AK 的，后来慢慢降到了 $230$ 左右。 好像 GD 只有我和 Bronya 是 $264$。 赛后才知道大家的 $64$ 分基本都是一种贪心，就我写的是差分约束，后来随便想了想，发现那个贪心优化到 $O(n\log n)$ 有一万种做法，欸……感觉最错误的地方就是一开始就往差分约束上想。 然后听 ZJ 讲述的他那紧张刺激的过程：$11:00$ 分数还是两位数，剩下两个小时直接冲到 $264$，不得不说我也为他捏了把汗，希望他 DAY2 别干这种危险事了。 然后又是打球时间。 #### DAY 1.5 社会活动喵，社会活动谢谢喵。 感觉有点抽象。 下午先在自习室把几道我做过的比较好的数论题过了一遍。本来想跟 ZJ 打球的，结果传递信息出现了一点错误。 晚上本来想去看一下 Alex_wei 的数论专题，点开一道题，发现不会，于是就开摆了。 #### DAY 2 $3:58$ 醒了，然后一直躺倒 $7:00$。 快进到进入考场。 开 T1，一想，感觉没有任何思路啊。 于是决定先打表，写了个 $O(nm)$，突然发现答案好像很小的样子，于是写了个搜。 结果 $8.9\times 10^5$ 的样例也搜过去了。 加了点优化，直接冲到 $8\times 10^6$，拿下 $90$。 感觉已经很高了，于是先去看 T2，感觉这是最正确的决定。 然后去看 T2，结果刚开始题目看错了，看错后的题目非常抽象，大家就不用关心我是怎么个错法了。 然后就像，要是题目是条件改一下（改成看对后的题意），那这就是水题了。 想了一会儿，没思路，于是再读一遍题，才发现自己看错了，于是就秒了。 大致就是观察一下，每次冲刺之后的 $\min(d_x-h_x)$ 均为冲刺后的那个点的 $d_x-h_x$。于是直接设 $f_x$ 表示点 $x$ 的答案，然后变成了如何快速转移。显然有很多做法，为了让代码简洁明了，我写的是离线线段树合并，然后又到了大型唐氏现场： DFS 过程中实现 $[l,r]$ 级祖先的 $f$ 值之和怎么做？ 我：树状数组维护树上差分就行。 别人：直接维护前缀和就行了。 是的，因此我复杂度凭空多了乘个 $\log$（别为我为啥这么唐），不过不要紧，可能是实现优秀，最慢的点也就 $1.4s$，简单卡常一下后变成了 $1.2s$，想必是没问题的。 此时只过了不到两个小时。 又折返回去看 T1，突然一想：我昨天已经比队线高很多分了，实在不行就当是白给 $10$ 分，反正 T2 已经过了，只要花点时间把 T3 暴力打满少这 $10$ 分也没关系，~~毕竟 T2 不会有人分数高于 100~~。 然后看 T3，$O(n+m)$ 判断一个点是否是一类点很简单，拼上特殊性质 A，就有 $20$ 分了，再拼一个暴力就 $25$ 了。 然后我又花了很长时间想出了特殊性质 C 的做法，算了一下，拼一下有 $55$ 分，很赚，直接开写。 先写了 A，又写了 $n\le 1000$ 的 B 性质，因为一些脑瘫问题调了一段时间。 然后开始写 C，感觉 DAY2 如果能 $245$ 那肯定稳了，结果 C 性质写了接近 $5k$，小样例一遍过大样例过不了，手造的数据也能过。为了方便，我打算先调过 B+C 性质。本来想写一个拍，但遗憾的是我连指数级暴力都没写，好吧其实是我太唐了，当时没有意识到我已经 $O(nm)$ 解决 B 性质了，于是也没拍，此时距离比赛结束还有半个小时，我满怀希望的进行调试，一行一行读代码。直到时间一分一秒的过去，我逐渐由充满希望变成了绝望，最后几分钟，我也不想调试了，干脆关掉电脑，默默的看着比赛屏幕的倒计时…… 于是 DAY2 $90+100+20$ 结束了，T3 连暴力都没打满，感觉有点遗憾。说真的，感觉考 DAY2 有一种考期末考试最后一科的感觉，考场上也并没想着像 DAY1 那样拼死拼活去拿分，更多的是想着只要能金就行了。 讲个抽象事：没人过 DAY2 T1。 感觉 DAY2 最重要的决定就是 T1 写到 $90$ 就跑路。 其实回过头想一想，我 DAY2 打得挺唐的，首先是 T2 明明前缀和能做的东西我偏偏用了个树状数组，其次我到底也没意识到我 T3 暴力已经写好了，可以对拍了，感觉使用对拍 $30$ 分钟调出来特殊性质 BC 问题也不是很大。 有点难受，感觉已经吃了一正常好吃的比赛了，所以没吃午饭。 打完之后，就和 $O(1)$ 个人一起打 UNO，结果打到一半冲进来一个抽象人，声称要请 ZJ 队长去讲课，费用 $1500/h$，但他不愿意透露姓名和所在学校，问他，他就说是涟水中专的。 我：离查分不到一小时了，为啥不等查完分再说？ 他：我怕你们坐地起价。 然后他被 FXT 锐评了一波，被 DX 现场开合，最后被用神奇的方法请走了。 感觉查分前的一个小时，是人生中最漫长的一个小时。ZJ 的 $O(1)$ 个人在打一种奇怪玩法的牌，我因为不会规则所以在旁边帮 ZJ 刷《皇家守卫军》，时不时帮大家报一下“距离查分只剩下 XX 分钟”。 然后查分，没挂。 跟着 ZJ 去打球，结果打了一堆非常抽象的球，能上桌并且 ZJ 接不住，用 ZJ 的话说就是用 RP 打球。不会吧，考前 UNR 先把 RP 用完了，然后考试中一点 RP 都没用，考后又把 RP 用完了。要是能用点 RP 在 DAY2 上那就好了。 晚上嘉年华去看了一下，突然感觉没啥兴趣，于是绕着篮球馆转了 $O(1)$ 圈就走了，想起初中一篇的阅读理解，大概讲的是，一个老父亲邀请别人来看电影，但他不看电影，他觉得看电影的这些人对他来说就是一场电影。 #### DAY3 本想参加一下《我与 NOI》，结果走到一半想了想干脆不去了。 回去的路上碰到 ZAK，他怎么两天都 $300$ 啊。 颁奖典礼经典：给银首鼓掌。 然后就是著名的 [虚奇文家长横扫重庆]([JiazhangNews的博客 - JiazhangNews的博客 (qoj.ac)](https://qoj.ac/blog/jiazhangnews))，大家快去点赞，遗憾的是，我没注意到比赛结束后 xqw 家长们拍了个合照。 虽说有点遗憾，不过还好，最后还是苟进了集训队，也算是顺利上岸吧。