NOI2025 游记

max0810 · 2025-07-19 12:07:55 · 生活·游记

推荐在 cnblogs 里查看，因为洛谷加载不出图片。

来自高一 D 类选手的游记。

前情提要：NOI2024 摆烂记 - max0810 - 博客园，去年的 NOI 还有今年的好几次大考我打的都很烂，所以希望这次 NOI 不要像以前这么唐了。

Day -?

因为省选我不知道我在考场上干什么没有进队，于是申请了 D 类名额，并且通过了审核。

Day -1

报道日，上午坐飞机到绍兴。一下飞机就看到了巨大的 NOI 牌子，还有很多免费的食物，好评。

然后因为没有带伞所以被小小的淋湿了。报完到，去宿舍放东西，换徽章。因为 WC2025 的时候来过，所以没有进行参观之类的活动。然后就和 H_W_Y 去打羽毛球了。（羽毛球场没有空调差评，不如广二了）

晚上吃完饭，到了经典德扑环节。我，良心WA题人，未来姚班zyl，还有一些人前往自习室打德扑。不得不说自习室打德扑是真的爽（

然后在自习室很快就有很多人加入进来了，最多的时候加到了 10 个。最后小小宣传了一下德扑群聊。

Day 0

早上开幕式环节，看到了极其抽象的小品和舞蹈，还有听 dzd 发言。

下午试机，然后发现因为考点在学校外面，所以需要提前 1h 集合，体验到了绍兴一中举办比赛的最大恶心之处。（虽然 WC 时知道要提前集合，但是那时候并不耽误我睡觉，而 NOI 就不一样了）

试机依然是 NOIP2024，写了前面两道，然后开始半小时的笔试。笔试不出意外是满分。之后不能提前离场，于是我尝试自己思考一下 NOIP2024 的 T3（一年了完全没补），发现找不到思路，就在手机上查看题解了。

晚上吃饭，发现最喜欢的小龙虾，但这个东西好像吃的人不多，好在遇到了志同道合的 NATO 和 UOB，于是三个人吃了 5 盘小龙虾。

因为第二天是 Day 1 了，所以晚上就呆在寝室里，写了 NOIP2024 的 T3，敲了几个板子。大概在 23:00 睡觉了（指的是睡着）。

Day 1

早上 6:30 起来，有点小困。去外面集合，这下是又热又困了。看 UOB 在看博客，我感觉没啥需要看的，于是就迷迷糊糊的站了一会儿。大概 7:40 抵达考场，发现旁边隔一个位置坐的是 H_W_Y，之后马上开睡。

正常开题，读完 T1 发现应该是简单题。想了个前缀和优化建图的思路，每个点拆成 2d_i 个点，随便连点边就行了。然后因为细节比较多，大概在 1h 过掉了这个题。

继续开 T2，想了一小会儿不会，开 T3，仍然不会，但是 T2 好像看起来可做一点，于是去想 T2。T2 首先尝试第一小问，直接考虑 dp。思考了一些时间发现操作可以分为若干个不交的连续段，每个连续段都是所有数缩到中间某一个数。于是枚举连续段，再枚举缩到哪一个数，预处理后 \mathcal{O}(1) 判断合法，就有了 \mathcal{O}(n^3) 的做法。

然后这个优化我没有细想，第一想法就是换一维 dp 顺序，然后使用数据结构优化，复杂度是 \mathcal{O}(n^2\log n)，不确定能不能过，想先写写试试。写到一半发现直接一个 sort 就行了，不用数据结构，写完一测发现 n=5000 T 了，时限 6s，我跑了 6.8s。

这个时候我感觉不是很好优化，就直接看第二问。然后发现第二问直接用第一问一模一样的思路就行了，有个小 case 需要特判一下（整个区间消完）。写了一小会儿，通过了 90 分。这个时候大概是 11:20。

此时我已经比较高兴了，因为我觉得在 Day1 能获得 190 是比较高的，后面随缘看看就行。先尝试了下 T2 卡常，发现我的瓶颈就是一句 sort，弄了半天感觉卡不动。于是就去看 T3 了。

