10 月做题记录

· · 个人记录

CF2146E Yet Another MEX Problem

经过一定尝试，我们发现区间快速求 mex 并不好做，因为 mex 本身的含义太复杂了，我们尝试解构 mex，即考虑其定义：不包含于 a 的最小自然数。我们尝试考虑所有不包含于 a 的自然数。

对于数列 a，以及 x \notin a，我们记 g(a,x) 为 a 中大于 x 的数的个数。若 x \in a，我们规定 g(a,x)=0。

显然，w(l,r) = \max_x g(a_{l..r}, x)，故

ANS_r = \max_{1 \le l \le r}\max_x g(a_{l..r},x)

然后就是常见的、类似交换求和的技巧：

ANS_r = \max_x \max_{1 \le l \le r} g(a_{l..r}, x)

我们在扫描 r 的时候维护关于 x 的数列：b_x = \max_{1 \le l \le r} g(a_{l..r}, x)。

单个的 b_x 如何计算呢？

显然 l 一定是选择使得 a_{l..r} 不包含 x 的最小值。由这一计算方法，我们发现可以用线段树维护。需要区间加、单点修改和区间 max。

小结：

第一步看似复杂化了问题，但实际上给了我们更多的操作空间，因为 mex 是一个被封装过的概念，我们对其进行拆解可以获得更多信息。

这与一些和式技巧十分相像。同时这也是一个比较一般的方法可以经常尝试使用。

P12427 [BalticOI 2025] Tour

这种题目一般要么乱搞（但是失败了），要么重建图，把奇怪的关系封装在图里，然后用标准算法跑。

我们以边为点，以转移关系为边建图。此时边数为 m^2，我们考虑增加中转点减少边数，但由于有颜色限制，我们不能直接用原图的点当中转点，而是根据二进制拆点，因为两个颜色不同，一定存在一个位不同。

我们用 id(x,j,b) 表示原点 x 对应中转点，其满足指向其的点颜色第 j 位都为 b，其指出点颜色第 j 位都为 \neg b。

最后 DFS 找环即可。

P10596 BZOJ2839 集合计数

公式要背：容斥原理 & 二项式反演

