09.28-10.4 学习记录

发表于 2026-10-06 更新于 2026-10-14 分类于学习记录

9.28

VP CF 1124 Div.1

C

题意

给你一个长度为 $n$ 的序列，定义一个区间的价值为：

$m = \max a[l…r]$
$val = (m & a_l) \oplus (m & a_{l+1})\oplus…\oplus (m & a_r)$

求最大价值。$n \le 2\times 10^5,a_i \le 2^{18}$

赛时思路

这个数据范围看来要打一个 $O(n \log V)$ 的算法。
这种题一般都是要钦定某一个东西的。比如左端点或最大值？
1. 尝试钦定区间最大值：
  1. 因为 $a & b \le \max(a,b)$，$a& a=a$，所以 $m$ 依然是区间最大值。
  2. 稍微思考一下后发现 $\max val = m$。
  3. 于是我们从高到低考虑 $m$ 的这一位能不能取。如果这一位是 $0$ 定然不能取，如果是 $1$，要求区间里有奇数个数这一位是 $1$。显然 $m$ 可以贡献一个 $1$，但是如果都是 $m$ 在贡献那也不合法，因为区间长度至少为 $2$。这样貌似做不了。
  4. 猜测：区间长度越长，$val$ 越小。并非。
2. 尝试钦定区间左端点：
  1. 同样地尝试从高到低构造序列价值。
  2. 这个好像更不可做，序列信息更少。
不是很懂啊，用时 $24$ 分钟。

订正

考虑求一个序列 $val$ 的过程：
1. 首先找到最大值
2. 在最大值两侧找到左右端点。
一些关键洞察：
1. 题面的式子等价于 $(a_l \oplus a_{l+1} … a_r)\ &\ m$
2. 区间异或和，想到差分。区间信息想差分还是不够敏感啊。
发现这和笛卡尔树的结构非常吻合。于是我们建一棵笛卡尔树。
1. 钦定区间最大值，在左右子树找左右端点。
  1. 先弱化一下问题，如果每个数不需要 $& m$，这是一个经典 Trie 找最大异或和的问题。启发式合并。
  2. 但这题 $& m$ 使得问题变得复杂，不能对弱化解法进行推广，于是我们换种思路。
2. 直接从高到低位贪心，记当前答案为 $ans$，看 $ans$ 的每一位能不能填 $1$。
  1. 这样子就将问题转化为了一个判定问题，显然只有 $ans\ & \ m = ans$，即 $m$ 包含 $ans$ 的子树上才可能贡献答案（如果 $ans$ 的 $1$ 在 $m$ 这里是 $0$，说明一定凑不出 $ans$，因为最后的结果要 $& m$）。
  2. 那么我们就在这个子树的左右找，看存不存在一个 $(s_{l-1} \oplus s_r\ & \ m)\ &\ ans=ans$。因为 $ans$ 是 $m$ 的子集，所以式子等价为：$s_{l-1} \oplus s_r\ &\ ans=ans$。
  3. 对于 $ans$ 每一位，我们都更新一遍 $s$ 的取值，然后再这上面启发式合并，判断存不存在 $s_{l-1} \oplus a_r=ans$。
时间复杂度 $O(n\log V \log n)$。

D

题意

一个下标 $i$ 移动一次，可以移动到：

左边任意位置。
右边第一个比它大的数的位置。

定义 $f(i,j)$ 表示从 $i$ 到 $j$ 所需最少的操作次数，达不到就是 $0$。求 $\sum f(i,j)$。

$p_i \le n \le 10^6$

赛时思路

对于 $i>j$，$f(i,j)=1$，一共有 $\frac{n(n-1)}{2}$ 个。
只需要考虑 $i<j$ 的操作次数了。此时 $j$ 在 $i$ 右边，那么 $i$ 的操作是固定的，不断找到右边第一个比它大的数。只有在越过 $j$ 时会考虑向左。如果不能越过 $j$，说明 $p_i$ 是当前的后缀最大值，无论什么方案都得经过 $p_i$，此时无解。
这时候就有两个方向了：
1. 模拟过程：
  1. 钦定 $i$，每次跳到 $r_i$ 的时候，$[last+1,r_i]$ 这个区间加上跳跃次数。$[0,2,2,1…,3,3,2…]$ 这样的。
  2. 考虑先当作 $[0,2,2,2…3,3,3…0,0,0]$ 算，最后再减去链的长度。在差分意义下考虑这个操作，是 $[0,2,0,0…1,0,0…1,0,0…,-4,0,0]$ 这样的。
  3. 我们考虑维护这个差分数组。
2. 跳出过程，从序列结构上理解它。
放弃了，太复杂了，用时 $86$ 分钟。

订正

