Re: End of a Dream

· · 生活·游记

说是省选游记，可自从 NOIP 走出考场的那一刻，这已经只能算得上一篇 NOIP 后传罢了。

本着“参与为重”的精神，赛前我甚至没有专门集训，带着两瓶水，就上了考场。毕竟，对于 NOIP 全省 rk147 的选手来说，省选得分算得上什么呢？

Day 1

考前歌曲：

到了考点。与我同行的是一位体验名额选手。看他打了一会英国源神，只见各种反手红蛇。没过多久进了考场。

8:30，开考。看试题。感觉第一题特殊性质一和二都很良好。第二题像是某种数据结构题。第三题……不可言说。

先看 T1。想了一小会特殊性质二无果，于是又去想特殊性质一。发现可以尝试判断每个数 x 能否成为“幸运数字”。能取到 x 的就取 x，剩余的分别计算一下小于 x 与大于 x 的数字的下限与上限，尝试让它们尽量保持平衡即可。

这时候，我意识到，根据各段 b 的分布区间，我可以同时处理多个数。然后得到一个……O(n \log n) 算法？

8:48 开始写 T1。9:15 写完。因为开了 -Wall 又没使用 scanf 的返回值爆了一堆 warning。测样例二发现有一个点过不了。样例三后两个点过不了。样例四两个点都是错的。怎么回事呢？检查代码，发现没开 long long，修改，重新编译，依旧爆一堆 warning。再运行，怎么还是不对？

检查半天无果，准备输出中间过程，突然发现代码中间不知道什么时候多了一块样例。从终端往上一翻，发现 warning 上方居然还有 error。合着刚刚根本没有编译成功。删掉意外复制的样例，编译运行，通过样例。此时是 9:35。

看 T2。6s 时限，2GB 内存，不清楚出题人到底带着多大的决心一意孤行的卡掉错解。当然跟我无关就对了。 不错的题目，题面与背景相互呼应，……算了不玩抽象了。

寻思了一会感觉是某种高级数据结构（我不会的那种），但特殊性质一个都不会做。经历了漫长的思考，最终选择放弃。

看 T3。乍一看很吓人，仔细一看确实很吓人。G 联通又如何？反正我还是不会做。特殊性质 B 真包含于 C，故直接看 C。

手玩了一会，发现在一棵树中，各个子树必须占据一段连续的一段序列。那么结合字典序最小，一棵树内的遍历顺序确定。这可以用类似树形 DP 的方式实现。而将每棵树处理成一个序列后，又可以用某种类似括号匹配的方式合并各个序列，得到最终序列。这样可以通过带有特殊性质 C 的测试点。此时是 10:55。

写代码。顺便把暴力写了。把状态很差，合并序列写不清楚。上厕所，调整状态，决定先测试同时带有特殊性质 A 和 C 的代码。修了几个小 bug，阶段性任务完成。

突然意识到用类似递归的写法会比用栈硬写后面的序列合并更舒服，于是用递归算法重新编写不含特殊性质 A 的部分。测试对应特殊性质 ABC 的样例，运行时错误。输出中间过程，每次结束的点都不一样。这是为什么？？

观察样例性质，发现是一条链——递归层数过多爆栈空间了。这个小丑赛前忘记查怎么在 linux 系统下改栈空间了，这下测不了这个样例了（悲）。

测其它样例，很顺利地通过了。这时候突然发现多写了两个没有意义的 DFS，令人忍俊不禁。12:09。

再回去看 B 题，拼尽全力无法战胜。打完暴力，12:30，检查程序，注释记录比赛过程，跑路。

期望得分 100 + 20 + 52 = 172。不算很差至少能进浙江前 147 名。

Day 2

考前歌曲：

决战。

读题。T1 特殊性质 A 是个简单性质，特殊性质 B 应该也很好做，总的来说是个好嫖分的题目。T2……孩子们，是指数级别算法当正解，我们没救了。T3 什么玩意？？

开题。开 T1。秒了性质 A。样例只有 6 组，可能有点弱，回过头来可能要写对拍。看性质 B。记 b_i - a_i = d_i，按推箱子顺序排完序后，对于所有二元组 (d,t)，有 \sum d < t……

等等，这个式子我研究过！甚至出成题给学校里同学做过！！