$$ \begin{align} f_k = \binom{n}{k}(2^{2^{n-k}}-1) \\ f_k = \sum_{k\le i\le n}\binom{i}{k}g_i \end{align} $$ 对 $(2)$ 应用二项式反演得到 $$ g_k = \sum_{k\le i\le n}(-1)^{i-k}\binom{i}{k}f_i = \sum_{k\le i\le n}(-1)^{i-k}\binom{i}{k}\binom{n}{i}(2^{2^{n-i}}-1) $$ **小结**： 做题的时候也可能先想到用 $(2)$。 ### 审题：P11922 [PA 2025] 叠积木 / Wieża 塔的大于号看成大于等于。 ### P11912 [PA 2025] 集合 2 / Zbiory 2 再次被构思题创飞，[solution](https://www.luogu.com.cn/article/eq3bszxc)。 ### 典：P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava 感觉是很经典的优化建图。 首先我们以边为点重新构图就能很方便地确定边权跑最短路，但一个点周围地左右边构成完全图，所以需要优化。 由于边权是由点权（新图）差得到的，所以发现可以删到只剩一条链，链上点权有序。 ### P13691 [CEOI 2025] highest 很好地强化了我对倍增地理解。 倍增地本质是将**操作序列**进行**压缩**。 我们的思路是用 $f_{j,i}$ 表示从 $i$ 花费 $2^j$ 能跳到的最远点。但仅仅这样无法转移，也无法解决询问。 原因是对于某些操作序列，我们花费 $2^j$ 可能跳到某个 `2` 的“中间”。于是我们在用 $g_{j,i}$ 表示花费 $2^j-1$ 跳的最远距离即可。 因为能挑到的位置显然是连续的，所以可以用 ST 表转移。这有一个细节，理论上从 $i$ 花费 $1$ 不能仍停在 $i$，但我们不用管类似的情况，因为总是不优。 查询时因为不能存下 $n \log^2 n$，所以要离线做“整体倍增”。总复杂度 $(n+m) \log^2 n$。 ~~不知道单 $\log$ 怎么做的。~~ ## R19 ### T1 可以发现每个前缀永远都是在一个区间内的，因此最后一定形如从某个位置开始每次向左或者向右加数，并且一个数是从左还是从右加只和它后面的操作次数的奇偶性有关。 因此倒着扫一遍，维护操作次数的奇偶性，然后判断当前数字是加在前面还是后面。 时间 $O(n+m)$。 **小结**：赛时为了给 $a$ 排序用了一个计排，T 了。实际上我们只需要 $a$ 的 $cnt$ 即可。 ### T2 $f(n)=n-\varphi(n)$，其中 $\varphi(n)$ 为欧拉函数。 注意到如果 $n=pq$，其中 $p,q$ 为不相同的质数的话，$\varphi(pq)=(p-1)(q-1),f(pq)=p+q-1\Rightarrow p+q=m+1$。 注意到在 $10^9$ 范围内哥德巴赫猜想是成立的，并且我们可以直接从小到大枚举较小的那个质数，判断 $m+1-p$ 是不是质数，在本题范围内枚举的量是很少的。 **小结**：因为这是个构造题，所以 $n$ 很可能是某个特殊形式的，我们需要多做尝试。 ### T3 注意倍增数组开的顺序要根据循环嵌套的顺序来，内层循环灭据的指标要开在第二维。 #### 解法 1 路径 $p,q$ 有交 $\Leftrightarrow $ $p$ 的 $lca$ 在 $q$ 上或者 $q$ 的 $lca$ 在 $p$ 上。 因此可以算光覆盖了询问的 $lca$ 的权值和，加上询问覆盖的光的 $lca$ 的权值和，减掉 $lca$ 相同的情况。 我们先思考一个 $lca$ 被光覆盖的权值和如何计算，显然就是一个路径加，单点求值。 另一个问题是单点加，路径求和，但显然可以转化成上述情况。 所有的都可以用树上差分 $O((n+m+q)\log n)$ 维护。 **小结**：做题的时候要维持清晰，不时总结一下当前的进度，比如转化为了什么问题，有什么信息。 #### 解法 2 根据点边容斥，一棵树总是满足点-边=1。而路径的交还是路径，路径也是树也符合点边容斥，因此我们可以求出覆盖每个点的路径个数，减掉覆盖每条边的路径个数，那么每个相交的路径会恰好被计算一次，同样是树上差分。 **小结**：路径求和只要是静态的是用不到树剖的。另外**点边容斥**很经典。 ### T4 不妨设 $x<y$，$=$ 的情况是若干条链是容易处理的。 设 $g=\gcd(x,y)$，那么 $\bmod g$ 不同的点是独立的，接下来考虑 $x=x/g,y=y/g,\gcd(x,y)=1$​。 #### 解法 1 建立一个网格图，$i$ 的坐标是 $(\lfloor \frac{i}{y} \rfloor,(i\times x^{-1})\bmod y)$，那么 $+y$ 就是向下一行连边，$+x$ 就是向右\向右下连边，其中最后一列的右侧是第一列。 这样我么能得到一个网格图，考虑直接按行 $dp$，用类似轮廓线 dp 的记录当前轮廓线上每个点是否选了，这样的复杂度是 $O(n2^{y})$。 注意到我们还可以反过来对列 dp，但是这样需要记录第一列和最后一列之间的边选择的状态，时间复杂度 $O(n2^{2(n/y)})$。 把 $y$ 按照 $\leq \sqrt {2n}$ 分治，即可得到 $O(n2^{\sqrt {2n}}) $ 复杂度的做法。 #### 解法 2 从一个点出发进行 BFS，将点按 BFS 序排成一行，可以认为有边相连的两点不会隔太远，然后跑 $x,y \le 15$ 的做法（即只记录前最后的 $15$ 个点）。 #### 小结 两种做法都做了一件事，即对点重新排列使得边不会跨越太远。 ## M14 ### A 简单换根 DP，要二进制拆位。 ### B 先考虑一个区间 $[l,r]$ 如何解决。设最大 $highbit = p$，其出现次数为 $c$。 于是当 $c$ 为奇数，且 $len\ge 2$ 的时候 $G(l,r)=2^p$。当 $c$ 为偶数的时候，$len \ge 5$ 时 $G(l,r)=0$。 对于 $len \le 4$ 的情况，我们直接暴力计算。 对于处理询问，我们可以预处理一些前缀和之类的东西来计算，并不困难。 ### C（待补） $n\le 10$ 时只需暴力枚举所有可能的树. $k=0$ 时只需判断 $n$ 是否形如 $2^k-1$. $k=1$ 时可以暴力枚举在满二叉树上不平衡的节点, 是否合法只与此节点的深度有关. 或者直接判断 $n$ 是否形如 $2^p-2^q-1$. 对 $k$ 较大的情形, 考虑如下对树的刻画: 从上往下考虑, 假设当且节点高度为 $h$, 则有两种情况 + 他有两个高度为 $h-1$ 的子树. + 他有两个高度分别为 $h-1$ 和 $h-2$ 的子树. 按 $h$ 从大到小处理, 只需关心有多少已经生成的节点高度是 $h$ 和 $h-1$, 在动态规划时记录有几个不平衡节点即可. 直接实现此做法的时间复杂度约为 $O(n\log n\cdot k^3)$. 事实上, 我们不关心具体的 $h$, 因为假设有 $x$ 个高度为 0 和 $y$ 个高度为 -1 的点, 总会生成出一棵总点数为 $2x+y-1$ 个点的树, 因为每次合并两个点, 生成一个点. 假设有 $x$ 个高度为 $h$ 和 $y$ 个高度为 $h-1$ 的点, 有 $k$ 个不平衡节点的方案数为 $f_{x,y,k}$, 则转移时枚举 $x$ 个种有 $c$ 个不平衡的儿子, 转移到状态 $f_{2x+y-c,c,c+k}$. 根据刚才的观察, 我们只需要求出所有 $2x+y-1=n$ 的 $f_{x,y,k}$ 的值. 而上述转移时 $x$ 几乎总是除 2. 使用记忆化搜索倒过来转移, 总共扫描到的状态数为 $O(\log n \cdot k^3)$. 每次枚举转移时间复杂度即为 $O(\log n \cdot k^5)$, 事实上常数很小, 可以通过. ### D 根据传统的 dp 过程，维护 $cur$、$ans$ 和 $dif = cur - ans$。 每次执行 $cur = cur + a_i, \quad dif = dif + a_i$。如果 $cur < 0$，则 $dif -= cur, \quad cur = 0$。如果 $dif > 0$，则 $dif = 0$。不需要显式地维护 $ans$。 考虑将所有数都表示成 $\sum c_i \cdot 2^i$ 的形式，其中 $c_i = 0, 1, -1$。 则所有加法和减法操作均摊只需要执行 $O(1)$ 次。使用 set 维护这几个数即可。 使用 set 或者主席树直接维护 $1$ 的连续段也是正确的。 部分分是通向正解的阶梯。 **小结**：因为我们维护的庞大数字不能快速地比较大小，但是能快速判断与 $0$ 的大小关系，于是 $a<b \Leftrightarrow a-b<0$ 即可。 --- ### AT_arc104_d [ARC104D] Multiset Mean **经典 trick**：一般平均值需要和元素个数搭配才能和总和相互转化，但平均值为 $0$ 时是特殊的。 于是我们枚举 $x$。将所有元素减去 $x$，即求在 $[1-x,n-x]$ 中取数使得和为 $0$ 的方案数。这是一个多重背包。 我们记 $f_{i,j}$ 为前 $i$ 个元素总和为 $j$ 的方案书。但是如果正负物品混到一起，写起来有点麻烦。 我们可以把正负分开处理，$f$ 仅记录正数情况，因为负数是对称的，$0$ 的选取是任意的。于是 $$ ANS(x) = (k+1)\sum_{0 \le j \le n(n+1)k/2}{f_{x-1,j}f_{n-x,j}} - 1 $$ 多重背包可以前缀和优化，总复杂度 $O(n^3k)$。 **关于前缀和优化多重背包** ```cpp f[0][0]=1; int sum=0; rep(i,1,n){ sum+=i*m,l+=m+1; rep(j,0,i-1) f[i][j]=f[i-1][j]; rep(j,i,sum) f[i][j]=(f[i-1][j]+f[i][j-i])%P; int l=i*(m+1); per(j,sum,l) f[i][j]=(f[i][j]-f[i][j-l]+P)%P; } ``` 最后一个循环是处理物品数量的限制（前缀和 $\rightarrow$ 区间和），是和完全背包的区别点。 ### P11131 【MX-X5-T3】「GFOI Round 1」Cthugha #### 解法 1 建有向图，指向一个点的边权为其点权。跑 SPFA，在 SLF 和 LLL 优化的加持下可以通过（但不会 LLL，只用 SLF 会 T 一个点）。堆优化也可以。 注意 SPFA 判环中，$cnt_x$ 表示经过了几条边，所以计算应该是和松弛放到一起，而不是直接自增。 #### 解法 2 建无向图，边权为两点权和。对于无解情况，我们发现当且仅当相邻点权值之和为负数。 于是可以跑 Dijktra。 ### P10715 【MX-X1-T3】「KDOI-05」简单的序列问题 **转化 1**：显然可以先对 $a_i$ 取模。$S$ 会有一个直接关于 $a$ 的计算方法：从第奇数个 $1$ 走到第偶数个 $1$ 之前的段的长度和（虽然这个计算方法是无关紧要的）。 **转化 2**：关键转化，观察转化的费用是两点权值和，涉及交换的问题我们处理起来是困难的，于是考虑把一次“交换”拆解成两次“改变”，花费为 $c_i$。我们发现，只要最终 $0/1$ 数量对的上，总存在交换方案与之效果相同且花费相同。并且显然对于任意交换方案，也存在与之对应的改变方案。 然后显然就可以 DP 了，可以滚动数组优化。 MicroSun 指出这题可以从区间翻转的角度解决。 如果写了有返回的函数却没返回，则会发生不可预知的错误，这体现了 `-Wall` 的重要性。 ### P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天 有点意思。最大子段和变种。 **Case 1**：没有“半选”，此时 `00` 令 $sum$ 减 $1$，`01` 和 `10` 不变，`11` 令 $sum$ 加 $2$。 **Case 2**：有“半选”。因为“半选”在数量不超过 $2m$ 时是纯纯负收益，所以我们可以认为一开始就欠了 $2m$ 的价值。补上来了就是合法解，没补上来虽然非法，但一定不如 Case 1 的答案，所以无所谓。然后最大子段和，注意需要记录前一个位置的选择情况。 ### 经验：P11219 【MX-S4-T3】「yyOI R2」youyou 的序列 II 这种题一看就是要分析一个结论来高效判断输赢，因为这个博弈过程硬做实在太复杂了。 先考虑 $[1,n]$ 上的博弈问题。 零散地分析一些性质： 1. $\max_{1 \le i \le n}a_i \le w_1$ 是 youyou 赢的必要条件。 2. 如果存在两个点 $x,y$ 能被 yy 覆盖，但是不能被 youyou **一次**覆盖，那么 youyou 会输。 性质 2 的否命题同样正确，即：如果对于所有 yy 能覆盖的点，youyou 可以一次覆盖，那么 youyou 会赢（当然假设性质 1 的条件成立）。 剩下的就是维护 yy 能覆盖的最左最右点，可以用一个数组表示长为 $c_2$ 的区间和，线段树维护，查询可以二分。 最后判断一下边缘情况。 **小结**： VP 的时候基本把重要的东西分析得差不多了，比如 youyou 要输的话需要有两个点形成牵制，但就是没有有效的总结出结论。 一个有效得方法是把已知得结论列下来，写到草稿纸上。 总的来说，做题的时候应该自信一点，坚决一点，细致一点。 ### P11220 【MX-S4-T4】「yyOI R2」youyou 的三进制数 首先要想到将原题目转化为图论模型，否则一切都无从下手。 然后观察一个性质：所有 $b$ 与 $c$ 的交点都是同一个。这点比较显然。 然后是圆方数相关计数，非常简单。可以树上差分实现。 ### 待补：P11236 [KTSC 2024 R1] 水果游戏 一个经典的套路是：如果我们对一个问题有迭代做法，那么我们很可能可以用线段树进行多次查询的加速。 **OBS 1**：如果出现一个数小于两边，则两边相当于被隔开。 ### 二维平面视角：P14255 列车（train） 将区间信息放到二维平面上问题将变得易于解决。 将区间的左端点看作横坐标，右端点看作纵坐标。我们所维护的删除区间一定是递增的。 可以用线段树维护 $x$ 轴上的某种“拐点”，暴力单点修改，用势能可以说明复杂度。 **小结**：二维平面、图，都是常用视角。 ### AT_arc107_d [ARC107D] Number of Multisets 朴素地设计 DP：$f_{i,j} =$ 大小为 $i$，和为 $j$ 的多重集个数。 **转移**： 1. 若有 $1$，$f_{i,j} \leftarrow f_{i-1,j-1}$。 2. 若无 $1$，则可以由其他情况整体除以 $2$ 得到，即 $f_{i,j} \leftarrow f_{i,2j}$。 **小结**：可以和 AT_arc201_b 放到一起看。与 $2^k$ 相关，涉及整体乘除 $2$ 进行归化的思想。 ### P11234 [CSP-S 2024] 擂台游戏 ### *AT_arc186_d [ARC186D] Polish Mania **这题是不是不转换也行？** 一个显然的观察：一个 Polish 序列唯一对应一颗树。 我们要统计某种复杂序列的数量，理想的方法是找到等价条件。 **等价条件**： 1. $\sum a_i = n-1
  1. \forall m<n, \sum_{1\le i\le m}a_i \ge i

