省选联考 2025 游记

_lmh_ · 2025-03-02 23:29:43 · 生活·游记

像孤单的旅行家
骗自己我不害怕
再让我相信这一次
也许明天会到达

—— ilem / 心华《一人行者》

Day -?

看看往年的省选题吧。

重写一遍季风，过了所有大样例喜提 20 分。xor，感觉想明白之后不难写——但考场上咋可能想明白啊。迷宫守卫，不是人做的。最长待机，特殊性质原来能拼 80 分吗？过河卒，有了前车之鉴倒是一遍过了。填数游戏，好困难。城市建造，根本无法战胜啊。

Day 0

有点感冒。

背点板子。字符串，字符串，字符串，poly，网络流。

被家长要求 11 点之前睡觉。

睡不着一点。

Day 1

早上差点没能爬起来。

总之是开考了！带了一瓶咖啡，会赢吗？

开 T1，秒了（所以这玩意凭啥蓝啊），写写写。不难发现离散化之后可以枚举中位数所处的段。可以做到除排序之外线性不过脑抽写了个树状数组——好处是不用多清空一位。

开 T2，知道你喜欢怀旧了但是这能做？？想了一百万个线段树合并状物并毫无意外的全部假了，打了 20 分跑路。

开 T3，这是？？？哦原来是把图拍到数轴上要字典序最小，看上去这个树的部分分有点可做。显然我要先放 1 然后再放 2，中间拉出来一条链顺序也是固定的，好像可以递归。哦哦哦原来是子树内 \min 和节点本身排序从小到大做。

哦哦哦联通的性质一点用没有，把每个块的序列搞出来拼一下就好了，52 分跑路。

最后意识到 T2 的 O(\frac{nm}{w}) 是能过的（不然呢你要挑战图灵奖吗），想想特殊性质吧。AB 是个显然的对序列按照 a_i 分块，并且可以每一块单独做压空间（其实你不用压空间的铸币吧）。这个东西似乎可以做 a 固定的特殊性质。

先对序列分块，再对时间分块，每 \sqrt q 个操作暴力重构一次，对整块的操作查询的时候不考虑后面一块修改的位置——这个放到每组询问里面单独做，时间复杂度可以摊到单根号。等下，我 \sqrt n 个块，\sqrt q 次重构是不是平方的？原来可以把块长调到 n^{\frac{2}{3}}，没事了。

写写写，写了一辈子写完了。然后大样例调不出。等一下，我 ans 取 \max 写成赋值了？这下虚空调试咯。

大样例跑的有点慢，鬼知道这玩意能不能过 10^5，但 8\times 10^4 应该还是能过的。

获得了 100+52+52，是不是赢麻了，开始对着 T2 的题目背景发呆。等一下，分块套分块是不是能做 a 有修改的情况？赶紧写，赶紧写，写不完了——

倒闭。

出考场发现许多人只有 128，那我有分就偷着乐吧。不过平方过 6e4 又是什么意思呢，欺负我数组只开了 2000 是吧。

Day 2

还有救吗？？？

开题，T1 一眼秒了，写写写，怎么要线段树二分，生气了。等一下，为啥最后一个点挂了？哦原来是我们整型溢出，没事了。

昨天一题没拍今天还是拍一下吧。最后一共测了几十万组数据，问题不大。

开 T2，这啥？我知道我快要被永远遗忘了但这是啥？我怎么 n\le 6 都不会？哦 m\le 6，我会了。B 性质感觉像个树上 dp，不太想写。

开 T3，你是？

破防了。

仔细想了想发现 AB 性质很可做——可以枚举最大值，发现序列总共只有两个递增的段，就是推式子了。顺手给它拼了个爆搜。

还是得想想 T2，总之先写 24 分的性质吧。写完发现树上的答案好像与形态无关？还真是那么回事，不过无所谓了。

之后开始憋 C 性质。和树的形态绑定的做法显然没一点道理，对合法的初始点集合计数也不太行。此时时间已经过去了 3h+，情况不太好。

发现合法当且仅当缩点之后只有一个强连通分量没有入边。一开始以为和连通性有关又编了几个假做法，发现是强连通分量就好做了。先容斥一遍求出每个点集 S 划分成 x 个强连通分量且它们之间没有边相连的方案数，然后对这玩意做一次容斥就好了。

小数据调了一会就过了，但为啥我 n=9,m=27 会输出 0？哦哦我存边的数组只开了 O(n)，会越界，没事了。

为啥过不去 n=15 啊？不管了。

最后半个小时尝试冲击 T3 的 n\le 18 未果，又假一个做法。