省选联考 2025 游记

IvanZhang2009 · 2025-03-01 19:17:10 · 生活·游记

前情提要

NOIP 写了 100+100+100+64 变成 100+100+88+48=336，屈辱掉下队线。

省选前几天狂摆，在引诱，雀魂，学习【数据删除 1】和看【数据删除 2】之间反复横跳。

2025.2.28

下午面人，突然告诉我有 \frac{1}{3} 这个东西，然后相当于我 NOIP 上队线了？这么牛的。

进场打了把雀，和 cyx 通牌。我坚信牌运和 rp 是可以同时存在的！试机写了 ntt，然后看 tyx 和 lpl 讨论 query 就写了一下，写完过了前三个样例，第四个挂了，摆。

和 cyx 和 yrq 吃饭。吃完回家摆。晚上肚子有点不舒服，但是管他呢。又学了一会儿【数据删除 1】，但是没学进去啥。十一点十分睡觉。

2025.3.1

被七点的闹钟强制开机了，感觉状态会很差。

早饭 /ruo。

快进到进考场。座位号是 406-049。板子写了 read 和 qpow，然后发呆。八点二十发现了下发文件（显然需要密码），看了一下文件夹，猜测 graperm 是个构造（输入一如既往的大，但是输出也比较大，最后比输入还大），大概都是多测，然后 lucky 看着输出很少。样例这么少大概会是签吗？

8:25：下发了密码。结束的时候背了一下，大概是 keeP*drEAm&iNg。大致看了一眼三个题意，原来 graperm 是这个意思啊？我还指望学点新单词呢。发现 T1 很简单，直接开写。狂敲键盘试图搞心态。

8:30：T1 怎么写完了。挂样例 2 红温中。

8:40：终于调出来了。死因是中位数必须存在。

简要题解：

直接枚举中位数！某个 apio 启发我们中位数的判定和 <=> 的个数相关。容易发现等于的越多越好，所以包含中位数的区间一定是 =，严格左边的肯定是 <，严格右边的肯定是 >。简单扫描线容易维护出三个对应的区间的和。注意到若 <=> 的个数是 x,y,z，合法条件是 x+y\ge z,x<y+z。这相当于 |x-z| 要尽量接近 0。如果 x,z 所在区间有交则肯定可以取到 0，否则可以取左边区间的右端点和右边区间的左端点 check 一下就可以了。

需要离散化，时间复杂度 O(\sum n\log n)。

8:40 ~ 9:10：大概在 T2 和 T3 之间反复横跳了一下，都有不少收获。

• 观察到 T2 需要注意时空限制。发现这个有向图可达性是不是不弱于 n^2 来着，还可以简单 \frac{n^2}{\omega}。算一下空间发现大概 1 个 G，那是不是对完了。怎么是暴力题。

• T2 感觉没啥头猪，可能可以分点小块，比如说按 10 分块，预处理每块的每个 msk 的 b_{\max}，复杂度是 O(\frac{nq}{B}+n2^B)，空间也很卡。好像没啥前途。

• T3 感觉嗯做啊，看上去部分分很诱人很丰富。这个树可能不难，森林估计也就嗯推一下，然后取个生成树做一下估计也不难。待会儿嗯想一下。

• 考虑 T2 如果边都是 i\rightarrow i+1 怎么做，似乎相当于动态二维数点，所以看上去 polylog 死路一条。不如接着想暴力。

然后抉择了一下还是决定全力 T2。然后突然发现了一下这个 A 的带修好像比较容易。目标是求出对于一个 r，所有 a_i\le r 对应下标的 bitset。似乎可以直接分块维护，设块长 B，暴力维护每个 r\equiv 0(\bmod B) 的 r 对应的 bitset，修改的时候只要改 O(\frac nB) 次，然后查询的时候 O(1) 跳每个散块，差分就可以得到 [l,r] 对应的 bitset 了。然后和可达性对应的 bitset 与起来，然后 a 的修改就对完了！这一看就正解相关啊，b 的管他呢，写了再说。

大概在 9:50 到 10:10 间写完，手写了 bitset，感觉不太难写。写完可达性测了一遍样例，跑一秒左右，感觉还行。最后加入了暴力跳 next 找 b_{\max}，调了一调就过了样例，最后一个样例仅仅跑了 8s！

然后想了一会儿咋修改 b。想了半天还是只会二分，而且二分的内容看上去也难以维护，否则这个 \frac{nq}{4} 说不定值得尝试一下。欸但是这个 b 的带修能不能仿照一下 a 的带修，分分块，然后根据 WC 文艺汇演的相声：

找一个数在有序序列中的出现位置的时候，先分块！二分它在哪个块里，然后在块里二分！就做到了 O(\log\sqrt n)！