首先考虑 $f(i,j)$ 的过程。
1. 要么是一直往右跳，跳到越过再回来。
2. 要么是先往左跳一步，然后跳到越过再回来。
考虑无解（也就是 $f(i,j)=0$ 的情况）
1. $r_i=i$ 的点会将整个序列划分成很多快，不同块之间不能相互到达。
2. 如果 $i$，$j$ 处于不同块则无解。
计数题，考虑将贡献拆到起点 $i$ 上：
1. 如何计算 $f(i,j)$ ，其中 $i<j$ 的和呢？此时应该能想到 dp，因为跳跃的过程是由 “子过程” 拼接而成的。
2. 用 $g_i$ 表示这个量，考虑如何转移 $g$。用形式化的语言表达量，这个意识还是比较缺乏。
  1. 因为是从前往后跳，所以 $i$ 一定从 $i<j$ 转移。
  2. 转移需要在已有的基础上新增一段，我们来考虑新增的是哪一段。
  3. 新增的 $j$ 和两步能到达的范围有关（一步的话显然不能转移），令 $x = i$ 两步能到达的最右位置，于是我们开始讨论：
    1. $x=r_i$，此时无法在两步之内走到大于 $r_i$ 的点。
      1. 对于 $i>j$ 的点，从 $i$ 和 $r_i$ 出发是一样的步数。
      2. 对于 $i=j$ 的点，走的步数比 $g_{r_i}$ 少 $1$。
      3. 对于 $i<j$ 的点，走的步数都比 $g_{r_1}$ 多 $1$。
      4. 因此 $g_i=g_{r_i}+R-i-1$，其中 $R$ 是当前块末尾。
    2. $x>r_i$
      1. 对于 $x\le j$ 的点，从 $i$ 出发比从 $x$ 出发多 $2$ 步。贡献 $2(R-x+1)$。
      2. 对于 $r_i<j < x$ 这个范围内的点，可以通过 $r_i$ 走两步，也可以通过 $x$ 走三步，还可以通过向左跳地比 $r_i$ 高再向右跳。我们统计那些两步能到达的点的数量。
        
        $r_{r_i}$ 贡献一个，如果它小于 $x$ 的话。
        
        从 $i \to k \to j$，要求 $k<i \and r_k=j$，记这个 $j$ 的数量为 $c$。
        
        这部分贡献 $2(x-r_i-1)+(x-r_i-1-c-[r_{r_i}<x 且 r_{r_i} \notin c])$。
      3. 对于 $j=r_i$ 的点，贡献 $1$。
      4. 对于 $i<j< r_i$ 的点，可以通过跳到 $r_i$ 再跳回来，步数为 $2$。贡献 $2(r_i-i-1)$。
      5. 因此 $g_i = g_x + 2R +x - r_i - 2i - 2-c - [r_{r_i}<x \text{ 且 } r_{r_i}\notin c]$。
    3. 考虑如何求出 $x$ 和 $c$。
      1. 它们都和先跳到一个 $k$ 再跳到 $r_k$ 有关，我们不妨定义一个 $l_j$ 表示，最小的 $r_k=j$ 的 $k$。
      2. 那么 $x=\max\limits_{l_j<i} j 或 r_{r_i}$，$c=r_i < j < x 且 l_j<i$ 的数量。
      3. $l_i$ 和 $r_i$ 是可以预处理出来的。
      4. 正序扫描 $i$，维护标记集合 $s$，记 $x$ 为其中的最大值或 $r_{r_i}$，$c$ 为其中 $j>r_i$ 的部分，$flag$ 表示 $r_{r_i}$ 是不是被 $c$ 标记过，这个可以用值域树状数组做。
      5. 结束之后给 $l_j=i$ 的 $j$ 加入标记集合。
      6. 这样统计出 $x$ 和 $c$ 的数组，再倒序做 dp 即可。

图论专题

CF1076D Edge Deletion

题意

$n$ 点 $m$ 条边的联通无向带权图，记 $d_i$ 表示 $1$ 到 $i$ 的最短路径。现在只能留下最多 $k$ 条边，要使得 $d$ 变化的尽可能少，输出留下的边的条数和编号。

$n,m,k \le 3\times 10^5$

正确思路

先把不必要的东西剔除。建出一棵最短路树，显然只有 $(n-1)$ 条边是有用的，在里面每删一条边，至少使得一个点的最短路非法。
现在要在里面保留 $x$ 条边，每条边对应一个点，dfs 搜一遍，贪心选前 $x$ 条就好了。
本题不含 $0$ 边权，因此当某个点出队时，其至根的路径上的点都被松弛完毕了。直接加入这条边即可，不需要显性建树。

AT_abc243_e Edge Deletion

题意

$n$ 点 $m$ 条边的连通无向图，删除最多的边，使得全源最短路不变。

正确思考

这题让我们想起 Jzzhu and Cities，同样也是删除最多的边。于是我们仿照那题思路，考虑删除一条边能不能删。
1. 如果 $w > dis_{u,v}$，那么这是一条废边，必须删。
2. 如果 $w=dis_{u,v}$，考虑有没有代替路径，如果有两条及以上的路径，也一定删除 $w$。
  1. 删除 $w$ 不会使最短路变大，考虑反证法。
  2. 如果变大了，当且仅当另一条最短路径中的一条边被删除了。可我们的删除条件是，有代替路径再删除，如果被删除了，证明一定有代替路径，因此最短路根本没有变大。$w$ 可以删。
3. 这样操作完之后，剩下的边但凡再删一条，都没有代替路径了（有代替路径的都被删掉了），因此就是最优的。
甚至结论都和那题一样啊，只不过那题是单源最短路计数，这题是多源的。

无向图的最小环问题

题意

给你一个 $n$ 点 $m$ 边的带权无向图，找到一个至少 $3$ 个点的简单环，使得环边权和最小。输出这个边权。

$n \le 100$，$m \le 5\times 10^3$

正确思考

