省选复健做题记录

· · 个人记录

前言

WC2025 的低分铁败北让我意识到 OI 不能光吃老本，企图依靠运气进省队。于是我决定好好开始写题。

这段时间的目标有两个：

因此这段时间的训练除了打模拟赛之外，会以限时训练 CF 2400~2800 为主。

WC 结束~1.30

1.25 南瓜赛

赛后反思。

比较复杂的题想到正解后千万记得手玩小样例！

1.26

南瓜赛 T3：*2600？80min

积累一下树哈希柿子 h(x)=1+\sum G(h(son))。

2048E - Kevin and Bipartite Graph:*2000 30min

碰到可能无解构造题当作 MO 的组合极值做就好了。

1.27

2049E - Broken Queries:*2400 25min

没有任何难度的小清新交互。

2043F - Nim:*2700 10+50min（过样例用时，没调出来）

如果区间长度 \ge 50 答案就是 1 或 2，\le 50 可以 dp。

ABC390F - Double Sum 3:*1801 10min

可能出于想练练省选第一题速度吧，可能只是想放松一下吧，我也不知道为什么我要做这么水的题

扫描线，每次从右边加一个数，维护答案变化量。

1.28

2060G - Bugged Sort:*2400 10+30min

又是小清新。正如万奆所言，CF 和 CNOI 风格差异还是不小的。

考虑对 (i,j)(j,k)(k,i) 连续使用三次操作。容易发现我们将其中两对 swap 了。因此我们能得到的数列都能通过任意打乱这些数对和偶数次 reverse 得到。

考虑含 1 的数对一定放在第一项；2 如果没有和 1 配对一定放在 1 后面。以此类推，我们可以得到：最终每个数对的顺序一定是按照 \min(a,b) 升序排序。最后为了兼顾“偶数次 reverse” 还要奇偶讨论 dp。

2056F1 - Xor of Median (Easy Version):*2700 不会+25min

到转化为斯特林数都想出来了（40min），最后一个 dp 只会 O(n^3) 且没发现是斯特林数有点太菜了。

1.29

CF2055E - Haystacks:*2800 40min+大过年不写题

我的思维比较松弛，干瞪了 30min 才转化成 \sum a_i-\sum b_i\le t。转化完后是 P3619 魔法。

CF2053I1 - Affectionate Arrays (Easy Version):*2800 假了+大过年不写题

一开始题目看错了就难绷。然后一直在思考贪心，寄了。

看了题解发现是优化 dp，得出 dp 方程是容易的，转移也是容易的。感觉这题挺好，有时间写一下。

1.30

在蕴秀斋口胡省选计划模拟赛 09，100+40+100 遗憾离场，并且第三题还不知道能不能写出来，感觉场上最多 100+40+40。

T1:*2700? 30min+没写

不妨设 a_i=0 后只保留线性基中的 b_i，则最后一个人的策略是自然的。

考虑倒数第二个人的策略，比如最后一个人的线性基里有 1100，倒数第二个人有 1000，那他明显可以控制（右起）第三位，控制不了第四位。

所以就是从后往前进行线性基合并。因为没有修改，直接猫树维护是对的，双 log。

T2:*3000+? 不会+没写

一开始想歪了，导致 30min 才想到对 a 状压，转化为无向图完美匹配计数。直接状压只有 40。

考虑钦定每次插入一条边时有一个端点是目前没有加入的最小点，一算状态数是 Fib_n，有 70。

正解是不妨设 n 偶，强令 2i-1 和 2i 加边，转化为数环，状态数压缩为 2^{n/2}。

T3 *2900? 30min+没写

首先树是假的，枚举两个叶子就划归为链，发现其中一个叶子没必要枚举（写一个可撤销数据结构好像就可以了）。

考虑两条链。在一条链上右端点扫描线，转化为如下问题：

一个 n\times n 的方格表，支持染黑 (1,y) 和 (x,y) 间的所有格子。要维护每个纵坐标上的白色连续段的权值 \max。保证修改的 y 递增。

倒序操作+线段树合并似乎是可以的？

总结