然后类似数位统计，加上格路计数。需要用到经典的反射容斥。

*QOJ7649 序列

非常像 BJMX 的一道题，观察到一个递归结构然后可以 DP。

一个神秘技术：n 固定时，f_{n,m} 是关于 m 的多项式，于是用拉格朗日插值解决 m 很大的情况。

*AT_arc117_e [ARC117E] Zero-Sum Ranges 2

连续段 DP，熟悉不同角度的 DP。

*AT_arc118_e [ARC118E] Avoid Permutations

考虑用所有路径减去经过了黑点的路径得到答案，这里需要一个容斥。

考虑用 f_{i,j,k} 表示走到 (i,j) 经过 k 个黑点的路径数。如果黑点的排布是任意的，那么这样就可以了。

但本题黑点是按照排列来排布的，即每行仅有一个，每列也仅有一个，所以加两个 0/1 位来表示即可。

反悔贪心与模拟费用流：P11268 【MX-S5-T2】买东西题

可以建费用流，但是没用，不如匹配模型简洁，而且增广模式不是按照 SSP 算法的，如果先入为主会陷入误区。

我们考虑将物品按 a 升序排列，优惠券按 w 升序排列。不妨假设所有物品都先使用折扣。

考虑增量过程，物品 i 如何抉择：

  1. 直接吃折扣。\Delta=0。
  2. 拿一个没有匹配的优惠券。\Delta=(a_i-b_i)-v_j，j 为某个优惠券。
  3. 拿一个有匹配的优惠券，看上去会引起一系列变动，但实际上发现被夺走优惠券的物品如果去拿另一个券，不如直接让 i 匹配。\Delta=(a_i-b_i)-(a_j-b_j)，j 为某个优惠券匹配的物品。