令每个环在被它编号最大的那个点统计。记这个点为 $k$。
枚举 $i$，$j$，它们与 $k$ 相邻，则构成一个 $i \rightarrow k \rightarrow j \rightarrow \dots\rightarrow i$ 的环。环长：$dis_{i,j}+w_{i,k}+w_{k,j}$。
回忆 Floyd $dis$ 定义，$dis_{i,j}$ 只会使用 $< k$ 的中转点，且 $i$，$j$ 本身小于 $k$（枚举决定的）。
因此不重不漏地考虑了每个环。

Chokudai’s Demand（★5）

题意

$n$ 个点的完全图，两点之间的边权是 $G_{i,j}$，如果 $G_{i,j}=-1$，则它实际上是 $x$。

定义“好对”为：可以从 $i$ 出发，花费不超过 $P$ 到达 $j$，其中 $i<j$。

好对的数量恰好为 $k$。问有多少个正整数 $x$ 可以满足。

$n \le 40$

思考

首先把 $-1$ 当作无限大，然后先把那些必然成立的点对去掉。剔除无用元素。
$x$ 越大，满足条件的点对越少。考虑二分 $x$。
还真可以。时间复杂度 $O(\log V \times n^3)$。

函数调用

题意

给你一个长度为 $n$ 的序列 $a$ 和 $m$ 个函数，每个函数是以下 $3$ 种类型之一：

$p$ 点 $+ x$
全局乘 $x$
调用 $c$ 个其他函数

然后依次处理 $q$ 次调用，问调用后的 $a$ 的取值。

$n,m,q \le 10^5$，$\sum c \le 10^6$

思考

类型 $3$ 函数可以拆成多个全局乘，多个单点加。发现主要的瓶颈就在这个操作可能很多。
事情变得复杂起来了，我们尝试简化问题：
1. 如果没有全局乘操作，可以怎么样弄呢？
  1. 这样就没有顺序关系了，我们记录一下每个函数每调用了几次，当作点权。
  2. 然后在建出来的函数调用图上，按 topo 序将点权传递下去，类似前缀和。
  3. 之后处理没有出度的节点即可。时间复杂度 $O(m+\sum c+q)$。
2. 如果没有单点加操作呢？
  1. 同样地没有顺序依赖，同样地记录。
所以现在的问题就是，加法和乘法之间存在顺序问题。现在的方向有 $3$ 种。
1. 将加法变成乘法：不行。
2. 将乘法变成加法：不行。
3. 将乘法和加法统一成某个神秘运算：想不到。
只能靠部分分的提示了。如果形状是一棵树怎么处理？
1. 加法是调用次数 $+1$。
2. 乘法的话，相当于将全局的调用次数乘以 $x$（需要将初始值视作 $n$ 次单点加）。
3. 感觉假的没边了。。。

正确思路

最后的 $a_i$ 一定形如：$xa_i+y$ 这种形式，我们要做的就是去维护这个参数。
先考虑乘法参数怎么维护。
1. 类型 $2$：乘 $x$
2. 类型 $3$：乘内部函数的乘积
3. 为了方便，我们把每个函数的乘法参数记为 $mul_u$
再考虑加法参数怎么维护。
1. 我们尝试去维护每个加法操作的调用次数。
2. 从后往前扫，维护一个倒序乘积 $suf$。
3. 类型 $1$ 和 $3$ ：$cnt_u \leftarrow cnt_u + suf$。
4. 然后考虑怎么维护类型 $3$ 内部的调用次数：先传递根的，然后也是同样地后缀乘积，用 topo 序更新这个参数即可。
最后先把乘法参数乘上去，再依次处理加法参数。

一些思考

维护加乘操作的题目，多去想 $ax+b$ 这个结构。这题的结构体现在函数带来的变换上。

9.29

VP CF 1124 Div.2

C

题意

给你一个长度为 $n$ 的数组和 $k$，每次操作可以删除正数第 $k$ 或倒数第 $k$ 项，删除之后得到价值，最大化价值。

$n \le 10^5$

赛时思路

首先只能操作 $n-k+1$ 次。
模拟这个过程，倒着数的那个指针一定是不断向右滑动的。
正难则反，相当于要保留 $k-1$ 个数，这些保留的数有什么限制吗？
1. 首先在中间的数肯定都会被删掉。
2. 能保留下来的数，只能是前 $k-1$ 和后 $k-1$ 个中的 $k-1$ 个。
3. 等等，删掉中间的数之后，不论删哪里，都会令两个指针移动。
4. 这个时候直接做双指针就好了。
总结一下，删完中间的 $[k,n-k+1]$ 个数之后，在前 $k-1$ 和后 $k-1$ 个数里双指针，再删 $\min(n,2k-2)-k+1$ 个。
用时 $35$ 分钟，要讨论清楚有点烦人。

D

题意

给你一个长度为 $n$ 的数组，$a_i < 16$。每次操作可以令相邻两个数同时异或 $3,6,9,12,15$ 其中之一。

不限操作次数，要使尽可能多的数字能被 $3$ 整除。

然后 $q$ 个询问，每次询问会改一个 $a_i$，改完之后最多有多少个数字被 $3$ 整除。

$n,q \le 2\times 10^5$

赛时思路

