2025 God Selection

· · 生活·游记

喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵喵

Lemma. ： 省选是给神打的。

Proof. ：

先证，我没有参加省选：

![](https://cdn.luogu.com.cn/upload/image_hosting/b0luc3fq.png) 充分证明了，我打的是一场由与 CCF 关系极为密切的民间组织，秘密组织的一场模拟赛，择优者走后门进省队。 又 $\because$ [机房の神](https://www.luogu.com.cn/user/162084) 是唯一的。 $\therefore$ 我 $\not \in$ 神， [机房の神](https://www.luogu.com.cn/user/162084) $\in$ 神 $\therefore$ $\exist$ 人 $\not \in$ 神，不打省选； $\exist$ 神，打省选 $\because$ “省” $\approx$ “神” $\therefore$ 省选 $\approx$ 神选 $\because$ 由语文知识可知，神选的对象为神。 $\therefore$ 仅限神可以参加神选。 综上，省选是给神打的。 $\mathbb{QED.}

对此我认为：

西江月·证明

即得易见平凡，仿照上例显然，留作习题答案略，读者自证不难。

反之亦然同理，推论自然成立，略去过程 QED ，由上可知证毕。

省选前一周

老师并不要求脱产，从 NOIP 结束到现在，总计摆烂 4 个月整。

期间并没有进行竞赛学习，我感觉我已经废了。

对于一直用 Windows 的我，感觉失去了最后的希望（玩__玩的）。

Day -1

周五回家就开始打臀，顺带复习了板子，但是太多了，再加上人性恶的弱点，所以复习了 Manacher 和 KMP ，还有 Tarjan 就跑了，睡觉睡觉~~~

Day 0

菜鸟第一次打省选，好紧张啊~~（反正过 D1T1 就行）

但是，去早了，看到了 强者 ，一起 \bmod 了 机房の神 。

不小心进考场了，然后出不去了，干坐了 35 min （手自己动了）。

有点后悔没带板子，呃呃。

8:25

开始报压缩包密码了 keeP*drEAm&iNg ，那个报密码说了半天什么 “ Ender 符号”，听了半天才明白是 & 。

8:30

开始了， T1 开局看特殊性质，保险写了个离散化，感觉上是一个连续的区间做贡献，但是觉得不好写，先叉掉了，虽然是对的。

于是思考怎么算贡献，最开始的是考虑维护一个左闭右开的区间是否符合条件，对于左右两边的数的个数的区间进行维护，计算最少差值是多少。

写挂了，开始打草稿，看了半天才明白怎么回事。

于是改了个思路，此时是 9:00 ，考虑维护单个值与两数之间的开区间，同时记录下左边，包含和右边的个数区间，同上计算是否符合条件。

调了 1h ，终于出来了， 死因：如果左边多，应该是包含数的最大值大于两边最小差值，而非大于等于。

开 T2 ，题目背景好，本着会 D1T1 就开摆的战术，所以先写了 O(NQ) 暴力，然后暂时没有然后。

开 T3 ，没啥思路，还是本着会 D1T1 就开摆的战术，所以写了个 O(N!) 暴力，然后也没然后了。

想了一下 T2 ，这么大的时空间，算了一下，写 bitset 然后先 O(\frac{N^2}{\omega}) 预处理一下可到达性，然后想了想莫队，不是很能过，不是很会，于是觉得肯定是分块，此时大概是 11:30 。

接下来，是笑点解析，我一看时间，并没有着急写与想怎么分块，原因是我以为是 12:00 结束，觉得 30min 肯定调不完，所以没仔细想，磕了一下 T3 ， O(N^2) 的解没出来，特殊性质也不会。

12:00 的时候，突然意识到还有 1h ，于是开始想 T2 的分块，然后没想出来（我在期待什么）。

13:00

寄……

听同机房的也是 128pts （普遍较菜），心中极其平衡。

晚上

AK 了 ABC ，感觉我又行了。

熬到了 00:00 ，觉得不能再熬了，于是睡了~~

这是一个永远也无法遗忘的夜晚，因为 5:00 就起了。

谁叫我平时 3:00 睡 8:00 起的，呃呃。

Day 2

手不用自己动了，带板子了，从 7:50 玩到 8:15 进考场。

太阳真大，自动上全隐。

8:25

Re#MAin(LoVinG ，这下听清了。

8:30

先开 T1 ，一眼贪心，先写了个按 t 排序，再将往左往右分了个类，然后开始推式子，推了 1h ，推出来了个像样的东西，总而言之就是比较 (a_j - j) 与 (b_i - i) 的大小，然后贡献就是 \sum_{i = 1}^N |(a_i - i) - p_i| （没记错的话），然后线段树维护的 p_i 是单调的，所以区间取 \max 或 \min 维护和即可，复杂度应该不会假，感觉是最多分成两段（一段可以全赋上去，一段可以不用动），主要是不会写线段树二分（此时我们要邀请 机房の神 出力，毕竟如果 T1 是线段树二分，她总是能写出来）。

【上帝视角：其实复杂度好像在我的一番操作下变成了 O(N^2) ，挂成了 44pts ，但我没发现问题所在。】

调完线段树用了 1h ，还有 2.5h ，看了 T3 ，觉得神秘，于是没打算写，暴力也不太会。

于是看 T2 ，看到 N \leq 15 ，我觉得就是状压 DP 啊，写了一会暴力，感觉要容斥，容斥了 2h 没容斥出来，还是太菜了，图计数的问题就没做过几道，而且还都是初赛的时候做的。

反正就是想到了先 Kruskal 按边权排序，分不同边权 DP ，然后内部就是一个容斥，出来的复杂的估计就是 O(3^N + 2^NN^2) ，至少考场上把复杂度猜对了，交了个包错的 0pt 代码扔了上去。

13:00

这次没记错时间，但是还有笑点解析。

想着摸会再走，于是摸了一下板子，也就 15min ，看人走完了，才开始走的。

结果给我关杭师大里差点出不来了，最后跟闸走的（莫要学我）。

Day 3~8

看了一眼题解，果然是我不会做的题，放弃了。

出分了， D2 挂完了，明年再战，再摆一年~~

Happy Ending