可以想到直接二分它在哪个块里（因为只维护了整块信息，查询还方便），然后暴力查询块内，这样完美平衡了一下单点查询的 O(1) 和整块前缀查询的 O(\frac n\omega)！

写一下。调了好久才过样例，之间一直在 sample 3 爆 RE，查了 \inf 年才发现数组开小了。然后测速，样例 7 跑 7s？是不是要卡一下常数了。然后找瓶颈，在 wa 的时候就调了一下块长，直接令 B=2000，发现速度不慢，瓶颈竟然不是二分了？是暴力跳？？输出了一下暴力跳的总次数，发现爆了，再仔细一看发现二分写了个 if(f=1)res=mid,r=mid-1？？？改掉之后样例 7 跑了高贵的 2.3s。直接通过？？

然后加了个文件，对着原版代码重新测了一遍样例。中途写了两个相邻的编译命令：g++ 1.cpp -o 1 -O2 -std=c++14 -fsanitize=undefined -fsanitize=address -Wall -Wextra，g++ 1.cpp -o -O2 -static -std=c++14。细心的同学已经可以发现问题了，我的样例 7 此时跑到了 11s！然后发现了，还是高贵的 3s 以内。这个时候是 10:36。简要题解全在上面了。

然后做一下 T3。说服自己先把全排列写了。时间复杂度看上去有点大，可能是 O(Tn!n^2)。然后想了一下发现第一项大概固定是 1，然后排列的排名估计不大，反正最多是 O(Tn!n)。样例过了就是过了！。

想了一会儿树发现没什么头猪。想了一个依次把数填进去，没想清楚就乱写了一下，发现完全不对。然后摆了，准备看一下链。第一个样例竟然很良心地是 1 在端点。猜了一手只能按顺序，全错了。然后直接在 .in 里手动 dfs，发现是从头开始，在前面或者后面放。这个直接倒着做然后贪心就做完了。1 不是端点的话，似乎两个部分只能嗯拼起来啊！取个小的就好了。飞速通过了，时间忘了。

然后换了一些新奇的想法做树。一直在想到底可不可以拿 1 当根然后每个子树都是区间。然后想了一下别的点似乎也能当根啊？又想了一下似乎固定根之后可以直接嗯贪心啊？这个没什么细节的样子。写了一个枚举根然后贪心。

具体地，遍历一棵子树的时候一定可以先填最小值。更具体地可以发现，可以按子树最小值排序（不妨把根也当作一个点），然后依次遍历，遍历到根相当于输出根。

肉眼过了但是 diff 出锅了，难过。改了好久行末空格然后 diff 过了？还不错。

然后在纸上画了棵大树手玩根的情况，然后发现最优过程似乎相当于直接拿 1 当根模拟。于是直接令 1 为根就通过了？试了一下还真的通过了？？这时是 11:32，T3 得分是 32。

然后推了一下森林，花了好久让自己相信一个树只能完整地塞到两个子树中间。上面都把根扔进去排序了，不妨把所有不同子树的最小编号点都扔到 queue 里，每次一直考虑队首，如果比下一个选择优就直接插入这整棵树！很好写，一遍过了样例。这个时候是 11:42，T3 得分 52。10 分钟得 20 分？

然后在草稿纸上想返祖边和横叉边。返祖边似乎比较容易，限制可能是除了第一个点，下面的必须都挂在最左边或者都在最右边。横叉边呢？这么难？lca 处似乎可以放最两边，或者根的同侧相邻。然后呢？和这两边的相对位置有关。

还是稍微写一下吧。欸那些非树边是哪来的来着。咋是 dfs 树啊？原来没有横叉边啊？？？

然后仔细想返祖边，发现似乎忽略了两条返祖边交叉的情况。用暴力玩了好久发现似乎如果有相交的情况就无解了，所以大概可以大胆实现。又想了一亿年细节，写了一半终于写不下去了。不管了，252 就 252。

然后去检查了一下文件，阅读了 pdf 发现 T1 的大样例咋全是特殊性质啊？再仔细一看好像问题不大。

然后交卷了。签字好慢。

出来问到了 tyx 240，yrq 208，cyx 128，pmd 100+20+100？？？gqh 196，chw 212，qzx 260……

吃完饭回来发现传说江苏只有 pmd 会 T3？ 260 是标准分？我成 A 队线了？仔细想了一下发现进 A 反正是不可能的事情，进 B 只要不像去年一样大翻车就还挺有希望。

T2 没人和我一个做法啊？

晚上学了一下 T3，大概是考虑这个平面图大概可以看成若干个环的并，两个环最多交一条边，然后差不多就很可做了。不管了，谁能有 pmd 的脑子啊？

晚上睡前又强制【数据删除 1】了一会儿，然后不知道为啥很久没睡着。

2025.3.2

快进到进考场。没啥信心。

密码是 ReM#Ain(LoVinG。问就是最后几分钟没事干就背密码。