虽然题不太一样，但毕竟贪心的证明是一致的，更何况后续的处理比我自己出的题（当然了，估计早就有人研究过了）还简单。于是愉快的过了性质 B。

然后就卡住了。性质 C 简直就是来搞笑的，跟无特殊性质完全是一个做法。于是开始罚坐。

经过一番尝试无果，最终选择了大胆猜测忽略求证，直接沿用 B 中结论，将 t 从小到大排序，依次进行操作。对不对交给上天。写了个 n^2，能过 n \le 3000 的所有样例。但愿是对的。

那正解呢？把 a_i,b_i 各减去 i，可以使得我们能方便的维护箱子位置的移动。那关键是查询怎么办？比如向右移动，要求 \sum \max(c-x_i,0) 之类的东西，这分块当然能做，但我不会分块怎么办？

不会想了这么久，就因为不会数据结构挂分吧……

诶，不对！修改与查询的都是连续的一段箱子，所以可以先二分求出修改与查询的区间（是的，这个菜猫不会线段树二分），再用线段树维护！而且相当好写！O(n \log ^2 n) 在 n \le 2 \times 10^5,2s 的数据范围下可以说跑的轻轻松松（到时候被卡了就老实了）。这算是 A 了吗？

此时已是 11:00。

后面的赛程我就成纯小丑了。T2 有个特殊性质 B 可做，但我不知道怎么去重；T3 想破脑袋也没想出特殊性质 AB 怎么做。

看了半天，最终还是选择 T2。特殊性质 C 是所有的生成树都是最小生成树，但怎么去重？经过漫长的思考，最终还是只写出特殊性质 B。

时间来不及了，赶紧把暴力补掉吧。然而，这可能是我写过最恶心的暴力：求最小外向生成树怎么求？先枚举根节点再状压 DP？更新顺序怎么处理？最终，脑子里一片混沌的我写下了一片混沌的 BFS。

这可能是我写过的最恶心的暴力。光代码长度就来到了整整 2KB，时间复杂度更是在种种冗余的操作下来到了惊人的 O(4^m \times 2^n \times n)。但愿能跑。

在一通乱调之后，终于过了特殊性质 A 和 B 后的我发现考试时间早已来到了 12:50。看来没时间写 T3 了，查一下前面的题吧。

测 T1 的各个部分分。测 A。A 过了。测 B……怎么全输出 Yes？观看一分钟无果，我于是干脆直接将特殊性质 B 的分支注释掉，直接用“正解”跑。测试结果回复正常。测试 T2 无误。填完源程序字节确认表，T1 5.4KB，T2 4.2KB，T3 0KB——大道至简。剩下一分钟，没时间记录比赛历程了，对着 T1 代码想了一分钟特殊性质 B 的代码为什么之前测能过，刚刚测试时过不了，未果。遗憾离场。

出场后 5 分钟，突然想起来考试最后测试 T1 时用 move2.in 测试特殊性质 B，而那其实是特殊性质 1 的特殊性质。令人忍俊不禁。

期望得分 100 + 24 + 0 = 124，期望总分 296 分，两天分加起来没别人一天分高。

也算是一个意料之中的结局吧，就差了 D2T3 那 8 分的暴力。

后续

2025.3.4

看来我还是对线段树的常数太自信了。

事实证明，D2T1 我的 O(n \log^2 n) 做法在洛谷上可能要 3.2s 左右的时间才能跑过。

老实了再也不写线段树 + 二分了。

2025.3.7

出分。

Day 1 一分没挂。

Day 2 T1 不出意外的被卡掉了。贴心的评测机多送了我 4 分当安慰奖。

Day 2 T2 挂了 12 分，怎么回事呢？

if(debug=='B'||(4<=c&&c<=6))
{
    dfs(1);
    ans=ans*qpow(4,m-n+1);
    printf("%lld\n",ans*qpow(qpow(4,m),mod-2)%mod);
}

第 4 行后忘记取模了。

NOIP 总分 65 + 100 + 24 + 32 = 221，省选 Day 1 总分 100 + 20 + 52 = 172，Day 2 总分 76 + 12 + 0 = 88，三场总分 481，不及某些人省选两场成绩。

AFO。

等排名。

没有跌宕起伏的故事，没有逆境翻盘的情节，短短 8 个月的第二段梦境，于此时结束。

"Can you hear me?"