联合省选 2026 游记 / 人类能做到命令错误挂 108 吗

ANDER_ · 2026-03-08 21:56:48 · 生活·游记

前情提要，坐标 SD，初二体验。如想省流，请前往 Day2。

Day -2

开学。

Day 0

上午文化课。中午和学校领导合影之后上车，路上听题被初一神 zrl123456 完全击败。下午 \tt16:30 左右到酒店，然后吃饭，然后被刀削面辣到了。然后回酒店和室友 leather_handbag、insulin 一起玩 Rusty Lake : Cube Escape。真的很好玩。

然后去领了考试条，等待途中看 WFYZ 高中生打篮球。

济南晚上比较凉，让我感到绚烂而不真实。心里完全没有底，认为会被严厉打爆。

这么神奇。

提前 \tt1 小时来到逸夫楼门口，得知不能入场。众人认为太冷了，于是回酒店后复返。

发现了许多高手，本人右边是 OldDriverTree，他右边是 KSCD_。同一考场的还有 2huk，以及队爷 崔化博。此外还有初二的同学 insulin、ruiqi2012，其他忘了。

写了线性筛，发现 3\times10^8 跑了 3.4 秒，发现算上了编译时间。

继续听题，感觉要唐完了，发现真的啥都不会，Boruvka 都不会。

zrl123456 的母亲给我和他买了美味枣糕，感谢。

教练发了零食。

晚上干啥忘了。

Day1

进场，然后神秘充电宝起火了，然后火灭了。

大体浏览了一遍题目，\text{recollector} 显然是 DP，并不擅长，\text{string}、\text{night} 看起来都是 Ad-hoc，难难难。

开 \text{recollector}，上去就唐了一个假完的做法，及时发现。发现可以拆贡献，发现可以把 \sum_jl_j 拆成前后缀算，于是 DP，一个是 u 自己的重链长度概率，一个是 u 的兄弟的重链长度和的概率，直接卷积是立方的！大概 \tt9:45 才想到了这个后面看起来 native 的算法，然后写写写，然后挂挂挂，反正没调出来。我还以为又假完了，然后想了另一个假掉的算法。\tt11:30 感觉要燃尽了，后面的题部分分也不简单，于是写了个 \tt8 分暴力弃了。后面拼了个分多少忘记了。

打得稀烂，没有写出任何体现大脑存在的分数。

insulin 写了 \text{recollector} 的 \tt40，后来发现时间复杂度分析错了，就是满分做法但是没看出来，可惜。zrl123456 表示没多想，写了个多项式除法优化到平方，这是初一？队爷 崔化博 切 \text{string} 了，强强。

感觉葛立恒数个人写了 \text{recollector} 的 \tt40 分，我糖丸。

完全是能力的问题吧，调不出来太可惜了。

中午吃羊汤。

下午看护城河，登了解放阁，风景真的好。和 zrl123456、insulin 以及他们的家长一起去的。

::::info[照片]

::::

看题，zrl123456、insulin 强强。

下午回酒店玩 Rusty Lake : Cube Escape，有趣。

::::info[照片] ::::

晚上发现 leather_handbag 有点低烧，大家帮他买了药。

吃饭。

看题。

教练晚上给 leather_handbag 测体温的时候，告诉我我块头比较大，要求我在前面去敲另一个房间的门。声称自己躲在我后面，突击检查是否有颓神。欲辞不能，真是太神奇了。

感觉明天也不会怎么样了。

Day2

开题，完了完了完了是交互，这把没救了。

开 \text{perm}，仍旧秒出假完算法。

尝试随机钦定，于是开始以正解的角度思考。

::::success[题解] 先考虑固定查询左端点 l 为 0，右端点 r 从 n - 2 依次递减，直到找到 0。

对于两次查询 [l,r + 1],[l,r] 的结果，分别记为 q_1,q_2。分讨：

• 若 q_1 \not= q_2，很显然 res_{r + 1} = q_2。
• 若 q_1 = q_2，我们发现删除了 res_{r + 1} 但是对 q 没有影响，立刻有 res_{r + 1} \ge q_1

我们把第一种情况直接记在 res 里面，第二种情况离线下来。

找到了 0 的位置 pos，因为与 0 相离的区间查询结果都是 0，我们直接倒过来跑一遍。固定 r = n - 1，让 l 从 2 开始递增直到 pos。继续上面的过程。

最后那些没有填上的数字，我们直接根据第二种情况的限制，塞进去就行了。

考虑证明这样做是不会改变 \text{mex} 的。对于 res_i 覆盖它的区间可以发现从有零的方向划过来的区间才有意义，不然查询结果总是零，填啥都一样。所以我们考虑 i > pos 情况，其余同理。

所以对于 res_i，我们的查询是 [0,i - 1]。若此时 [0,i - 1] 的 \text{mex} 已经小于 res_i，那么很显然 \forall j \isin [0,i - 1],\text{mex}_{k = j}^{i - 1}res_k \le res_i，因为被包含的区间的 \text{mex} 总是不大于包含它的区间的 \text{mex}。

也就是说，我们用这种策略填了这个 res_i，保证了右端点为 i 的所有区间的 \text{mex} 都是相同的。

再次重申，因为 i 的右边没有 0，填任何值，以 i 为左端点的 \text{mex} 均为 0，条件天然满足。

查询次数显然是 n。 ::::

我去，怎么是 n 的操作次数！这不切了！

不会用给的 checker，自己写了一个。