T1 看着超级难。不会。瞄了一眼 T2，惊讶地发现数据范围咋又是 15。咋还有 10 个多测啊？这也太难了。T3 还是不太敢想象。

嗯想 T1。发现了一点 a_i<b_i 和题目等价。发现了每个点管的区间递增。发现了每个点对其它点的影响很小。发现了可以只考虑特殊时刻的总距离。发现了贡献的特殊计算方式（只考虑每个点到后面一个特殊点之间的点被它影响）。这个好像对完了，直接嗯维护一下是不是做完了。好像想了好久好久。

写写写，调了一万年样例，好像直接做到了 O(n\log n) 啊！样例好强，还总是有 n=5 的小样例给我调！挂了许多例如贡献算一半就不算了之类的小地方。过样例是 9:11。

然后看范围巨大无比就想改一改，尝试线性。把 set 换成单调栈就只剩排序了。那就是高贵的排序之外线性，很好啊！复制 6 遍 n\le 2\cdot 10^5 的大样例，跑了 0.2s。这时候是 9:25。

然后觉得样例太少了，写了个暴力模拟的代码，又调了一万年样例，又挂了写稀奇古怪的地方。然后过拍了。这时候是 9:37。

我到这时还没有发现这个模拟的过程可以直接线段树加速！！！甚至在写暴力前没有发现可以直接模拟。

然后觉得慢慢写暴力进队应该稳了，就一档一档写 T2。慢吞吞地写了半个小时过了 24，然后看了一眼 C 性质。仔细推了一会儿发现这个缩点之后可能很好看，然后缩点正好是主旋律，很好玩啊！先把主旋律写了。

不知道过了多久写过了主旋律部分。浪费很久时间的是计算 n=3 的三元环的答案手算错了以为代码假了。

然后接着推。没有发现任何度数相关的充要条件。我仍然在 dag 容斥！f(S) 表示 S 内的点已经组成了一个符合条件的 dag，然后往后面拼接一些没有出度的 SCC，要求到 S 都有边，然后再拼上一个 (-1)^{sz+1}。然后这个系数比较难绷，一个 SCC 连边的方案数是 2^e-1，因为要确保连通。我不太敢想容斥这个，然后直接想了拆括号。选一部分令它贡献是 -2^e，剩下的贡献是 1。然后把 -2^e 部分的东西先并在一起，然后再算 e 就可以算贡献了。转移先枚举 S，再枚举贡献是 -2^e 的部分，再枚举 1 的部分，做到 O(4^n)。调了一万年才过样例。

然后想的时候就大概意识到这个部分可以 subset convolution 了，然后我正好不会，然后新开了一个 cpp 开始现编。先编 or 卷积，运气很好一遍就编对了！其实这个东西我至少半年没碰过了，但是之前 CTT 背 ntt 的时候想起来似乎 ntt 和 fwt 长得一模一样，对着 ntt 编了一下，猜了一下系数，然后就一下编对了。然后回忆了一下改成子集卷积，调了好久 RE 之后也编对了！然后拼到代码里又拼了一万年，因为少写了一个 2。但是样例过了 11 和 12 过不去 14，想了一万年发现 2 的幂只意识流地预处理到 100（实际上不需要预处理这个，但我蠢就蠢吧），随便改成 600 就过了。时间复杂度 O(3^nn^2)。

卡了一下 fwt 的常数，结果 n=14 五组要跑八秒，简直没救了。似乎我的 O(4^n) 也有这个分啊？那我编了个啥？

然后就决心嗯做 T3 了。写搜子的时候没打算认真写，写了 set<vector<int>> 跑路。想过把序列哈希起来但是有点懒得写。后来想想 yyc 因此多过了一车分非常非常后悔啊啊啊。 然后看到 AB 性质主观感觉性质很强，不应该很难啊？然后用暴力和 n=3 来一步一步修我的意识流猜测，最后 O(nm) 过了样例。中途还挂过 a_1\neq 1，拜谢强样例。

然后编了一会儿状压，感觉状压没啥用，最后编不下去了，遂彻底放弃。这时候还剩十几分钟，查了几下文件，测了几遍样例就开摆了。一直默念着 172 其实也还行也还行也还行但是出来还是发现爆了。T2 少了那个 20 分真的挺痛的/ll

最后在猜标准分。猜了一手 100+64+44。结果是 100+100+8？？？这也能中。

站起来首先发现了 chw 的 152，然后 pmd 给我展示了一行草稿纸上的“我是 T3 战神！”，然后发现他是 100+52+80，遂破防。吊打标准分啊！算了一下发现只算 T3 落后 pak 一整个 100 分。这谁打得过他啊？

反正不管怎么挂基本上都进队了吧。

熨斗 D1T3 挂了 20。埃及吧过不过。