NOI2025 游记

· · 生活·游记

前置：2024-2025 这一年

Day -?

7.3 来到绍兴，参加一下 mx 集训。认识了好多很厉害的人，感觉自己水平还是不够高。

Day 0

报到，JS A 队在一个宿舍。好像今年 A 队的构成和去年十分相似：一个高一，一个去年的 Au，一个去年的 Ag，一个去年没进省队。事实上从结果来看，抛开某 rank 51 不谈，和去年的牌子颜色以及相对排名都完全对上了。

晚上和 kevin 一起 vp 上周的 CF，然后从 B 开始就被他 n+1，结果我 F1 做得太唐了，做到 F2 的时候从 F1 改过来改了一坨，调了好久才过。

Day 0.5

开幕式实在太闷了，光忙着呼吸，节目都没看。吸取了某人 UNR 笔试的教训，宿舍一起背了几遍笔试。

笔试之后发现 b6e0 因为过于拘泥于选项的字眼被扣了 1 分。由于神秘原因，笔试之后不能立刻离场，于是和 kevin 一起打贪吃蛇。

试机的时候想了一下昨晚的 G，好像比较 standard。晚上发现 H 也不难，但我一秒看出来关键结论之后不会区间 dp 想了一年。最后看了看板子就睡了，因为忘了怎么写李超树被锐评了。

Day 1

进考场，发现旁边是 zxx，这把高端局。开场刚把三个题看完 zxx 就开始写题了，感觉不是人。

看了一眼 t1 发现大概是 abc F 难度的，遂花了几分钟写完，没有调就过了 pretest。不敢相信这是 NOI t1 难度，于是想了一会有没有坑，发现确实没有。

然后做 t2。好像可以重复的计数有一万种方法，所以为了能做第二问，先没急着写第一问，而是找了一种看起来更有前途的方法，写了一个三方的第一问。

继续分析发现能变成全零的段一定可以从一端开始。这样取出所有极小的非全零段，从左往右依次可以确定唯一的分界点，于是序列不同等价于分出来的段端点不同。这样做就容易三方做第二问了。写完三方只过了 1h，感觉还不错。

后来改成平方的时候写了一些乱七八糟的东西浪费了好久，不过终于在 1.5h 的时候过了。

下面剩下 3h 做 t3，所以目标暂时变成尽可能 AK。这种题一看就先需要一个 poly 的做法。想了一下平方发现直接对着树 dp 是没有前途的。所以考虑转化成给每个点钦定先走左儿子还是右儿子。这样直接考察每一对颜色相对位置带来的限制，发现所有限制都形如“两个点颜色相同/不同”。由于一定有解，直接并查集合并就是对的。

想到上面那个东西好像还挺快的，大概 2.5h 不到就获得了 256 分，然后那个 B 性质把暴力连边改成摊到树上用标记连边就是对的，所以 3h 拿到了 280 分。

当时还觉得自己挺牛，但后面一直在想正解想不出来就开始慌了。毕竟这 280 分都不是很难写，就算是我运气好 3h 写出来了，也感觉一车人 5h 写不出 280 的概率不高。如果有几十个 AK 的那我就完蛋了。

出了考场稍微放心了一点，虽然确实有不少 280，但 >280 是很不平凡的分数，所以 280 尽管没有很大的优势，至少也不是一个劣势分数。

好像 js 考得有点寄的，不过感觉大家 Day2 应该都能翻。

晚上和 zhk duel 试图找回做题的手感，但做了一个就做不动了。感觉明天还是得做点题，不然手感就全无了。

Day 1.5

去科技馆和城市发展馆走了一个上午，下午太累了，没去电影。让 kevin 和 zhk dueal 3200，随到了非常好题目，还好我做过了，没有再吃一遍。

晚上继续 duel 和看板子。其实对 Day2 还是比较忐忑的，主要是不知道题目究竟是难是简单，Day1 这个分数既不能保守也不能冲刺。这是我之前很少遇到的情况，因为我一般 Day1 考得都很糟糕，Day2 就只有冲刺的份了。

Day 2

进入考场，周边没有认识的人。同样先看一遍三个题，没有字符串也没有图论，t2 像是计数，t3 像是 dp，感觉还行。

然后做 t1，没有一眼秒。不过因为有区间反转，而且放在了 t1，大概率是有比较简单的求答案的方法的。手玩了一会看出了只和 110 和 101 有关的结论。写了个暴力验证一下，然后换成线段树就过了。大概做了 1h，实在有点慢了。感觉主要是因为不知道什么原因，写代码的时候手一直是软的，好像下一秒就要瘫倒了一样。

t2 显然无法刻画 f 相同的限制。然后思考容斥。发现钦定 f(P)\cap f(Q) 是能做的。这个玩意转化一下变成一个形如子集卷积的东西，但是权值涉及到 \frac1{a_i+1} 的乘积，直接做就爆了。但这个做法用到了 B 性质，所以应该确实是这么个路子。

仔细思考发现如果记乘积里有多少个 a_i+1=0，那么答案非零的容斥只有在 P,Q,P\cup Q 对应个数相同时才会出现。而且 FMT 就是高维前缀和，可以离散地做。所以按照这个个数分层，每层做一个离散的子集卷积就是对的。

很快写完了 O(2^nn^2) 的做法，然后因为多测 T 飞了。忽然发现子集卷积里设计按位与的部分的权值是 2^{popcount}，所以把这个玩意拆了就不用记与的结果了，然后就变成 O(2^nn)，很快过了。

这个题只做了 0.5h，我觉得是 CF 的 F 或者 G 难度，感觉 Day2 也没区分度了。这下不得不在 t3 获得不少部分分才行了。很快会了单次 check O(n) 的 dp 做法，加一个双指针可以过 40。不过这个写起来细节不少，调了一会，大概 3h 时获得了 240。

然后就不会了。直接优化 dp 肯定不行。然后又想贪心等等看看能不能过数据随机，总之就是各种尝试，一直到 4h 的时候还啥也不会。这个时候我又慌了，因为数据随机这一档分有 30，如果 256+270 是比 280+240+5 高的，那么就算是没什么人 AK，如果大家都会 270，我一样得寄。

所以我开始不择手段地试图获得更多分数。猜了一些结论，即 check 的时候先把攻击牌打掉，然后防御牌直接假定攻击牌足够多，贪心放去 check。这个显然是错的，但是忽然意识到如果攻击牌比防御牌多很多，那么这样是十分有道理的，因为限制其实更多的针对于防御牌本身，而非攻击牌。然后 C 性质是只会把防御牌变成攻击牌，所以用暴力 dp 计算前若干次询问的答案，后面的用这个假做法。

然后写完了发现可以过 AC 性质的大样例，所以放到 selfeval 上测一下，结果过不了那个点。但这个时候只剩下 5 min 了，也没时间思考了，就把前面暴力的界开到了 500，然后就变成 45 分了，也不知道为什么。

当然赛后发现这个思路继续思考一下把攻击牌的限制加到后面那个 check 里面只关心上界就是正解，代码写出应该差不多（应该比 std 简单不少），不过已经不重要了。

考完之后仍然心有余悸，害怕有很多人会 >=70 分。不过问了一圈发现甚至 t2 都不是平凡的，而且 t3>40 也不容易，这样应该是没有问题了。

查分之后确认了排名大概是 rank 5，应该说已经远超我的预期了，所以还是比较满意的。比较遗憾有一些一直一起学的同学没考好，希望他们之后一切顺利。