研究操作的性质
1. 首先一个数最多异或一次相同的数，所以可以用 $2^5$ 表达一个数的状态。
2. 虽然题目说只能选相邻两个，但事实上我可以选任意两个同时异或。
3. 通过打表我们发现，这些数的组合只能异或出 $0, 3, 5, 6, 9, 10, 12, 15$ 这几种值。显然每个数只会与其中之一进行异或。
4. 再次通过打表发现，只有 $5, 10$ 可以变成 $3$ 的倍数（剔除原来就是 $3$ 的倍数的数）。
5. 能使 $5$ 和 $10$ 成立的数：$3, 5, 6, 9, 10, 12$
$5$ 和 $10$ 可以两两相消，最终只会剩下一个孤立的 $5$ 或 $10$。
除非序列里其他数都是 $15$，否则一定可以让这个孤立的 $5$ 也变成 $3$ 的倍数。
所以统计一下序列里 $5$，$10$，$15$ 和非法的数的数量就好了。
等等，就算全是 $15$ 也可以通过异或 $3$ 得到 $3$ 的倍数。所以不管怎样都可以得到 $3$ 的倍数。
只需要统计非法的就好了。
用时 $53$ 分钟。

9.30

VP CF 1123 Div.2

D

题意

给你一个长度为 $n$ 的排列 $a$，可以交换 $a_i$ 和 $a_{i+2}$，问能不能让它变成一个单峰序列。

$n \le 2\times 10^5$

赛时思路

把序列看成是奇偶两条链，链内部可以任意调换顺序。
1. 同一条链内如果出现相邻的值，例如 $23$，则它们一定处于不同侧。
先来确定好确定的位置，最大值一定处于峰。
1. 如果最大值和次大值处于同一条链则无解。
2. 次大值一定在最大值左边 / 右边一格。
钦定峰，考虑贪心选左右两端：
1. 上升段：选的数越小越好
2. 下降段：选的数越大越好
3. 这个贪心好像是对的？我们试图使用调整法证明：
  1. 当前处于上升段，当前剩余点中第一个比上一项大的点是 $p$，当前点取 $q$，假设 $q>p$，则交换 $p$，$q$ 必然不劣：
  2. 若 $p$，$q$ 同属上升段：不存在这种情况。
  3. 若 $p$ 处于下降段：可以通过不断翻转路径的形式调整，确实是不劣的。
  4. 下降段的论证是对称的（应该）。
直接按照贪心策略写就好了，不用钦定最大值，如果遇到了 $n$，就调整至下降段。用两个 set 维护奇偶集合。
用时 $44$ 分钟。

E

题意

定义一个 $01$ 串的代价为：每次可以将一段连续的 $0$ 或 $1$ 翻转，令串变成全 $0$ 或全 $1$ 的最小操作次数。

定义一个 $01$ 串的价值为，其所有子串的代价之和。

$q$ 次修改，每次翻转点，求修改后的价值。

$n,q \le 2\times 10^5$

赛时思路

先来看这个代价怎么求：将 $01$ 串缩点，取白点黑点的 $\min$ 就好了。
再来看价值怎么求：
1. 钦定左端点，记当前处于 $i$ 点，则贡献：$\sum len_i\times(len_{i+2k-1}+len_{i+2k})\times k$。把 $len_i$ 提出来，后面那项分奇偶用一个变量做后缀和就可以实现 $O(n)$ 计算。但对本题好像没什么作用。
2. 把贡献拆到每一个点上，每一个点 $i$ 贡献：$\sum len_k\times len_i \times \frac{\lvert k-i+1\rvert}{2}$。同样把 $len_i$ 提出来，后面那项同样分奇偶用四个变量维护可以实现 $O(n)$ 计算。
来讨论修改的情况：
1. 修改后不改变块数
  1. 相当于一个块长度 $+1$，另一个 $-1$。
  2. 对同奇偶的块没影响，主要是对不同奇偶的块的影响。
  3. 继续讨论感觉会相当复杂，打住。
是否存在一个给定 $len$ 序列快速计算价值的方法？并不存在吧。

订正

因为题目是单点修改，我们从连续段的角度来考虑的话不是很合适，所以我们应该从点的角度考虑。
考虑代价怎么求：
1. 本质是求区间连续段数量 $/ 2$ 下取整。
2. 区间连续段数量是一个经典问题：
  1. 定义 $c_i \gets a_i \ne a_{i-1}$
  2. 定义 $s_i \gets s_{i-1}+c_i$
  3. 则 $[l,r]$ 区间的连续段数量即：$s_r-s_l+1$。因为自身包含一段。
考虑价值怎么求：
1. 钦定右端点，枚举左端点，$val = \sum\limits_{r=1}^n \sum \limits_{l=1}^{r-1} \lfloor \frac{s_r-s_l+1}{2} \rfloor$。
2. 我们现在想让取值符号去掉，$\lfloor \frac{s_r-s_l+1}{2} \rfloor = \frac{s_r-s_l+(s_r-s_l)\bmod 2}{2}$。这是一个很好用的技巧。
3. 然后提出来：$val=\frac{1}{2} (\sum\limits_{l<r} s_r-s_l+\sum\limits_{l<r} (s_r-s_l) \bmod 2)$
  1. 前面的部分，可以把贡献拆到单点上，每一个 $c_i$ 贡献 $(i-1)(n-i+1)$。
  2. 后面的部分，等价于 $a_{l+1} \ne a_r$，也就是求满足 $l<r \and a_l \ne a_r$ 的有序对个数。因为这是 $01$ 串，所以就是 $cnt_0 \times cnt_1$。