这段时间训练还是比较随性（日均打卡时间 <2h）；希望从蕴秀斋回来后打卡时间能达到 3h+/d，最好 4.5h+/d。

2400 还是较为容易的，省选（D1T1 除外）大概也不会放这么水的题；限时训练范围改为 *2500~\3000。

2.6~开学

2.6

P4284 [SHOI2014] 概率充电器：*2200? 秒+40min

换根 dp 的本质：删边后再加回来。

想到把期望拆到每个点后换根 dp。

1994G Minecraft：*2500 秒+没写

转化一下题意，然后按类似 学校食堂 的方法状压 dp。

P11673 [USACO25JAN] Median Heap G:*2200?10min+25min

考虑单次询问，显然只有和中位数大小关系是重要的（trick），所以本质不同的权值只有 3 种，一次 dp 求解即可。

考虑多次询问，把询问排序后每次修改 O(1) 个 dp 值即可维护。

P11674 [USACO25JAN] Reachable Pairs G:*2100?5min+20min

倒序操作。

P11675 [USACO25JAN] Photo Op G:*2400?5min+没写

注意到仅线段按照相交关系成的连通块重要。set 维护即可。

2.9

什么？2.7 和 2.8 呢？学 MO 去了

上午补 2.6 晚胡的 USACO 金组。

下午打 JRKSJ，T2 会双 log 没调出来，难绷，100pts 下播。

我 T2 的做法离正解只差一步却拿了 0 分？难绷

2.12

2045J - Xorderable Array:*2600 不会+30min

完全知道每一步要怎么做，但是懒得思考了。

2045K - GCDDCG:*2900 10min+没写

其实这个 10min 是假的，因为我以为 3log 过不了，一直在想优化想不出来，结果题解就是 3log

这题的主要难点在于把柿子写出来，之后的莫反是 easy 的。

2042F - Two Subarrays:*2600 5min+没写

动态 dp。

2.13

白天打 AIME，晚上开工。

CF2042E - Vertex Pairs:*2900 不会+懒得写 50min（但被卡常了）

没有想到钦定连通块含根（积累一下，含根的连通块是容易刻画的），然后就变成简单题了。

CF2041L - Building Castle:*2900 10min+计算几何狗都不写（

