NOI 2025 游记

kaixinguo · 2025-07-19 13:09:21 · 生活·游记

写一个游记纪念一下 \text{NOI 2025}

Day -\infty

参加 nfls 集训，每次模拟赛排名计算方法由该 Python 代码计算：random.randint(30, 70)

感觉 \text{NOI 2025} 没救了

Day -9

呀，\text{UNR} 笔试忘参加了，后续复现为 95 分

感觉 \text{NOI 2025} 没救了

Day -8

参加 \text{UNR Day 1}，\text{T1} 构造题完全不会啊，\text{T2} 只能看出来模拟费用流 / 反悔贪心，没发掘出更多性质，最终 30 + 56 + 0 = 86 喜提 329 名

感觉 \text{NOI 2025} 没救了

Day -7

参加 \text{UNR Day 2}，\text{T1} 简单题，\text{T2} 和 \text{T3} 只会写几分的暴力，最终 100 + 10 + 4 = 114 喜提 125 名

感觉 \text{NOI 2025} 没救了

Day -6 \sim -4

• 即将前往绍兴（补题 + 摆烂）
• 正在前往绍兴（补题 + 摆烂）
• 已经前往绍兴（补题 + 摆烂）

感觉 \text{NOI 2025} 没救了

Day -3

参加南外模拟赛，80 + 40 + 28 = 168，第 35 名

感觉 \text{NOI 2025} 没救了

Day -2

参加南外模拟赛，100 + 40 + 25 = 165，由于暴力分打得太少，喜提第 50 名

感觉 \text{NOI 2025} 真的完全没救了

Day -1

参加南外模拟赛，\text{T2} 写完矩阵乘法后发现和 \exp 生产函数很像，优化了一下就过了，100 + 100 + 20 = 225，第 5 名

感觉 \text{NOI 2025} 好像也不是完全没救了

下午前去报到，同寝室的 wzh, pa, sdy 感觉都是高手啊

Day 0

参加笔试，提前背了好几遍，没出意外，100 分

Day 1

好紧张，害怕连去年的 Ag 都拿不到了。

开场先看 \text{T1}，发现就是一个最短路，直接开始敲，除了编译错误一遍过，此时比赛过去 20 \text{ minutes}

随后看 \text{T2}，本以为操作的两个数一定 i < j，直接开始敲，测第二个样例发现错了，随后手模发现读错题了，发现仍然是枚举区间进行转移，发现如果为 0 还操作是无意义的，发现区间一定是左侧从外向内，右侧从外向内，考虑枚举剩下的两个数的左边那个，以及左右的大小关系，发现分奇偶性后满足特殊的单调关系，然并卵，发现大的数要减去小的数，所以峰只有一个，且大于两边的数，此时 O(n ^ 3) 是非常简单的，发现条件展开后拆分为：左侧满足条件、峰满足条件、右侧满足条件，而峰需要满足的条件只和奇偶性有关，随后 O(n ^ 2) 就是非常容易的，此时比赛过去 2 \text{ hours}

然后去看 \text{T3}，题目保证有解的常见套路是找出每个解和我选择固定住的解如何互相调整，每个解与一个调整序列一一对应。发现交换左右儿子是难以快速确定是否仍然满足条件的，但是翻转整个子树，从根向叶子调整，是可以调整到所有解的。

考虑什么时候可以交换？第一想法是只有当前子树只存在一个未配对点或不存在时可以交换，写完发现样例 3 挂掉了。

开始找反例，发现如果一个点不存在未配对点，则左右侧的未配对点集合一定相同，如果均非空且非单元素就可以同时交换，改了一下，挂了。

继续找反例，发现不一定是左右侧子树，如果是左子树和右子树的左子树，就没办法判断了，于是考虑 dfs 子树前统计一下之前的同未配对元素集合的点的个数，dfs 子树后加入集合，挂了。

继续找反例，发现首先可能存在祖先和自己的集合相同，与外部的与自己的集合相同归纳一下，发现其实答案就是和不同的集合数有关，测样例，发现对了，此时 100 + 100 + 56 = 256

显然不用每次都 dfs 一遍，只修改祖先，于是 100 + 100 + 80 = 280，此时比赛过去 3.5 \text{ hours}

最后一个半小时冥思苦想没能继续拿分，出考场之前感觉应该是大众分，\text{Day 1} 题目相对简单，分差会比较小，查询其他人得分后好像还算高的（？）

感觉 \text{NOI 2025} 好像也不是完全没救了

Day 1.5

只记得科技馆的机器人那片区域很好玩，电影的放映方式好独特，有一种我就是无人机的感觉

晚上复习了一下知识点最后摆烂了 10 分钟，但是感觉没什么意思就睡觉了

Day 2

比 \text{Day 1} 紧张

第一题输出一下操作序列，容易发现规律，随后用线段树维护即可，此时比赛过去 1 \text{ hour}

第二题发现直接容斥可以 O(5 ^ n)，换一个枚举变量，每次发现有 2 的幂次种情况答案相同，变为 O(4 ^ n)，发现只需要维护 \text{popcount}(i) + \text{popcount}(j) 以及 i | j，类似子集卷积做一下即可 O(n ^ 2 2 ^ n)，发现 a_i 可能为 998244352，而 \text{FWT} 需要做减法，但是根据 \text{FWT} 之前的数组可以发现一个数的子集的值包含的 998244353 的幂次一定不高于这个数包含的 998244353 的幂次，于是 56 分到手，发现不需要记录 \text{popcount}(i) + \text{popcount}(j)，直接初始值上改一下即可，100 分，此时比赛过去 3 \text{ hours}

第三题发现直接贪心可以 35 分，此时比赛过去 4 \text{ hours}

最后一小时尝试思考第三题 40 分，然并卵

参加活动和颁奖典礼，\text{Au} 线 571，拿了 \text{Au} 算是挺意外的吧，这次确实是超常发挥了