我们可以考虑为优惠券赋一个新权值 d：

  1. 未匹配，d=v。
  2. 匹配 j，d=a_j-b_j。

算法过程会保证当前的答案为考虑前 i 个物品的最优解（一般的贪心都是如此）。

P10997 【MX-J3-T4】 Partition

十分巧思的一题，把贡献拆一拆，可以等价转化为两次可重叠的染色，并且两次是独立的。

经验：P11064 【MX-X4-T4】「Jason-1」一步最优

当我们遇到一个与经典问题的相关的问题时，不要怼着一种经典算法想，因为不同算法有不同优势。像这里我没想起来经典的线段树维护最大子段和。

P11158 【MX-X6-T4】夢重力

改变统计顺序。

没有关键点的子矩形贡献为 2\binom{n/2}{2}，有一个关键点的贡献为 1。

后面的计数没做出来。

暴力是 O(n^2) 的，我们考虑一行一行考虑，每行考虑纵向的一段区间，维护区间内的点，然后就可以根据点之间的空隙数数了。

之前老想用神秘数据结构。

警示：P5058 [ZJOI2004] 嗅探器

虽然这题极为简单，但还是有个细节要注意：判断割点 u 是否可以为信息中心，要用 dfn[t] >= dfn[v] 而不是 dfn[t] > dfn[u]。因为 u 为割点，且 t 在子树 u 中，并不能说明会断开，因为仍可能在同一个点双内（割点不一定会断开一切儿子）。

P7907 [Ynoi2005] rmscne

注意到合法性的“传递性”，这题就容易了。还有子区间是一个后缀的前缀。