所以维护 $01$ 个数，每个 $c_i$ 的贡献就好了。

图论专题

最大半连通子图

定义半连通图为：图上任意两点，都存在 $u \to v \or v \to u$。

半联通子图定义为图 $G$ 的导出子图是半连通的。问半连通子图中，顶点数最多的图有多少个顶点，以及数量。

$n \le 10^5$，$m \le 10^6$

正确思考

首先导出子图只与 $n$ 有关，暴力的做法是枚举所有 $n$ 的排列，时间复杂度 $O(n^2n!)$。
先来考虑第一问，如何求出最大的半连通子图呢？
1. 注意到选了一个点之后，它所处的强连通分量也一定被选上。因此我们将原图缩点。
2. 缩点之后发现问题就变成了找 DAG 最长链以及最长链计数。

矿场搭建

最少选几个点，使得删掉原图中任意一个点之后，每个连通块都还至少包含一个点。

以及在最少的前提下，有多少种选择方案。

$n \le 1000$，$m\le 500$

正确思考

删点问题天然导向割点，删除非割点显然无用，删除割点才可能使连通块发生变化。
删除割点导致的连通块变化，又会导向块割树，于是我们就在块割树上考虑。
1. 定义叶块为：度为 $1$ 的节点，因为割点度至少为 $2$，所以叶块一定是 dcc。
2. 考虑删除叶块唯一连着的那个割点，则 dcc 与外部不连通，因此它的内部一定要选一个非割点。
3. 非叶块的 dcc，无论如何，都可以通过另一个割点走到另一个 dcc 里，所以不需要设点。
每个叶块需要设点，方案数就是叶块大小 $-1$ 的 prod。特判没有叶块的情况，此时要选两个点。

10.1

图论专题

loidc，跑起来

$n$ 点 $m$ 边无向连通图，图中不存在三角形。初始两人分别处于 $a$，$b$ 点，两人可以不动，或走到相邻点。

在均采取最优策略的情况下，$b$ 能不能一定抓到 $a$，输出最少轮数。

$n \le 3000$，$m \le 1.5\times10^4$

正确思考

如果 $a$，$b$ 同处一个环里，则 $b$ 一定抓不到 $a$。
因此 $a$ 的策略就是尽快走到一个环上面。
所以我们考虑如何找环上的点。处于 edcc 里的点一定处于环上，处于环上的点也一定处于 edcc 里。所以我们找到所有 edcc 就好了。这等价于在 dfs 生成树里找 scc。
只要 $a$ 比 $b$ 能更快的到底一个环上点，那么逃脱成功。
否则就要在 $d_1 < d_2$ 的情况下找 $d_2$ 尽可能大的点。

一些思考

edcc 或 vdcc 上的点都处于环上，且环上的点都处于 edcc 或 vdcc 上。区别是，edcc $= 1$ 的点不是环，vdcc $\le 2$ 的点不是环。

满汉全席

$n$ 个点，每个点有 $01$ 两种状态。$m$ 个约束，每条约束规定两个点的状态，要求满足至少其一。

问能否满足所有约束？

思考

至少满足其一，意味着：只要不满足其一，就必须满足其二。
于是我们把这种关系打包，于是这种关系是单向而不是双向的，于是我们连单向边（如果是双向等价关系就可以用种类并查集）。
如果相同点不同状态处于同一个 SCC 中就不行。

Coprime Solitaire

$n$ 个卡牌，每个卡牌有正反两面，分别有数子 $a$，$b$。

是否存在一种摆放方案，使得朝上的数字两两互质。

$n\le 3\times 10^4$，$a,b \le 2\times 10^6$

正确思考

这是一个典型的 “选我则不选它”，可以用 $2$-SAT 解决（两面状态想 $2$-SAT）。
具体地，把每个点拆成四份，分别表示选 $a$，不选 $a$，选 $b$，不选 $b$，这里也有 “选我就要选它” 的约束。
1. 选 $a$ 与不选 $b$ 连边；选 $b$ 与不选 $a$ 连边；
2. 然后枚举另一个数，如果不互质就连边。这样时间复杂度是 $O(n^2)$ 的，瓶颈在于建图。
考虑将数按照质因子分类，每一类里只能选一个。于是前后缀优化建图。
1. 具体地，$pre_i$ 表示前 $i$ 个节点的不选，$suf_i$ 表示后 $i$ 个节点的不选，维护很简单。
2. 对于 $i$，要和 $pre_{i-1}$ 和 $suf_{i+1}$ 连边。
然后 SCC 判合法性就好了。时间复杂度 $O(n \log n)$。

10.2

图论专题

Triangle

给你一个 $n$ 点无向图，给出邻接矩阵，求其中三元环的个数。

$n \le 3000$

思考

钦定其中两个点。找到共同 $1$ 的个数。
直接 bitset，然后答案除以 $6$。时间复杂度 $O(\frac{n^3}{w})$。
bitset 本质是把一串二进制拆成多个大整数，然后做位运算，所以时间复杂度可以除以位数。可以当作一个可以快速做位运算的 bool 数组。

无向图三元环计数

$n \le 10^5$，$m \le 2 \times 10^5$

思考

