NOIP 2025 游记

· · 生活·游记

最惊险刺激的一轮！

8:33 过 T1 没什么好说的，这比 CSP-S 还简单。

然后是 T2，转化为计算不合法的情况，发现只有在 m 剩 2 的时候选择了一个 w_i=1 的时候才有可能不合法。

假设应该选 a_k(w_k=2)，实际选了 a_i,a_j(w_i=w_j=1)，那么就满足 a_j+a_i\lt a_k\lt 2a_i，枚举 i,k，j 可以用双指针维护。此时容易做到 n^3。

发现式子可以用范德蒙恒等式优化，然后就做完了。说来也巧，这是集训时我出的那套模拟赛的 T2：

记得这个东西是初二的时候 tzy 讲给我的，印象很深，后来就试着给它出成题。当时赛时很多人直接用 \log^2 卡过去啦，然后就没管正解，如今看还是有些遗憾的。

不过这玩意自己推应该也容易推出，所以我只是吐槽一下当时的情况，嘻。

总之 9:1x 过 T2。

然后看 T3，感觉是不可做题，跳了。

差不多 9:30 开始做 T4。

这里我用了个非常奇怪的方法，不知道有没有人和我一样，大概率是没有的？

看到这个东西我就发现 q 比 n 小很多，容易想到把询问的区间离散化，变成 2q 个小段，我只要求出每个小段对于 1\sim n 的答案最后离线用 st 表之类统计一下就直接结束了！

令第 i 个小段为 [L_i,R_i]，枚举左端点，直接先滑动窗口统计所有 [j,j+L-1]，剩下 [j+L,\min(j+R-1,n)] 的长度为 R_i-L_i+1，考虑分块，比较好（？）维护。

差不多就是维护每个 [j,j+B-1] 的和、前缀和的前缀 \max、前缀和的后缀 \max、右端点在 [j,j+B-1] 中的 [L,j-1] 最大值、包含 [j,j+B-1] 的区间和最大值。

总之复杂度为 n\sum_{i=1}^{cnt} \sqrt{len_i}，cnt 是分出的小段的数量，其中 \sum_{i=1}^{cnt} len_i =n，感觉就非！常！可行啊！

此时我通过了所有大样例（虽然我这种大常数选手可能直接被卡爆），但是我发现——空间炸啦！！！

因为我的算法要先存下一个 2nq 的数组最后离线处理，但是%E&##的出题人 |a_i|\le 10^5，sum\le 5\times 10^9，10^8 的 long long。

此时已经 11:45，我已经开始慌了，我发现我好像根本没有任何办法可以降低空间复杂度，T3 还没有写，我到底该怎么办？

所以，我直接摆啦！将 long long 直接换成 int。

然后我通过了所有大样例。

？

没错！此时我突然发现答案很难超出 int 范围！但是出题人肯定会有专门的数据卡，怎么办？欸！sum\le 5\times 10^9 不就证明 ans_{\max}-ans_{\min}\le5\times 10^9 吗？退一步讲，出题人真的可能出一个全 10^9 且 q=1 的狗屎数据来卡你吗？不可能！所以直接对每一个小段定一个偏移量，然后将记录的答案都平移到 int 里面！

咳咳，就这样，我在 11:50 的时候将空间卡进去了。

再来看 T3，一看就是个性质题或贪心。思考到 12:30 无正解思路，想出来的贪心都是一眼假，我是废物，直接打个 n^3 和 m\le 2 就滚了。

出考场发现 lwz 稳过 T124，%%%。xcx 因为只过了 T1T2 而没交代码？额，真不至于。好多选手没过 T2，个人感觉这次 T2 确实不太好的样子，长得跟个网赛似的，不过这些都是后话了。

最后得分 100+100+56+[50,100]=[306,356]，明年再来吧，滚回去学 whk 了。