NOI2026 游记
FQR_
·
·
生活·游记
Day 1
先开 T1，是个简单 dp。写了个时间 O(nmk)，空间 O(m^2k) 的东西。交上去发现全 MLE 了，空间限制竟然只有 512MB。尝试滚动无果后，发现 dp 数组两维有大小关系限制，所以空间可以除以 2。交上去 T 了几个点，优化下内存访问就过了。切掉这道题花了 1h。
然后看 T2 和 T3。T2 发现会存在一个阈值，距离比它小则走过去，否则传送。打了个表发现阈值和最终期望值的函数是凸的，可以直接二分。需要写一个点分树，总时间复杂度两个 log。写了很久，又调了很久。在 3h 时获得了 80 分，决定弃掉。
去看 T3。发现 sub1 是送的，一次询问所有数字即可。对于后两个 sub，尝试随机若干个询问序列，然后选取最优的。但是分数比直接套用 sub1 的做法还低。又思考了很长时间，没有什么进展。
后来受到 sub1 做法的启发，如果已知答案在某个集合 S 内，询问这个集合就可以得到答案。那么可以设计两次询问，第一次用来缩小可行的集合，第二次直接找到答案。注意到第一次询问的集合为相邻质数的乘积（[2,2\times 3,3\times 5,5\times 7,\dots]）是比较优的。获得 51 分。
## Day 2
看 T1。可以用二分变成 01 序列的问题。判定时，先判断 1 的数量够不够，如果够再按照 k 的奇偶性讨论。如果是偶数，则需要补上一个间隔，否则需要补上两个间隔。判定很简单，很快就写完了，测大样例发现 WA 了。
原来 $k=2,3,5$ 需要单独做。没找到通用的算法，于是对 $k=2,3,5$ 分别写了个判定算法。写得又臭又长，越写越不对劲。总共写了 5KB，终于在 1.5h 时通过了。
看 T2 和 T3。发现 T2 是令人欢喜的 ds，T3 是令人厌恶的数数，于是开 T2。
先思考 prufer 序列有没有别的还原方式？有的有的。从小到大考虑每个数，找到它最后出现的位置 $endpos$，再找到 $endpos$ 后第一个没被访问的位置，就找到了它的父亲。
继续思考填 $vis$ 数组的规律，终于找到了查询某个点父亲的方式。需要支持二维平面上的单点修改，以及矩形查询。先写了个树状数组套树状数组，内层树状数组用 gp_hash_table 存储，结果是 TLE 80 分。换成树状数组套动态开点线段树，就获得了 $100$ 分。
此时距离比赛结束只剩 $20$ 分钟了。写了个 T3 的八分暴力。
$100+100+8=208$。
总分 $5+100+(100+80+51)+(100+100+8)=544$。获得高位 ag。
2026 年大满银。我该怎么办。