首先暴力的做法是，枚举每个点 $u$ 的儿子 $v_1$，再枚举 $v_1$ 的儿子 $v_2$，再枚举 $u$ 的儿子中，存不存在 $v_2$ 儿子（用一个标记数组判断）。时间复杂度是 $O(\sum\limits_u \sum\limits_{v \in u} d_v)$。
发现时间复杂度与度数有关，想到大点小点分治。重复统计导致冗余，于是我们想要钦定代表元。
将 $deg$ 小的点连向 $deg$ 大的点，这样每个点的 $deg$ 就在 $\sqrt{m}$ 以内，并且每个环只会被它 $deg$ 最小的那个点统计。
时间复杂度 $O(m \sqrt{m})$。

Colorful Graph（★6）

给你一个 $n$ 点 $m$ 边无向图，$q$ 个操作。

每次操作给定 $u$ 和颜色 $c$，先输出 $u$ 的颜色，再将 $u$ 以及它的邻居染成 $c$。

初始都是颜色 $1$。$n, q, m \le 2 \times 10^5$。

正确思考

暴力做显然不行，会有很多无用行为。
查询点 $u$ 时再找它的相邻点？和暴力一样啦。
这里存在两个方向的思考，但是都因为度数很大所以不行。
图上涉及度数的问题，通常考虑分类讨论，大点小点分治（度数小于 $B$ 的是小点）。
对于度数大的点，我们不去遍历它所有的邻居，让它的邻居来遍历它。
对于度数小的点，我们通过遍历它的所有邻居，来确定取值。
每个点都只需要更新它们的大点邻居，最坏 $O(2m / B)$。
小点查询时最坏 $O(B)$。
总共时间复杂度 $O(q (B + 2m / B))$，对这个求导，显然当 $B = \sqrt{m}$ 时是极值。

补题

前缀进位

前缀进位 - 题目详情 - 深圳实验中学 OJ

给你一个长度为 $n$ 的序列 $a$，至多 $k$ 次操作机会，每次操作可以令 $a$ 的一个前缀集体 $+ 1$。

问 $a_1 \mathbin{&} a_2 \mathbin{&} \dots \mathbin{&} a_n$ 的最大值。

$n \le 10^6$，$k, a_i \le 2^{60}$

正确思考

位运算的题目，从高到低贪心答案。
1. 我们把操作次数形式化，设在 $i$ 点加了 $b_i$ 次。这个形式化的技巧很重要，把你的决策/操作用符号表达出来。
2. 则有性质：$k \ge b_1 \ge b_2 \ge \cdots \ge b_n \ge 0$。
3. $b$ 显然越大越好。
4. 于是我们的问题就转化为：构造一个最大的 $b$，使其满足：
  1. $b_i \le last$
  2. $(a_i + b_i) \mathbin{&} ans = ans$
  3. 上一个式子等价于 $a_i + b_i = ans + y$。理解这一步动机的关键是要理解约束。一定要包含 $ans$ 里面的位，并且此时已经包含了 $ans$，所以把 $ans$ 抽出来就很自然了。
  4. 为了使 $b$ 最大，我们要最大化 $y$。考察 $y$ 的约束：
    1. $y \le a_i + last - ans$。
    2. $(ans + y) \mathbin{&} ans = ans$。
5. 考虑从高到低构造 $y$，记 $x=a_i + last - ans$。
  1. 考察 $y$ 与 $ans$，$x$ 的二进制约束：
    1. $y$ 只能取 $ans$ 为 $0$ 的位数，令 $ms$ 为 $ans$ 取反后的数，则 $y$ 只能取 $ms$ 为 $1$ 的位数。
    2. $y$ 要比 $x$ 小，做一个类似数位 dp 的过程。
  2. 贪心地考虑
    1. $x$ 最高位 $1$ 之前的数只能取 $0$。
    2. $x$ 为 $1$ 且 $ms$ 为 $1$，则一定取。
    3. 第一个 $x$ 为 $1$，$ms$ 为 $0$ 之后，剩下的就没有 $x$ 约束了，也就是把 $ms$ 取满。
    4. 总结一下，找到第一个 $x$ 为 $1$，$ms$ 为 $0$ 的位置，记为 $p$。
      1. $p = \log_2{(x\ &\ ans)}$
      2. 记 $mask = (1 \ll p) - 1$：0000111111
      3. 无 $x$ 约束：取 $ms \mathbin{&} mask$
      4. 有 $x$ 约束：取 $x \mathbin{&} ms \mathbin{&} mask$
    5. 所以 $y = (ms \mathbin{&} mask) \mathbin{|} (x \mathbin{&} ms \mathbin{&} \sim mask)$
    6. 得到 $y$ 之后，$b_i = ans + y - a_i$，检查一下是不是小于上一项就好了。
时间复杂度 $O(n \log V)$。

10.3

补题

白格连通

白格连通 - 题目详情 - 深圳实验中学 OJ

给你一个 $3\times n$ 的 01 网格，每一列必须填一个 1，且相邻两列的 1 不能在同一行。问所有方案中，最大的由 0 组成的连通块的大小的期望。

$n \le 500$。

思考

