SHOI 2025游记

yanzihe · 2025-03-02 14:52:46 · 生活·游记

Day [\infty, -1]

停课训练，每天打模拟赛，分数越来越低，不知道为什么，感觉自己越训练越弱了。

Day 0

发明了「打块做题法」，即一道题思考 10min 后如果没有想出解法，就打 10min 块，这样大脑就能得到了修整，然后就能继续思考。

我用这个方法很快写做出来了ARC180D，稍微找回了一点自信。

Day 1

考前一晚没睡好，早上不知为何醒的特别早，状态不好，喝了一杯咖啡也不太管用。

虽然状态不好，但T1是简单题，很快想到了结论，写了个动态开店线段树和二分，不到一小时过了。

开始想 T2，根本不可做，完全想不到办法维护 DAG 联通性（实际上我一直在考虑 O(n\sqrt n) 和 O(n\log^2n) 的做法，完全没有往 bitset 方面想） 浪费了 2h 后放弃，得了 20 分。

看 T3，发现如果是一颗树，那么每个子树被赋的是连续的点权，直接贪心即可。简单证了一下就开始写，直接过了大样例。

考虑森林的做法，在用了一会打块做题法后，发现只需要对每个树分别贪心，然后贪心地合并即可，简单写了个 set 做法，很快过了。

此时只剩下 30min，开始写最基础的 8 分暴力，结果写挂了，调调调，调到考试结束也没调出来。

还可以吧。

最值得高兴的是在考试期间（8:30~13:00）共计打了 30min 的块，估计是全上海最久的。

Day 2

T1 是简单题，显然按照 t 从小到大的顺序推箱子，如果暴力枚举推箱子路上会经过的所有其他箱子，则会 TE，遂考虑 ds。
首先想线段树，感觉不太可做。这时发现平衡树可以做，只需要把相邻的箱子合并为一个连痛块，在平衡树上暴力查询即可。通过势能分析不难发现复杂度 O(n\log n)。

正准备写 FHQ-treap，突然发现 FHQ-treap 所需要支持的功能和 set 一样，于是直接用 set 写，很快就过了。

因为大样例数量太少，于是写了个暴力简单对拍了一下，在 1.5h 时搞定了这题。

T2 24 分是简单的，于是想特殊性质 C，发现完全不会维护有向图联通性，遂倒闭。只能写一个 A 的暴力枚举，用了一会打块做题法后，想到了一个点减边容斥套树上 DP 过了特殊性质 B。

还剩下 1.5h，看 T3，理论上 1.5h 在 T3 拿 16 分时容易的，但是我认为我必须拿到所有特殊性质 B 才有翻盘的希望，于是想了半小时，不会。 还剩下最后一小时，写暴力，发现第一档暴力也不会。不知道为什么，我认为暴力复杂度 O((n^2)^n)，没敢写，输麻了。

不会暴力就只能尝试写 n\leq 18 的特殊性质 AB，此时已经完全慌了，不太能冷静思考，随口胡了一个不知道真假的做法，调不过，最后在 T3 得了 0 分。

赛后发现几乎所有人都拿了 T3 的 8 分，只有我没拿，输麻了。

其实之前我的状态是比较好的，做 T3 的时间也算充裕，但我觉得时间不太够，没敢使用打块做题法，导致思绪非常混乱，最终也只能遗憾离场。

其实如果我打一会块的话，至少 8 分应该是有的。