T3 我都是心态非常放松的去看，发现暴力有 8 分。想了下题目感觉完全没多项式思路，就观察样例，发现包括大样例所有输出都是 2 的幂，尝试去证明，不会。写了个第 i 个询问输出 2^{2n-i} 的程序，发现竟然能通过 8 分的 AB 性质。

这个时候已经是 12:10 了，我感觉可以打个 16 分跑路了。这个时候突然有灵感，发现一个序列满足条件的充要条件是不存在 xyxy 这样的子序列，这个性质非常牛啊，于是只需要枚举所有数对 (x,y) 之后就是独立的了。分类讨论下 4 个点的情况，任意一个数对要么是没有要求，要么是要求两个点的方向必须相同或者必须相反。因为题目很良心保证有解，于是只需要并查集维护就行了。

于是先写了个 \mathcal{O}(n) 求 LCA 的程序验证正确性，发现怎么 \mathcal{O}(n^3) 过掉了所有 \mathcal{O}(n^2) 的分数？非常牛啊，然后求 LCA 改成 \mathcal{O}(1) 求，拼上 8 分，获得了 64 分的好成绩。最后还剩 10min，没有事情干，在电脑上乱翻东西。最终是 100+90+64=254。

出场自我感觉良好，因为觉得这个分数再怎么也不能拉开太多分差。然后发现有一车 280。

遇到 UOB 询问，发现 UOB 怎么 T3 只获得了 8 分？那不是 Day2 需要翻比较多才行啊。然而 cdqz 高一的好像不太理想。

下午查分，没有挂分。询问旁边的 H_W_Y 分数，结论是“不告诉你”。过了会儿去问 Nityacke，他正常发挥 264，Hanghang 有点小寄，H_W_Y 280 非常牛逼。

之后评讲那肯定是不去的，很显然是打了一下午+一晚上德扑。晚上正常 12:30 睡觉。

Day 1.5

怎么早上 8:10 要集合啊？那我还需要早起？这下完全不如 CQYC 了。

去绍兴城市展示馆参观，看了绍兴市的各种介绍，然后去科技馆玩各种东西。

考虑到来绍兴还没有买纪念品，于是从一个地图上随机摘了一棵树。

下午安排的是看电影，那很显然是继续德扑。晚上还是看了下各种板子，也是大概在 23:00 睡觉。

Day 2

早上起来还是比较困，到考场坐下来后又睡了会儿，甚至差点睡着。

依旧先开 T1，一眼不太会，又开 T2T3，发现有道集合幂级数，依然也都不会。于是就尝试手玩 T1 找性质，玩一堆样例后发现找到第一个 110 的位置就结束了。因为还要判断是否有 101，所以用一个线段树维护区间内一堆东西，写到大概 9:20 通过。

然后应该就是全场区分度最大的 D2T2，题意是这样的：

给定一个长为 2^n 的序列 a_0\ldots a_{2^n-1}，设 S 是一个 \{0,\ldots,2^{n}-1\} 的子集，定义 f(S) = \cap_{x\in P}x，g(S) = \prod\limits_{x\in S}a_x。你需要求出：

\sum_{P\subseteq\{0,\ldots,2^{n}-1\}}\sum_{Q\subseteq\{0,\ldots,2^{n}-1\}}[P\cap Q = \empty][f(P) = f(Q)]g(P\cup Q)

对 998244353 取模的结果，n\le 20

第一想法肯定是容斥，设 f_{i,j} 表示 f(P)=i,f(Q)=j 的结果，设 g_{i,j} 表示钦定 i\subseteq f(P),j\subseteq f(Q) 的结果。于是有 f_{i,j} = \sum\limits_{s=i}^{2^n-1}\sum\limits_{t=j}^{2^n-1}(-1)^{s+t-i-j}g_{i,j}，因为答案是 \sum\limits_{i=1}^{2^n-1} f_{i,i}，所以一个 g_{i,j} 的贡献是 (-1)^{i+j}2^{|i\&j|}。