虽然问的是期望，但本质计数题，因为总方案数是 $3\times2^{n-1}$。（即第一列随便放，后面的要根据前面的选另外两个）。所以问题就变成了统计所有连通块大小的总合。
计数题要拆贡献，这题应该只能拆成：最大连通块 $=x$ 的数的个数。
这种网格图连通块，是可以用 dp 来维护的。于是我们考虑 dp。这个 dp 成立的关键在于，任何时刻，一个可扩展连通块大小为 k，另一个可扩展连通块大小至多为 1。
1. 定义 $f[j][k][0/1]$ 表示，前 i 列，第 i 列的 1 放在中间 / 两边，最大连通块为 j，最右侧可扩展的连通块大小为 k 的数量。
2. 用 $f[j][k][0]$ 刷表：
  1. $g[\max(k+2,j)][k+2][1]+=f[j][k][0]$ 和大小为 k 的连通块连接
  2. $g[\max(j,3)][3][1]+=f[j][k][0]$ 和大小为 1 的连通块连接
3. 用 $f[j][k][1]$ 刷表：
  1. $g[\max(k+2,j)][k+2][1]+=f[j][k][1]$
  2. $g[\max(k+1,j)][k+1][0]+=f[j][k][1]$
统计答案就是：$\sum (f[j][k][0/1]\times j)$。

一些思考

这种维护 连通性 的状压 dp，有个专门的名字叫做插头 DP。

一维很小，一维很大的题要考虑这个。核心思想是只维护已处理和未处理分界的信息。

鸽。

路径片段计数

路径片段计数 - 题目详情 - 深圳实验中学 OJ

给你一个 n 点树和一个 [1,n] 排列。统计有多少个排列上的区间 [l,r] 满足：

树上 [l,r] 形成的导出子图是一条路径。

$n \le 2\times 10^5$

思考

显然我们需要钦定区间端点，用一些方法维护左端点的信息。这种模式在计数问题里非常常见。
于是我们钦定区间右端点，考虑维护左端信息：
1. 点的度数约束：
  1. 由于是一条路径，所以 $d_u\le2$。
  2. 显然点越多，度数越多，所以这个具有单调性，可以双指针。
  3. 具体地，右端点右移时，记录超标点数量。然后左指针做删除，直到超标点为 0。
2. 连通性约束：
  1. 只能有一个连通块。
  2. 树的导出子图一定是树。有关树的连通性，要去考虑点数和边数的关系。树上连通块数量 = n - m。
  3. 显然只有当 $m=n-1$ 时才是一条路径。
  4. 因此我们用线段树维护 [j,r] 的 $n-m$，n 通过区间加维护，m 在加边的同时区间加即可。
  5. 注意到 $n-m$ 的最小值就是 1，否则的话必然存在环或重边。因此维护区间最小值及其数量即可。（注意维护区间 = x 的数量，还需要支持区间加的话是不可 n log n 的）。
时间复杂度 $O(n \log n)$。

树林的回声

T826263 树林的回声 - 洛谷

n 个节点的树，节点有一个小写字母作为点权。

对每个 $u\in[1,n]$ 统计，有多少个字符串 s，可以由至少两条从 v 出发向下的路径得到，v 需要不同。

$n \le 2\times 10^5$。

思考

首先考虑单独的 u 怎么求。
1. 给每个儿子建一棵 trie，然后合并 trie 得出 u 的 trie。
2. 考察合并的过程。
  1. 合并当前 trie 和子 trie 时，如果子 trie 和当前 trie 都存在一个相同的节点，则说明至少有两条路径可以得到相同的结果。
  2. 当时这样会重复计数，因为当前 trie 里的那个节点的贡献可能已经被算过了。所以我们用一个标记数组标记。
3. 子树信息，无修改，考虑 dsu on tree。每次 u 继承重儿子的 trie，将小的合进来。
4. trie 合并的时间复杂度是 $O(Vn)$，每一棵子树合并后大小都会翻倍，子树大小最大 $O(n)$，所以总时间复杂度 $O(Vn \log n)$。

后记

感觉对 trie 的掌握还是不够，有些云里雾里的。

10.4

DP 专题

子序列

P1410 子序列 - 洛谷

给定一个长度为 $N$（$N$ 为偶数）的序列，问能否将其划分为两个长度为 $N / 2$ 的严格递增子序列。

$n\le 2000$

思考

每个元素需要恰好属于一个子序列。
第几个元素是阶段，长度需要作为状态，末尾元素需要用于转移。因为最后一个元素一定属于一条链，所以我们定义状态 $f[i][j]$ 表示前 i 项，末尾是 $a_i$ 的那个序列长度为 j，则另一个序列长度为 i-j，另一个序列以 $f[i][j]$ 作为结尾，要求取最小值。状态设计是一个不断尝试的过程。阶段首先设出来，再看状态需要什么，转移需要什么。
考虑转移：
1. $a_i$ 接在状态显性设出来的那条链里：$f[i][j]=f[i-1][j-1]$，条件是 $a[i]>a[i-1]$。
2. $a_i$ 接在没有显性设出来的那条链里：$f[i][j]=a[i-1]$，条件是 $a[i]>f[i-1][i-j]$。

后记

相似题目：CSP-S 2024] 染色 - 洛谷。

本质都是将序列染成红色和蓝色，所以我们沿用那题的 dp 思想，做一个可行性 dp。

令 $f[i][j]$ 表示前 i 项，强制 i 点为 换色点，并且和 i 点同颜色的有 j 个的可行性。

