SNOI2025 卣计

· · 生活·游记

前言

今年初三，第二次参加省选，第一次不记得总分，好像不到 40，今年停了一个学期左右的课用来搞信竞，感觉要是没有进队就完蛋了，所以压力也比较大。

Day1

往文件夹装了致死量的德芙巧克力后就出发了，考点还是西工大。在门口罚站 20min 后成功进入考场，我们学校的人座得都比较近，形成了一个首项为 22，项数为 6，公差为 2 的等差数列，还有两个人被孤立了。

刚坐下看到要填的表我忽然脑洞打开：我没带笔，然后找同学借了一根，yes！你说的对，但是 8:00 下发文件，还在观看大样例试图猜测题面的时候，听到 pdf 已经可以看了，4.5 个小时秒变 5 个小时如何呢。然鹅前半个小时疑似在睡觉，光顾着想答题策略，然后题目一个字没有想。

T1 深度思考了 30min 后发现部分分是容易的：可以暴力枚举所有数字，然后 check 以下是否可以成为中位数。如何 check?不难想象到对于 x，可以让 x 尽可能多，这时候，所有 l_2\le x\le r_2 的 r_1 都要统计贡献。而前后两侧可以考虑适应匹配，因为我们假设 x 的前中后各有 L_1,L,L_2 个数字，则不难列出不等式，应当有 L_1-L<L_2\le L_1+L，考虑对于所有 L_1 可能的取值列出一个并集，那么假设 A\le L_1\le B，那么如果 L=0 则无解，否则 A-L<L_2\le B+L，于是我们只需要求出 L_2 的取值范围就可以得到结果。以上都是容易求得的。然后一秒推广到全部情况：不难考虑到对于一些区间段 [L,R]，其中的取值要么都有可能，要么都无可能，这样的段就是你对 l_2-1,r_2 离散化后的结果，那么最多有 O(n) 个段，统计信息利用差分可以做到 O(n)（考场降智使用树状数组维护），复杂度瓶颈在离散化，因此总复杂度是 O(n\log n)，写完是在 9:45。

T2 传递闭包是简单且容易的，不难想到用 bitset 实现有 O(\frac{n^2}{w}) 的优异复杂度，后面不会了，因为过于虚弱，连部分分的正确写法都没有想出来，最后自暴自弃写了个 O(n^2) 的暴力，大样例跑了 35s，气得我直接拆了包巧克力，然后被牛奶味巧克力齁死了。

接下来考虑 T3，树的部分应当是简单的，只需要考虑贪心往子树中找最小值再不断往回跳即可，但不知道为什么脑萎缩认为这个做法没有正确性，打完链的部分分才发现是对的，极限没有打出部分分，暴露了自己的愚蠢，保留了 12pts 的代码。

剩下的时间想了个 T2 的枚举优化：普通的将 b 从大到小枚举，这样找到了就可以直接推出，另外 17、18 两个包的枚举范围可以改为 [l,r]，能写优化不写是傻子，然后发现大样例只跑了 9s，我直接就被吓死了。

考试结束被拘禁了 30min，和同学聊天吓唬他们考了 212pts，差点给他们心态搞崩。和 NOIP 坐我旁边的同学聊天，他说 wyr 有 252pts，我不得不感叹牛哥的强大，幸好我和他不抢名额，嘻嘻。然后发现 T3 52pts 疑似大众分，心态略有爆炸。关于 T2 打算相信 CCF 的数据强度和新晋少爷机的评测速度，毕竟 O(tn^2) 好像只有 2\times 10^{10}，6s 可以跑过的对吧。

回去打了一下午游戏，感觉不能这么颓废了，于是换了个游戏打。

Day2

赛前和同学聊昨天的题，探讨了今天的比赛是否依旧延长到 5 个小时，还有 Day1 Day2 座位号的规律。经过 1s 的研究，我们成功得出座位号关于 26 号对称后的结果，然后成功获悉了正式选手的人数。然而我是 26 号，所以我不动，有一点开心。刚坐下发现笔有没拿，又借了一根。果不其然又是 5 个小时的考试。

T1 感觉比较难，可能是心理因素，先想了 O(n^2) 的暴力：显然按照规定时间从小到大排序肯定不劣，对于一个箱子，假设 a<b，最优做法肯定是将 [a,b] 这一段路径上的箱子（假设有 c 个）依次放到 [b,b+c-1] 的位置上，如果这些位置上依然有箱子，则继续递归直到不存在箱子，暴力枚举可以快速实现这个过程。对于 a>b 同理，并且注意这里的 a 是每个箱子的当前位置，而不是起始位置。然而我们发现这个过程是有规律的：每次移动的箱子的区间是具有单调性的，更具体来说，如果一个箱子当前所处的位置足以支持在它前面的所有箱子从 b 开始排布，那么它一定不在最后的需要移动的箱子中，那么我们可以二分这个位置，接着考虑位置的改变，不难看出我们只是将一个区间修改成了公差为 1 的等差序列，只需要维护首项就可以正常下方标记。于是考虑平衡树，在平衡树上二分找出需要改变位置的箱子区间后，计算这一段区间的总用时，放置位置标记，接着比较时间即可，总复杂度是 O(n\log n)。但因为细节问题，到了 10:20 才写完。努吃 2 个巧克力，再次被齁死。

T2 因为赛前复习被同学洗脑说不会考最小外向生成树没有背诵板子毫无头猪，于是选择先行弃掉，对于 T3，暴力是显然的，写一个 hsh 即可拿到 [8,20] 的得分。

滚回来写 T2，思来想去决定先把 12pts 写了：考虑枚举每条边在最终图里的状态，然后判断最小生成树是否和原图一样，但是发现最短路是假的，只能使用暴搜，最后凭借 O(n^22^{4n}) 的惊险复杂度拿到了分。

结束后听同学说打了 120pts，感觉应该是大众分，通过人脉得知了 wyr 224pts，orz。和同学预估了一下加权得分，感觉还行，一时兴起又吃了几个巧克力。通过广泛的社交，我们得知 T2 24pts 是简单的（然而我不会）。

总结

预估得分：100+[20,100]+12+100+12+[8,20]=[252,344]

云斗得分：100+96+12+100+12+12=332

CCF 评测机你是机器中的擎天柱，能不能让我多拿几分。