注意到答案是 2S_P-2\max S_{P\cap P'}。三分套三分枚举对称中心+半平面交。

2.14

上午写 CF2042E。

CF2041J - Bottle Arrangement:*2700 25min+没写

暂时只考虑判定答案是否为 0，求出答案同理。

考虑峰是确定的时候是容易的。

我们从大到小枚举 b 中元素，并维护所有可能作为峰的位置即可。

CF2040F - Number of Cubes:*2700 10min+没写

熟记 Burnside 引理：\dfrac{1}{|G|}\sum_g |X^g|。

用完以后推一推柿子就结束了。

CF2038M - Royal Flush:*2800 5min+没写

幽默数据范围。

本质不同的状态很少，直接 dp。

CF2038I - Polyathlon:*2500 30min 单 log+没写

想了三种亚平方做法，感觉都有一定启发性，和标答一起记录下来。

根号：考虑如果能快速确定下一个有人被淘汰的时刻就是 nmT(x) 的。暴力计算可以做到 T(x)=\min(n,m)。

双 log：每次从剩下的选手中随一个作为基准，二分哈希求出每个选手和基准第一次不一样的时刻，取这些时刻的 min 就是第一次有人被淘汰的时刻。如果不是基准被淘汰就没问题，如果基准被淘汰就需要重新随一个基准。因为基准的变化是 \log 次，所以 T(x)=\log^2。（upd：可以分析出单 log）

单 log：不需要选基准，维护相邻两列第一次不一样的时刻即可。

线性：和上面做法没有关系。注意到，每次胜出的选手是字典序 max，考虑倒序扫描每次比赛的答案，基数排序一下即得。

2.15

ARC192C - Range Sums 2:*2250 15min+没写

和标答不太一样的做法：初始下标集合为 \{1,2\}，每次插入一个下标，我们维护 P 中以它们为下标的元素的大小顺序。

设当前最大的是 P_r，最小是 P_l，要插入 P_{x}，我们查询 (l,x) 和 (r,x) 即可。

（upd:似乎有点假）

下午打了 TPOI Round 1 & 省选加油赛，不仅迟到四十分钟还打得像奶龙一样，100+100+100+5 耻辱下拨。

其实这个 T3 思维难度和细节数量都和季风差不多的。当时我季风只用了 1h，这个题用了 2h，我是不是退化了。

2.16

CF2038F - Alternative Platforms:*2500 10min+没写

Key：\sum\max(\min x,\min y)=\sum\min x+\sum\min y-\sum\min(\min x,\min y)。

三部分分别算就好，需要 FFT。

2.17~2.23 拥抱停课生活！

2.17

CF2035F - Tree Operations:*2500 25min+25min

固定 ans \mod 2n 二分 ans，树形 dp。

CF2038E - Barrels:*2900 20min+90min

尝试给出一个细致的思路。

容易发现，最优策略是从右往左填满桶。

把水面和管道均视作点，如果一个水面高于它相邻的管道，在其间联边。

维护每个时刻的连通块，则每次是往最右边的连通块里加水。

如果这个连通块最左端不是管道，那这个连通块水面上升，上升到与管道相平时合并；

否则就递归考察其左侧的连通块（即，水顺着管道流过去了）。

复杂度为 O(n^2)，发现瓶颈是找水面上升的连通块，但这也是可以维护的。O(n)

调了好久呢。

P10220 - [省选联考 2024] 迷宫守卫:15min(假了后又想了 30min)+懒得写

为什么去年场上一万年不会做今天再看直接秒了啊啊啊

Bob 的策略：

先二分第一位 mid。将 < mid 的符文 q_i 均视为 0，\ge mid 的视为 1，要求使 Q_1=1 且总花费最少。

最小总花费容易用 dp 统计：dp_{leaf}=[q_i=1]0+[q_i=0]inf,dp_i=\min(dp_{2i}+dp_{2i+1}\text{（睡）},dp_{2i}+a_i（醒）)。

于是我们求出了第一位。不妨设左子树是第一位所在的子树。

先递归求解左子树，再把剩下的所有 K 都投入右子树求出右子树第一个数，如果大于左子树第一个数就直接递归；如果小于则需要唤醒根节点再递归。

_AT_arc160f - Count Sorted Arrays:*铜牌 25min+

~如果你有一个同学，并且他的名字叫 wjq，那这道铜牌题就是水题~

Trick：排列计数/排序相关问题，n\le 18，可以先考虑 01 序列。

observation 1：m\le 5\times 10^5 是假的，实际上 m\le \binom{n}{2}。

observation 2：暴力求出每个 01 序列是否可以被排序，复杂度是正确的。

转化为高维格路计数。

2.18

CF2032F - Peanuts:*2700 10min+50min

熟记 Anti Nim 结论：若非全 1 则胜负性和 nim 一样。

然后变成简单题。

P11469 校园跑：*不知道 3min+

zzp 推的大好题。

设 f_i 为 n=i 时的答案，转移方程 f_i=\dfrac{1}{m}\sum_{j=1}^m \min(f_{i-1},a_j),f_0=\infin。

设 a 已经从小到大排序，注意到 f 递减，所以每次选 f_{i-1} 的决策点构成 长度递增的后缀。

设当前选 f_{i-1} 的后缀从 l 开始，我们可以倍增+矩阵乘法求何时后缀从 l-1 开始。O(m\log n)。

CF2045F - Grid Game 3-angle:*3000 1h- +一边想一边写

独立做出的 *3000，不容易啊。

首先发现它不弱于每次至多取 k 个数的 nim（做结论题时，发现严格不弱于它的题可能很重要）。但是这个题我不是很会做。考虑 SG 函数，只有一堆的 SG 值是好算的（即 x\bmod k+1），多堆直接异或起来。

于是我们发现每行\mod k 的异或很重要（记为 x_1,\dots,x_n）。猜想答案只与它们有关。

如果 x_i 全为 0，显然后手必胜。如果有 1，猜想先手必胜。交一发，WA 了。

我们找到反例：x_i=1,0,\dots,0,1，其中有 k 个 0。这时先手赢不了。

于是我们大胆猜测：只有 i\bmod k+1 重要，即每次 sg_{x\bmod k+1} 异或上 z\bmod k+1，它过了！证明是容易的。

2.19

P11219 -【MX-S4-T3】「yyOI R2」youyou 的序列 II:*2800（草皮说的）25min+120min

直觉告诉我们蓝方要防住两个点。即，如果 [l,r] 中蓝方能染到的最左和最右的点红方不能一步染到，则蓝胜，否则红胜。

线段树上二分求出这两个点即可。

但是 corner case 好多/kk，碰到这种情况记得在草稿纸上把流程写清楚。

CF2028F - Alice's Adventures in Addition:*2700 20min+

最优化问题一般先找性质，然后根据性质发现可以 dp 的结构 / 优化 dp 复杂度。

性质 1：每个 1 对答案或者没有贡献，或者有 1 的贡献。这启发我们把所有 1 剔除，判断结果能否介于 [m-cnt1,m] 间。

性质 2：每个乘法区间或者包含 0，或者长度 \le 13。

因此我们有暴力的 dp：dp_{i,j} 表示前 i 个数是否能合成 j。转移只要考虑前 13 项和前一个 0 的那一项。

然后发现可以 bitset 优化。O(nm\log/w)。

【mcw 给的坤题】:*【mcw 不让剧透】15min+没写

记录一下自己做过这个 mcw 不让外泄的题。

CF2030G2 - The Destruction of the Universe:*3100 30min 想出来 easy ver

好题，有三个关键步骤。

第一步是 P3286 - [SCOI2014] 方伯伯的商场之旅 的 trick：定义 dis(S)=\min_t\sum_{s\in S}|s-t|，求 \sum_{\text{一大堆集合}}dis(S)，可以考虑一开始所有集合的 t 都设为 1，每次 ++t 后计算偏移的集合的偏移量之和。

这题大致符合这种性质，但是 dis 是点到区间的距离之和。于是有第二步：注意到点到区间的距离是点到区间的两端点距离平均值减区间长度的一半。 于是我们拎出所有区间长度的一半单独求和，就把区间拆成其两端点。

当 t\to t+1 时，如何求出贡献的变化量？

对于一个点集 S，设有 a 个元素 \le t，b 个元素 \ge t+1，则 t\to t+1 时距离变小 b-a。但如果距离变大则不优，所以实际上是 \max(0,b-a)。

如果 l_i\le t,t+1\le r_i，则这样的区间加入 S 后 b-a 不变，它的贡献只是让答案 *2。记 A 为 r_i\le t 的 i 个数，B 为 l_i\ge t+1 的 i 个数。则变化量为：

\sum_{i=0}^A\sum_{j=0}^B\binom{A}{i}\binom{B}{j}\max(0,2j-2i)

对于 easy ver 想办法把它预处理出来就好了。对于 hard ver 需要快速计算（即为第三步，我没想到，混凝土数学白看了）。

我们枚举 j-i 并用范德蒙卷积：

&\sum_{i=0}^A\sum_{j=0}^B\binom{A}{i}\binom{B}{j}\max(0,2j-2i)\\ =&\sum_{d=0}2d\sum_{i=0}\binom{A}{i}\binom{B}{i+d}\\ =&\sum_{d=0}2d\binom{A+B}{B-d}\\ \end{aligned}

注意到在所有需要计算该式的情况中，A+B 的变化总量是 O(n) 的，于是用维护组合数前缀和的套路维护就好了！

CF2029F - Palindrome Everywhere:*2500 共 1h

不断对照样例对自己的结论进行修改。

P7519 - [省选联考 2021 A/B 卷] 滚榜:*2400 秒了复杂度假了只有 40pts+不想写

直接设状态发现复杂度是对的。 upd：是错的，不想改了。

P7516 [省选联考 2021 A/B 卷] 图函数：30min 想出 80pts

考虑计算原图的答案。那就是把点按 $1\sim n$ 的顺序添加，维护当前所有强连通块。直接暴力重构的复杂度是 $O(nm^2)$ 的。 其实上面的做法本质是每秒加一条边，维护每个时刻的所有强连通分量。 考虑在原图上加一条边对哪些时刻的哪些强连通分量有影响。容易发现，加一条边对某一时刻的影响就是合并两个强连通分量，且若上一时刻合并了 $a,b$ 所在强连通分量，这一时刻还会合并 $a,b$ 所在强连通分量（如果 $a,b$ 还没在一起）。 所有可以二分+tarjan 求第一次出现强连通分量合并的时刻并暴力合并。 ### 2.20 _P7521 [省选联考 2021 B 卷] 取模_ 爆标了。[https://www.luogu.com.cn/article/hrgn1kar](https://www.luogu.com.cn/article/hrgn1kar) **启示：这种看起来比较随机的最优化问题（比如这题，JRKSJ Ex T2 和 WC T2），一般都是找答案的一个显然的界，只有极少情况能突破这个界；或者设计一个剪枝的暴力，证明复杂度是对的。** _CF2026E - Best Subsequence:*2500 共 30min_ 即求子集大小减其覆盖集大小的 max。看上去有点像 Hall 条件？建出二分图跑最大匹配即可。 mcw 说是**最大权闭合子图模型。即，DAG，点有点权（可能为负），求最大权子图使得子图中任何一点走一步还在子图中。求法是：S 向所有正权点联边，所有负权点向 T 联边。** _CF2026F - Bermart Ice Cream:*2700 我之前好像胡过_ 建出操作树转化为单个 deque，用均摊重构的 trick。 _CF2025F - Choose Your Queries:*2700 45min_ 先建图，根据数竞的熟知结论，每个连通块至多有 1 的贡献。 考虑构造方案，即给定一张连通图，要求选出 $\frac{m}{2}$ 对边，每对有公共端点，每条边至多用一次。 树是容易的。对于图，可以用以下方法（**值得积累**）变成树： ![](https://cdn.luogu.com.cn/upload/image_hosting/q4mpc1a2.png) _P8207 [THUPC 2022 初赛] 最小公倍树:不会_ **积累特殊图最小生成树的 trick：环上（通常考虑三元环）最大边不在最小生成树上。** _CF2025G - Variable Damage:*3000 不会+没写_ **Trick：维护两个集合排序后的对位大小关系，考虑转到数轴上变成前缀的黑白点数量大小关系，然后再转成维护直线。** 相同的 Trick：_P3992 - [BJOI2017] 开车_ _CF660F - Bear and Bowling 4:*2500 10min+没写_ 从化简式子的角度入手，设出 $a_i$ 和 $ia_i$ 的前缀和，最终可以变出一个凸包的形式。 _CF1979E - Manhattan Triangle:*2400 秒+没写_ 曼转切。**熟记公式**：$x'=\frac{x+y}{2},y'=\frac{x-y}{2}$，则 $man(P_1,P_2)=2qie(P_1',P_2')$。 猜想：满足条件的三点必有两点平行坐标轴。证明是容易的。 _CF1866K - Keen Tree Calculation:*2500 5min+狗都不写_ 史。 ### 2.21 _CF2022E2 - Billetes MX (Hard Version):*2600 5min+没写出来_ 第一步是拆位将值域变成 $[0,1]$。 接下来刻画好的矩阵：$a_{i,j}=a_{1,1}\oplus a_{i,1}\oplus a_{1,j}$。 如果矩阵中每个元素都不确定，那答案是 $2^{n+m-1}$。如果至少一个元素是确定的，不妨把它拎到 $(1,1)$。 将每个 $a_{1,j}(j>1)$，$a_{i,1}(i>1)$ 看做点，$a_{i,j}(i,j>1)$ 看做边构造二分图。则每个连通块的贡献是 $0/1/2$。 _CF2021D - Boss, Thirsty:*2500 10min+_ 考虑定义状态 $dp_{i,j,k}$ 为 上一次选了第 $i$ 行的区间 $[j,k]$，但是已经超时了。 我们转化题意：先选 $n-1$ 个数 $x_1,\dots,x_{n-1}$，再选每行的区间 $[l_i,r_i]$，要求 $x_i\in [l_i,r_i],x_i\in [l_{i+1},r_{i+1}]$。 设 $dp_{i,j}$ 为前 $i$ 行，$x_{i-1}=j$ 的答案。转移要枚举 $l_i,r_i,x_{i-1}$，但发现是可以前缀和优化到单次转移 $O(1)$ 的。 _CF2023F - Turtle and Three Sequences:*2800 不会_ **很少的数两两不同，考虑值域随机映射刻画。** 转化成值域很小的情况，就是一个状压 dp。 ### 2.23 2.22 被 MO 干爆了，没做题。 _2013F1 - Game in Tree (Easy Version):*2700 10min+没写_ 首先如果 Alice 不是往 Bob 的方向走 / Bob 不是往 Alice 的方向走（称为“当怂货”），则其实就是拼两个人还能走到的连通块的深度。由于第一次当怂货的时刻只有 $O(n)$ 种可能，我们可以枚举。 这样只需要知道每个人走到的连通块直径的两端点。连通块的直径是可以合并的，做完了。 _2009G3 - Yunli's Subarray Queries (extreme version):*2700 15min+没写_ 显然的转化是 `b[i]-=i`。然后发现答案只与长为 $k$ 的区间众数有关。转化成 _P3246 - [HNOI2016] 序列_。 _CF2005E2 - Subtangle Game (Hard Version):*2500 不会+没写_ ~~真难绷，我 5min 想到正解然后把它 hack 掉了。~~ 首先有显然的 $n^3$ dp。然后发现为了压缩对手的生存空间，对 $a$ 数组的每个位置只会有 $O(n)$ 个状态。 ## 总结 停课之下的我效率还是会比假期高不少的。 但是仍然存在诸多不足，详见 [https://www.luogu.com.cn/article/89y7iwsa](https://www.luogu.com.cn/article/89y7iwsa)。 # 2.24~2.28 ### 2.24 _CF2003E2 - Turtle and Inversions (Hard Version):*2700 25min_ 爆标！线性做法。 题目给的条件比较鬼扯，但是翻译一下就发现，好的排列都存在 $k$，使得 $\le k$ 的记为 0，$>k$ 的记为 1 后，每个区间都有 0 和 1，且 0 的出现是一段前缀，1 的出现是一段后缀。 这是一个不错的刻画，但我们还可以更好。考虑拎出所有左断点和右端点，在左端点写一个左括号，右端点写一个右括号。则原来哪些左括号和右括号是匹配的不重要。 断言：对括号串建树一定是若干条链（即`((((()))))()((()))` 这样）否则无解。证明是容易的。 同时，注意到如果括号串出现嵌套（形如 `(...()...)`），则左边的省略号处只能填 0 ，右边全 1。 这时问题划归为 E1。 从大往小扫描 $k$，要最大化逆序对。每次是将第一个可以改成 0 的 1 改成 1，简单维护即可。 _CF2002F1 - Court Blue (Easy Version):*2600 20min_ 人类智慧+打表找规律题。 打表找所有能走到的点，发现质数行 / 列能走到很多点，于是考虑素数间隔是非常自然的。 ### 2.25 省选临近，我的代码却练得少了。今天暂停胡题，把一些胡过的觉得应该写的题写一写。下面记录写这些题的心得。 _CF2045K - GCDDCG_ 日了一早上没日出来，mcw 劲爽爆标。 柿子第一步就推错了，然后带了个小样例进去是对的，我就觉得自己没推错。调了一早上发现是这里错了 /oh “遇到一个思想正确，但细节可能不是很完备的结论，试两个小样例确定所有的细节。”——zzp _CF2040F - Number of Cubes_ 日了一下午日出来了。 柿子第一步就推错了，然后带了两个小样例进去是对的，我就觉得自己没推错。调了一下午发现是这里错了 /oh/oh/oh ### 2.26 一道题没写。 一直在和 cjld，CP 双排，完全没有自己写题的欲望。 ### 2.27 _1994G - Minecraft_ 状态定义比较奇怪的题记忆化搜索写法异常好写。 --- 这好像就是我在役的最后几天干的事了？