则有转移：$f[i][j]=f[k][k-j+1]$，要求 $a_i>a_{k-1}$ 且 $[k,i-1]$ 这一段严格递增。

暴力枚举 k 显然超时，考虑优化。注意到想要满足 [k,i-1] 这个约束，k 一定是递增的，所以用数据结构维护一下，可以做到 $O(n^2 \log n)$。

换色点 dp 的本质在于压缩连续相同段。

后后记

观点来自：dp 题方法总汇 - 洛谷保存站

上文提到的正解和换色点 dp，本质上可以归为类两种不同类型的 dp：

单步转移：每次只决策最小单元，在这题的例子里就是每次只决策一个元素，通常优先考虑这种。
断点转移：类似“跳跃”，每次决策一段，在这题的例子里就是决策一段，如果单步转移不行再想这种。

Miny

PA 2020] Miny - 洛谷

n 个炸弹，每个炸弹有位置 $a_i$ 和引爆半径 $r_i$，如果 i 爆炸了，i 半径覆盖范围内的炸弹都会爆炸。

现在手动引爆一些炸弹，问有多少种不同的爆炸集合。

$n\le 3\times 10^5$，$a_i,r_i \le 10^{18}$

思考

首先要把这个爆炸关系表达出来。如果 a 炸了会引爆 b，那么就令 $a \to b$。
把 SCC 缩点，现在的图变成了多个 DAG，每个 DAG 之间互相独立。
考虑如何计算单个 DAG 的贡献。
1. 如果选择一个点，从它出发能到达的所有点都会被消除。问最终留下的点有多少种方案。
2. 那就钦定引爆 i 点，看能造成多少种方案。好像不可做。
3. 考察 DAG 的性质：想要遍历 DAG 上的所有点，需要从所有度为 0 的点出发跑 dfs。这有什么性质吗？
上述转化其实是把问题转化为了：“数一个偏序集的反链数”，这个是多项式做不了的。

订正

我们的直觉失败了，转而使用机械化的流程做题。
推导等价条件，重新表述问题：
1. 等价条件：无。
2. 重新表述：统计爆炸集合的数量，等价于统计不爆炸集合的数量。
  1. 爆炸集合的性质是，不能再向外扩展，极大。
  2. 不爆炸集合的性质是，无法被扩展，极小。
思考过程，考虑暴力：
1. 过程就是，引爆一个炸弹，会导致一个区间的连环爆。
2. 暴力的做法，状压，钦定引爆的地方，然后统计最后的结果数量。
联想模型，尝试套用：
1. 计数题：钦定主体，组合数学；计数 DP
2. 考虑套用 DP 模型：
  1. $f_i$ 表示，前 i 个炸弹，i 强制引爆，能产生的不同方案数。
    1. 找到连锁反应的结尾 j，它是最后一个被引爆的，于是有转移：$f_i=\sum f[0,j-1]$。
    2. 然而这个转移是错误的，因为前面引爆的点可能会波及 i 后面的点，这个状态没有考虑到。
  2. 失败时候，尝试使用问题的不同表述。上文是在用 “爆炸” 表述，下面就尝试 “不爆” 表述。
  3. $f_i$ 表示，前 i 个炸弹，i 强制不爆，能产生的不同方案数。
    1. 找到上一个不爆的位置 j，则 $f_i = \sum f_j$。
    2. 现在的问题就是如何快速找到 j。有关 j 的约束是：[j+1,i-1] 强制爆，但是 i，j 不爆。
    3. 定义 $l_i,r_i$ 分别表示 i 点能影响到的最左和最右区间，则：
      1. $j < \min l[j+1,i-1]$。这个是查询范围约束，非法之后还可能合法。
      2. $i > \max r[j+1,i-1]$。这个是生命周期约束，非法之后不可能合法。
    4. 这两个玩意儿具有单调性，都在不断变大。
      1. 第二个查询范围约束，只需要找到第一个大于等于 i 的 r ，从它开始的 j 都满足条件。所以预处理左边第一个大于我的数就是查询范围。
      2. 第一个生命周期约束，找到 i 右边第一个小于等于我的就好了，在那里打删除标记。
    5. 上权值树状数组。

释放囚犯

P1622 释放囚犯 - 洛谷

n 个牢房，要释放 m 个人。每次释放的代价是所处连通块大小 -1。问全部释放完的最小代价。

$n \le 1000$，$m\le100$

思考

无论做什么题目，第一步都是把它当作无算法题或贪心题去挖掘性质，然后再换角度套算法。
这题直接上 dp 能不能做呢？反正我是想不出来的。
于是我们就去挖掘一些性质：
1. 感觉有点像货舱选址？每次都选中位数好像就是最优的。并非吧。

订正

关键在于观察出操作的影响：每次选了一个人之后，会将整个区间断成两半，两半互相独立。
这就是 区间 dp 的结构：一个关键点+两边独立区间。
所以我们考虑区间 dp。
1. $f[i][j]$ 表示，将编号 $[i,j]$ 的人全部释放，保留的最少代价。
2. 有转移：$f[i][j]=\min f[i][k-1]+f[k+1][j]+a[j+1]-a[i-1]-2$.
答案就是 $f[1][m]$，时间复杂度 $O(m^3)$。

后记

区间 DP 的结构和笛卡尔树的结构很类似，不过笛卡尔树的关键点是最值。结构的相似性也是笛卡尔树优化区间 DP 的基础。