专栏文章

浅谈 OI 中的一些对偶类问题

ss4CRIF1CbUbbL3AtIAly
算法·理论参与者 26已保存评论 25

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
25 条
当前快照
1 份
快照标识符
@mk9zddlv
此快照首次捕获于
2026/01/12 01:01
上个月
此快照最后确认于
2026/02/19 01:18
11 小时前
查看原文

引言

OI 中经常有各种各样的复杂问题出现，而解决问题的手段也种类繁多。其中经常会出现这样一类做法：
“对于 xxx 问题，虽然原问题不好做，但是我们可以通过 xxx 将其转化为 xxxx，从而获得优化的空间。”
虽然对于这些问题，应该总是存在与这种做法本质相同的强行解决原问题的做法，但通常都比较阴间，这就导致等效的问题转化是一个很关键的技能。本文将列举一些常见的等效转化，或者更直白的说，一些对偶的问题，以及在他们之间转化的应用。

正文

那么首先我们需要知道一些常见的对偶问题。
如果你阅读过 OI-Wiki 中线性规划对偶的页面，你会读到这样一句话：
最大流、最小割、最小费用流、最短路、差分约束、二分图最大（权）匹配和最小点覆盖 等问题，都可以转化为线性规划问题求解。而且，最大流与最小割、最短路与差分约束、二分图最大匹配和最小点覆盖，两两互为对偶问题。
结合一些常识，我们可以想到下列对偶问题：
  1. 最大流与最小割；
  2. 最短路与差分约束；
  3. 二分图的最大匹配与最小点覆盖；
  4. 线性规划问题的对偶；
  5. 偏序集上的最小链覆盖与最长反链（Dilworth 定理）；
  6. 一般图中的最小点覆盖与最大独立集（互补）；
  7. 矩阵的转置原理（？）
其中，最后几个可能与严格意义上的“对偶”并不相符，但是这些确实是一些具有强相关性的问题，所以它们之间的关联确实值得我们思考。下面将会依次对这些对偶问题进行简单的介绍并给出一些例题。

最大流与最小割

首先有一个众所周知的 最大流最小割定理，它告诉我们任意一个有源汇网络图中的最大流都与最小割在数值上相等。实际上，我们也可以用线性规划的对偶来说明这一点。
而对于大部分图论问题，最大流与最小割在图上的表现形式区别较大，因此这个转化会让我们在一些题目的思考上方便很多。

例题 1. P9545 [湖北省选模拟 2023] 环山危路 / road

给定一张 nn 个点的竞赛图，容量均为 11。mm 次查询，每次给定若干源点和一个汇点，你需要求出此时整个图的最大流。
题解
一个最大流直接摆在脸上了，而且看起来就不好直接做，于是考虑转最小割。
假设最终与起点连通的集合为 SS，与终点连通的集合为 TT，那么我们需要最小化的就是 f(S,T)=∑u∈S∑v∈Teu,vf(S,T)=\sum_{u\in S}\sum_{v\in T}e_{u,v}，这里 eu,ve_{u,v} 表示它们之间的边的朝向是否为 u→vu\to v。
尝试找一些性质。首先不难发现 f(S,T)+f(T,S)=∣S∣×∣T∣f(S,T)+f(T,S)=|S|\times |T|。接着考虑 f(S,T)−f(T,S)f(S,T)-f(T,S)，拆到每一条边上，s→ts\to t 对答案的贡献是 11，t→st\to s 对答案的贡献是 −1-1，不难想到把答案写成 ∑u∈Soutu−inu\sum_{u\in S}out_u-in_u。所以我们如果确定了 SS，那么可以快速得出 f(S,T)=∣S∣(n−∣S∣)+∑u∈Soutu−inu2f(S,T)=\frac{|S|(n-|S|)+\sum_{u\in S} out_u-in_u}2。
现在我们需要最小化这个，于是枚举 ∣S∣|S| 的取值，那么这样我们一定会选择给定的点以及剩下的点中 outu−inuout_u-in_u 最小的那些，排序之后贪心即可。
总复杂度 O(nm)O(nm)。

例题 2. QOJ15449 Finances

有一张无源汇的无向连通网络图，且每个点有初始的流量 aia_i（可正可负），保证 ∑ai=0\sum a_i=0，记 A=∑ai[ai>0]A=\sum a_i[a_i>0]，那么每条边的容量 cic_i 都满足 ci≥⌈A2⌉c_i\ge\lceil\frac A2\rceil。你需要判断这张图能不能流量平衡。
题解
首先加一个源点和汇点，源点连向所有 ai>0a_i>0 的点且容量为 aia_i，ai<0a_i<0 的点连向汇点且容量为 −ai-a_i。这样的话满流就说明合法。显然满流就是最大流 =A=A。
这个问题的限制条件十分奇怪，它想说明只要有两条边就可以达到 AA，可是这用最大流的理解来看比较怪异。因此考虑转为最小割。
因为两条图边的边权和就已经 >A>A 了，而我们知道最小割不会超过 AA，所以我们只需要考虑割了一条图边的情况。
如果我们希望割的这条图边能对点之间的连通性产生影响，那么这条边肯定要是一个割边（否则删除这条边之后能够到达 TT 的点集没有变化）。于是我们只需要对每条割边检查如果删去它那么图的两侧能否自己满流。
而把这个问题再映射回原问题，我们只需要对每条割边判断其两侧必须要传输的流量（即 ∑ai\sum a_i 的差）会不会超过这条边的容量即可。

例题 3. CF724E Goods transportation

给定一张 n+2n+2 个点（S,T,1∼nS,T,1\sim n）的网络图，所有连边包括 S→pii→siTS\xrightarrow{p_i}i\xrightarrow{s_i}T，以及对于所有 i<ji<j 有 i→cji\xrightarrow{c}j，求 S→TS\to T 的最大流。
题解
考虑转最小割，那么我们需要选出一个点集连接 SS，剩下的点连接 TT，并割掉第一个点集连向第二个点集的边。
假设最开始所有点都连接 TT，考虑每个点从连接 TT 变成连接 SS 时答案的变化量 w(i)w(i)。记 f(i)f(i) 表示比 ii 小的连接 SS 的点数，g(i)g(i) 表示比 ii 大的连接 TT 的点数，那么不难发现 w(i)=c⋅(g(i)−f(i))+si−piw(i)=c\cdot(g(i)-f(i))+s_i-p_i。
那么每次我们肯定是选择一个 ww 最小的 ii 然后处理其他点的 ww 的变化量即可。注意到当 ii 从连接 TT 变成连接 SS 时，比 ii 小的点的 gg 会减少 11，比 ii 大的点的 ff 会增加 11，因此其实所有点的 ww 整体减小了 cc。
所以我们只需要按照初始的 ww 排序，然后按顺序依次取走每一个并计算答案的变化量，记录过程中得到的答案的最小值即可。时间复杂度 O(nlog⁡n)O(n\log n)。

例题 4. AT_codefestival_2015_final_j N個のバケツ

nn 个人围成一个圈，第 ii 个人的力气为 aia_i。你需要选择一个序列 bb，使得 bi+b(i mod n)+12≤ai\frac{b_i+b_{(i\bmod n)+1}}2\le a_i，并最大化 ∑bi\sum b_i。qq 次操作，每次修改一个 aia_i 的值，你需要回答每次操作之后最大的 ∑bi\sum b_i。保证 nn 是偶数。
题解
先把式子改成 ai+ai−1≤2pia_i+a_{i-1}\le 2p_i。
发现还是没有什么好的入手办法，考虑网络流。因为图是偶环可以黑白染色，所以能够得到如下建图：
SS 连向所有黑点，所有白点连向 TT，容量为 pip_i。黑点向相邻白点连容量为 ∞\infty 的边。
转化为最小割，考虑组合意义。显然不能割环上的边，于是接下来我们称割掉一个点表示割掉这个点向 SS 或者向 TT 的连边。
不难发现相邻两个点中至少要割掉一个，否则会存在一条 S→TS\to T 的路径。于是没被割掉的点形成一个环上的独立集。那我们只需要求出这个环上的最大权独立集。
直接线段树维护，每个节点上记录 f0/1,0/1f_{0/1,0/1} 表示该线段树区间上两端点选/不选所对应的最大权值和。复杂度 O(n+qlog⁡n)O(n+q\log n)。

小结

在一些问题中，将最大流转化为最小割之后，有助于我们分析性质，从而化简问题 / 用数据结构优化。

最短路与差分约束

我们知道，任何一个普通的最短路问题都可以将其写成差分约束的形式：一条有向边 (u,v,w)(u,v,w) 对应式子 disv≤disu+wdis_v\le dis_u+w。而差分约束的问题本身也可以用最短路的形式求解，因此它们之间的关联是很大的。
不过 OI 中与差分约束相关的题目并不多，这里收集了一部分例题。

例题 1. CF241E Flights & P5590 赛车游戏

给定一张有向图，给每条边赋一个 1∼k1\sim k 的边权，使得 1→n1\to n 所有路径长度相同。两题中的 kk 分别为 22 和 99。
题解
其实 kk 具体是多少并不影响做法。
显然图中不能有环。于是现在我们可以认为每条在 1→n1\to n 路径上的边都必须扯紧，即 disv=disu+wdis_v=dis_u+w。
因为 1≤w≤k1\le w\le k，所以我们直接将其写成 disu+1≤disv≤disu+kdis_u+1\le dis_v\le dis_u+k，于是这就是一个差分约束的板子了。

例题 2. P14038 [PAIO 2025] Adventure Plan

给定一张 DAG，每条边有一个边权区间 [li,ri][l_i,r_i] 表示其边权需要在这个范围内。一张图是好的当且仅当存在一种给边确定边权的方式使得对于每个 ii，00 到 ii 的所有路径长度都相同。
qq 次加边操作，保证加完之后图还是 DAG，你需要依次判断加每条边之后图是否仍然是好的，如果是好的就加入这条边。所有边加完之后你需要给出构造方案。
题解
和前一题类似的，直接建立差分约束系统，每条边相当于 disu+li≤disv≤disu+ridis_u+l_i\le dis_v\le dis_u+r_i。
所以我们现在需要动态加边，并查询是否存在负环。用 Floyd 先跑出来任意两点距离，每次加入一条边的时候就暴力更新两点最短路，并检查是否出现 fu,u<0f_{u,u}<0，最后直接构造即可。
总复杂度 O(m+n3+qn2)O(m+n^3+qn^2)。

小结

除了差分约束本身可以根据最短路的形式求解以外，还可以主动将最短路的问题放宽为差分约束，以解决一些特殊的限制条件。

二分图的最大匹配与最小点覆盖

有的时候与后面的 最小点覆盖与最大独立集 配合使用，可以得到二分图上的最大独立集 =n−=n- 最大匹配。
因为在二分图上的最小点覆盖和最大独立集的应用并不多，因此这方面例题可能较少。

例题 1. CF1404E Bricks

给定一个 n×mn\times m 的黑白网格，用尽量少的 1×x1\times x 或 x×1x\times 1 的矩形恰好覆盖所有黑格。
题解
注意到我们可以把选矩形过程改为最开始每个格子各为一个矩形，每次删除两个矩形之间的某一条边来合并它们。这样最大化删除次数即可。
而我们发现对于每个格子，其左右的边不能和其上下的边同时删除，于是我们可以把问题转成一个二分图最大独立集问题，直接求出最大匹配即可。

小结

这种对应关系能够让我们较为方便的解决二分图上的最小点覆盖以及最大独立集的问题。

线性规划问题的对偶

有一些最优化题的直接贪心做法十分神秘，甚至难以理解其正确性。这个时候，我们可以考虑将其转化为线性规划，并解决对偶问题。

例题 1. P6631 [ZJOI2020] 序列

有一个序列 aa，可以进行若干次操作，每次可以选择一个区间并将区间里所有位置 / 所有奇数位置 / 所有偶数位置的值同时 −1-1。问让数组清零的最小操作次数。
题解
对于这一类“操作型”贪心题，我们可以对其得出一个较为通用的结论。
记所有的操作集合 S={s1,s2,…,sk}S=\{s_1,s_2,\dots,s_k\}，其中每一个 sis_i 都是一个下标集合表示一种操作。记 xix_i 表示 sis_i 这个操作的使用次数，那么我们的式子就是 ∀i,∑i∈sjxj=ai\forall i,\sum_{i\in s_j}x_j=a_i，最小化 ∑xi\sum x_i。
把 == 写成 ≤\le 和 ≥\ge，于是我们得到了最初的线性规划形式：
{xi≥0∀i,∑i∈sjxj≥ai∀i,∑i∈sj−xj≥−aimin⁡∑xi\begin{cases} x_i\ge 0\\ \forall i,\sum_{i\in s_j}x_j\ge a_i\\ \forall i,\sum_{i\in s_j}-x_j\ge -a_i\\ \end{cases}\\ \min \sum x_i
对偶之后 2n2n 个式子都会分别获得一个系数，记正的系数为 y1∼yny_1\sim y_n，负的系数为 z1∼znz_1\sim z_n（这里 zz 直接表示绝对值）。对偶得到的结果为：
{yi,zi≥0∀j,∑i∈sj(yi−zi)≤1max⁡∑ai(yi−zi)\begin{cases} y_i,z_i\ge 0\\ \forall j,\sum_{i\in s_j}(y_i-z_i)\le 1 \end{cases}\\ \max \sum a_i(y_i-z_i)
那我们直接记 wi=yi−ziw_i=y_i-z_i，相当于我们有一个序列 aa，我们需要求一个序列 ww 满足对于任意一种操作 ss 都有 ∑i∈swi≤1\sum_{i\in s}w_i\le 1，并最大化 ∑aiwi\sum a_iw_i。
回到本题，我们要找一个满足任意子段和以及子段里的奇数位置和以及偶数位置和都不超过 11 的系数序列 ww，最大化 ∑aiwi\sum a_iw_i。
不难猜到最优情况所有 ww 都是整数。因为限制相当于最大子段和以及只保留奇数位置和偶数位置对应的两个序列的最大子段和都不超过 11，所以联想到 DP 套 DP，直接记录当前考虑到的前缀以及三个序列此时的最大后缀和。
因为不会超过 11，而且最大后缀和总是会和 00 取 max⁡\max，因此每一维都只有 00 或 11。而转移的时候不难发现如果 wi<−1w_i<-1 总是能改成 wi=−1w_i=-1 而且仍然合法。因此直接 fi,x,y,zf_{i,x,y,z} 记录上面所说的东西，转移就也是 O(1)O(1) 的。总复杂度 O(n)O(n)。

例题 2. P8182 「EZEC-11」雪的魔法

有一个序列 aa，可以进行若干次操作，每次可以选择一个长度不超过 mm 的区间并将区间里所有值同时 −1-1。qq 组查询，每次给定 [l,r][l,r] 求将 al∼ara_l\sim a_r 清零的最小操作次数。
题解
继续应用上一题的结论。在本题中，限制就相应的为任意长度 ≤m\le m 的区间和都 ≤1\le 1。不难发现 wi<−1w_i<-1 仍然不优，因此总是有 wi∈{−1,0,1}w_i\in \{-1,0,1\}。于是我们的限制可以看作是任意两个距离不超过 mm 的 11 之间必须有一个 −1-1。
考虑钦定一些距离超过 mm 的位置，这会把序列切成若干区间。区间内部可以直接视作 m=nm=n 的情况，因为这个情况下答案不会更优，所以这么做不会影响正确性。而根据常识我们知道 m=nm=n 的答案为 a1+∑i>1max⁡(0,ai−ai−1)a_1+\sum_{i>1}\max(0,a_i-a_{i-1})（这里从原问题的角度更好理解）。
因为我们钦定的地方一定是恰好空开 mm 个，于是可以直接计算钦定第 i−m+1∼ii-m+1\sim i 全都选 00 对答案的影响：bi=ai−∑j=i−m+1imax⁡(0,aj−aj−1)b_i=a_i-\sum_{j=i-m+1}^i\max(0,a_j-a_{j-1})。
所以我们现在的问题相当于是每个点有权值 bib_i，可以选择一些点并获得其权值，但是选择的两个点距离至少为 mm，最大化总权值。容易写出一个 dp，转移大概是 fi=max⁡(fi−1,fi−m+bi)f_i=\max(f_{i-1},f_{i-m}+b_i)。
因为我们要在一个区间上做一遍这个 dp，这肯定是不好的，于是把 dp 改写成最长路的形式，这样我们需要在转移图上求出两点最长路。注意到每次连向 +1+1 和 +m+m 的图其实是可以画成一个最后一行会向第一行下一列的位置有额外连边的网格图，于是考虑网格图最长路的经典解决方法，每次选择较短边进行分治，复杂度 O((n+q)n)O((n+q)\sqrt n)。额外的连边只需要在第一次对行分治的时候加上就行。

例题 3. AT_wtf22_day1_d Welcome to Tokyo!

有 mm 个区间 [li,ri][l_i,r_i] 满足 1≤li≤ri≤n1\le l_i\le r_i\le n，对于每个 k=1∼nk=1\sim n 求出从 1∼n1\sim n 选出 kk 个数之后最多能有多少个区间包含至少一个选中的数。
题解
先写成线性规划形式。因为我们相当于要最大化 ∑min⁡(1,∑j=lirixj)\sum\min(1,\sum_{j=l_i}^{r_i}x_j)，但是这个式子是不好直接表示的，所以用一个 yiy_i 来单独表示这个东西的第 ii 项，这样把 min⁡\min 当做限制塞进线性规划。式子如下：
{yi≤1∀i,yi−∑j=lirixj≤0∑xi≤kmax⁡∑yi\begin{cases} y_i\le 1\\ \forall i,y_i-\sum_{j=l_i}^{r_i}x_j\le 0\\ \sum x_i\le k \end{cases}\\ \max \sum y_i
可以调整法证明总是存在最优解的 x,yx,y 都是整数。直接对偶，记三个式子系数分别为 pi,qi,Rp_i,q_i,R，那么对偶之后的结果为：
{∀i,R−∑lj≤i≤rjqj≥0pi+qi≥1min⁡∑pi+kR\begin{cases} \forall i,R-\sum_{l_j\le i\le r_j}q_j\ge 0\\ p_i+q_i\ge 1 \end{cases}\\ \min\sum p_i+kR
以 qiq_i 为主元，那么不难发现 R=max⁡i∑lj≤i≤rjqjR=\max_i \sum_{l_j\le i\le r_j}q_j，pi=1−qip_i=1-q_i，于是不妨猜测 pi,qip_i,q_i 都只会是 00 或 11。于是如果 qi=1q_i=1 表示选择该线段，那么 RR 就是覆盖次数最多的点。
因此考虑对于每个 RR 计算最多能选择的线段个数 f(R)f(R)，这样一个 kk 的答案就是 min⁡(kR+m−f(R))\min(kR+m-f(R))。注意到该问题可以写成一个费用流的形式，因此 −f-f 应该是下凸的，再加上 kRkR 之后不影响凸性，因此可以双指针扫描得到答案。
回到计算 ff 的问题上。考虑 fx−1→fxf_{x-1}\to f_x 的过程。首先 f0→f1f_0\to f_1 有一个经典贪心是从前往后每次选择 rr 最小的线段，而能够证明我们把这个贪心扩展到其他的 xx 的时候也是对的。
考虑用数据结构维护该贪心：每次选择右端点最小的区间 qq，然后找到最靠后的覆盖次数为 xx 的位置 pp，后面只考虑 l≥pl\ge p 的区间。因此我们需要维护 ll 在一段区间内的线段中 rr 最小的，直接对每个 ll 开一个 multiset 维护其对应最小的 rr，再开一棵线段树记最小值（不要对每个线段树节点开 multiset！！！），再开一个线段树记录每个位置的被覆盖次数，需要支持区间 +1+1 和二分最后一个 ≥x\ge x 的位置。
因为每个线段至多被删除一次，所以总共操作次数也是 O(m)O(m) 的。所有数据结构部分都是单 log⁡\log 的，总复杂度 O((n+m)log⁡n)O((n+m)\log n)。

小结

对于绝大多数“操作型”贪心我们都可以尝试用线性规划对偶去获得另一个视角，从而得到一些思维上较为直接的 DP 或者贪心，不过在经过一些化简之后再重新从原问题的角度考虑可能会更方便。另外有的题目在描述成线性规划本身就需要一定手法。

偏序集上的最小链覆盖与最长反链

当今的 OI 界中，Dilworth 定理已经成为老生常谈的内容了，但仍然存在一些需要我们自己寻找偏序集以获得 Dilworth 定理形式的题目。因此这里主要记录这一类题目。

例题 1. P4298 [CTSC2008] 祭祀

给出一张 DAG，从中选出尽量多的点使其两两不可达。
题解
最直接的 Dilworth 定理板子。不难发现 DAG 上的可达性构成偏序关系，于是由 Dilworth 定理，答案相当于将图划分成若干个集合使得每个集合内部任意两点都具有可达关系。
那如果我们直接把可达关系求出来，直接跑个流求出最小链覆盖即可。而可达关系可以通过跑一次传递闭包来解决。
总复杂度 O(n3)O(n^3)。构造方案直接根据 Dilworth 定理的证明构造。

例题 2. P11231 [CSP-S 2024] 决斗

有 nn 只怪兽，第 ii 只的战斗力为 aia_i。你每次可以选择两只怪兽 x,yx,y 让 xx 攻击 yy，如果 ay<axa_y<a_x 那么就删去 aya_y。每只怪兽总共只能攻击一次，最小化最后剩下的怪兽的数量。
题解
不难发现如果只保留有效的攻击并且将一次 x→yx\to y 的攻击连成一条边之后，我们得到的图会是一个链覆盖。而我们的偏序关系如下：(i,ai)≤(j,aj)(i,a_i)\le (j,a_j) 当且仅当 ai<aja_i<a_j 或 i=ji=j。
显然每条链会剩下一只怪兽，因此我们要求的就是最小链覆盖，转化为最长反链之后就是求出序列的众数。

例题 3. P3974 [TJOI2015] 组合数学

有一个 n×mn\times m 的矩阵，你需要进行若干次操作，每次选择一条从左上角走到右下角，每次只往右或者往下走的路径，并令路径上所有权值 >0>0 的格子的权值都 −1-1。问最少要进行多少次操作才能让整个矩阵变成全 00。
题解
这个形式看起来像前面线性规划对偶的几个题，但是本题中操作存在与前面几个题不同的性质。在本题中，偏序关系为矩阵中坐标的二维偏序，那么不难发现每一条操作的路径都是一条偏序关系链。因此本题求的仍然是最小链覆盖。
用 Dilworth 转化为最大独立集之后，不难发现同一个位置上的所有物品要么同时选要么同时不选，所以可以直接看做关于格子的带权最大独立集。直接从左下往右上进行 dp，加上二维前缀 max⁡\max 优化之后不难得到如下转移式：
fi,j=max⁡(fi+1,j,fi,j−1,fi+1,j−1+ai,j)f_{i,j}=\max(f_{i+1,j},f_{i,j-1},f_{i+1,j-1}+a_{i,j})
最后 f1,nf_{1,n} 即为答案。总复杂度 O(nm)O(nm)。

例题 4. P4769 [NOI2018] 冒泡排序

定义一个排列 pp 是好的当且仅当对其冒泡排序的交换次数为 12∑∣i−pi∣\frac 12\sum |i-p_i|。现在给定 nn 和一个长为 nn 的排列 qq，求有多少个字典序严格大于 qq 且是好的排列。
题解
首先不难发现，交换次数达到最小值相当于每个数都只会朝着目标方向一直交换。如果存在 i<j<ki<j<k 满足 pi>pj>pkp_i>p_j>p_k，那么 jj 就需要跟 ii 和 kk 各交换一次，那么肯定不合法了。因此一个好的排列应该不存在长度为 33 的下降子序列。
根据 Dilworth 定理，最长下降子序列长度不超过 22 等价于可以划分成不超过两个上升子序列。进一步的，可以调整法证明，如果可以划分成两个上升子序列，那么用所有前缀 max⁡\max 作为其中一个子序列，剩下的作为另一个，总是一种合法方案。
而我们知道，一个排列的前缀 max⁡\max 以及其位置可以画成一条不会到达 y=xy=x 下方的折线，因此一个合法排列与一条这样的折线一一对应。
接下来处理字典序大于 qq 的问题。枚举 LCP，假设现在我们要求 pp 和 qq 前 i−1i-1 位相同，且 pi>qip_i>q_i，我们需要求方案数。首先如果当前前缀已经不合法就直接判掉。
记前面 i−1i-1 位的 max⁡\max 为 mxmx，最小的未使用的数为 mnmn，显然我们只能填 mnmn 或者比 mxmx 大的数。不过由于 qi≥mnq_i\ge mn，所以我们不需要考虑填 mnmn 的情况，因此能填的一定是一个后缀，而且当前位置一定是前缀 max⁡\max。
我们发现这个问题相当于在网格上有一条竖着的线段，我们需要求从它们中每个点走到 (n,n)(n,n) 且不碰到 y=x−1y=x-1 的路径数量之和。不难发现这个相当于从线段左下角的左侧出发到 (n,n)(n,n) 且不碰到 y=x−1y=x-1 的路径数量，直接反射容斥即可。
总复杂度 O(n)O(n)。

小结

有很多常见的偏序关系需要我们自己去发现，这样可以对问题进行一些有效的转化，从而得到新的视角。

一般图中的最小点覆盖与最大独立集

任意一张图上的最小点覆盖方案与最大独立集方案一一对应，而且互相对应的方案选择的点集互补。证明十分简单，考虑将每个点选或不选视作染色为 00 还是 11，那么最小点覆盖要求不存在 0−00-0，最大独立集要求不存在 1−11-1。

例题 1. P9036 「KDOI-04」挑战 NPC Ⅲ

给出一个含有 nn 个顶点，mm 条边的无向图 GG，求 GG 中大小恰好为 n−kn-k 的独立集的数量。
题解
把问题转化为对大小为 kk 的点覆盖计数。
显然，一个度数 >k>k 的点必须选上，否则就需要选择它的所有邻居。将这些点选择并删除之后，图的边数应该要小于等于 O(k2)O(k^2) 才有可能有解，因为我们希望用 kk 个度数不超过 kk 的点覆盖所有边。
采用经典的爆搜策略：每次选择度数最大的点，枚举其是否选择，如果当前图中最大度数 ≤2\le 2 说明连通块都是环和链，可以直接把每个连通块的答案预处理好然后乘起来。
因为每次要么选择一个点要么选择它的所有邻居，所以复杂度不超过 T(k)=T(k−1)+T(k−4)=O(λk)T(k)=T(k-1)+T(k-4)=O(\lambda^k)，其中 λ≈1.46\lambda\approx1.46。因此总复杂度大概为 O(k2λk)O(k^2\lambda^k)。

小结

有的时候最大独立集和最小点覆盖的转化在一些 NPC 问题的速度优化上会有一些用处。

矩阵的转置原理

这一类问题与线性规划对偶类似，本质上是对算法进行一些对偶类的操作。因此大部分转置原理相关题目的本质都是将问题转化之后用较为方便的方法解决再将完整做法转置回来，在转置方面的变种并不算多，因此在这方面就只给出一道例题（说白了就是我还不会转置原理）。

例题 1. P11824 [湖北省选模拟 2025] 团队协作 / team

一棵带点权的树，对于每个点求所有包含它的树上独立集的最大点权之和。
题解
不难发现这个问题是线性的，所以对其转置之后得到如下问题：
每个点还有一个系数 wiw_i，对于每个点 ii 求所有 max⁡v=i\max v=i 的独立集中所有点 ww 之和的和。
考虑按照 vv 从小到大依次加入每个点，需要维护的就是二元组 (x,y)(x,y) 分别代表独立集数量以及独立集的 ∑w\sum w 之和。
于是进行动态 DP，记 fi,0/1f_{i,0/1} 表示 ii 的子树内 ii 是否选择，所对应的二元组。
树剖维护每个点所有轻儿子对应信息合并的结果，写成矩阵形式方便接上重儿子的答案，用线段树维护每条重链上矩阵的积。
因为合并的撤销并不是很方便，所以用线段树维护每个点轻儿子信息的并，每次修加点的时候跳重链然后在线段树上修改，每次加一个点之后 f1,0+f1,1f_{1,0}+f_{1,1} 的变化量就是以这个点为 max⁡\max 的独立集数量以及权值和。
最后我们只需要把整个过程转置回来，封装每一种操作的转置操作，然后将所有倒序执行即可。总复杂度 O(nlog⁡2n)O(n\log^2n)。

例题 2. CF2039F2 Shohag Loves Counting (Hard Version)

对于一个数组 aa，定义 f(a,k)f(a,k) 表示 aa 中所有长度为 kk 的子区间中的 max⁡\max 的 gcd⁡\gcd。一个数组 aa 是好的当且仅当所有 f(a,i)f(a,i) 互不相同。现在 qq 次查询，每次给定 mm，你需要求出有多少个所有元素都在 [1,m][1,m] 之间的好的数组。
题解
记所有长度为 ii 的子区间的 max⁡\max 构成的集合为 SiS_i，那么 fi=gcd⁡Sif_i=\gcd S_i。不难发现 Sn⊂Sn−1⊂⋯⊂S2⊂S1S_n\subset S_{n-1}\subset\dots\subset S_2\subset S_1，注意这里都是严格包含，因此应该有 f1∣f2∣⋯∣fn−1∣fnf_1\mid f_2\mid\dots\mid f_{n-1}\mid f_n。所以 nn 肯定是 O(log⁡m)O(\log m) 的。另外因为 ∣S1∣=n,∣Sn∣=1|S_1|=n,|S_n|=1，所以 ∣Si∣=n−i+1|S_i|=n-i+1。而我们知道 Si→Si+1S_i\to S_{i+1} 的时候相当于从当前序列中删除所有极小值，因此极小值应当一直唯一，即序列单谷。
考虑序列从大到小排序后的序列 s1,s2,…,sns_1,s_2,\dots,s_n，我们需要保证的就是 ∀i,gcd⁡(s1,s2,…,si)>gcd⁡(s1,s2,…,si+1)\forall i,\gcd(s_1,s_2,\dots,s_i)>\gcd(s_1,s_2,\dots,s_{i+1})，而其会对答案产生 2n−12^{n-1} 的贡献。直接开始 dp，不难发现我们从大到小依次加入每个数，把 22 拆到每一次添加的过程中，这样我们就只需要记录当前所有数的 gcd⁡\gcd。记 fif_i 表示所有 gcd⁡=i\gcd=i 的序列的答案，于是从大到小枚举 xx 并尝试加入 xx，转移为
fi←fi+∑k>12fik[gcd⁡(ik,x)=i],fx←fx+1f_i\gets f_i+\sum_{k>1}2f_{ik}[\gcd(ik,x)=i],f_x\gets f_x+1
对 gcd⁡\gcd 部分容斥一下，记 si=∑kfiks_i=\sum_k f_{ik}，现在转移为
fi←fi+∑i∣j∣x(2sj−μ(ji))−2fi,fx←fx+1f_i\gets f_i+\sum_{i\mid j\mid x}(2s_j-\mu(\frac ji))-2f_i,f_x\gets f_x+1
高维后缀和优化（狄利克雷后缀和）可以做到单次 O(mlog⁡mlog⁡log⁡m)O(m\log m\log\log m)。
不难发现上述算法是一个线性变换。我们可以理解为有一个向量 v=(s1,s2,…,sn,f1,f2,…,fn,tmp1,tmp2,…,tmpn,1)Tv=(s_1,s_2,\dots,s_n,f_1,f_2,\dots,f_n,tmp_1,tmp_2,\dots,tmp_n,1)^T，初值为 (0,0,…,0,1)T(0,0,\dots,0,1)^T。而我们将 x=ix=i 的时候进行的变换记为矩阵 AiA_i，于是答案可以写成：
(1,0,…,0,0)×A1A2…Am…(0,0,…,0,1)T(1,0,\dots,0,0)\times A_1A_2\dots A_m\dots(0,0,\dots,0,1)^T
注意这个时候相当于是一个 1×11\times 1 的矩阵，因此将其转置之后答案应该不变。转置之后的式子如下：
(0,0,…,0,1)×AmTAm−1T…A1T×(1,0,…,0,0)T(0,0,\dots,0,1)\times A_m^TA_{m-1}^T\dots A_1^T\times (1,0,\dots,0,0)^T
这样的话我们从小到大扫描 mm 做转置之后的操作，注意需要单独开一个变量表示原来作为 11 的位置现在的值，这样后面的操作可以直接接在前面的操作上，于是我们就能对于每个 mm 求出答案了。于是做完了，总复杂度仍然为 O(mlog⁡mlog⁡log⁡m+q)O(m\log m\log\log m+q)。

小结

由于转置原理本身的性质，将一个问题转置之后其算法过程也会前后翻转，在一些相当于对操作序列进行前插的问题上优化的空间就比较大。

总结

对偶类的问题在 OI 中十分常见，我们可以利用这些对偶将要解决的问题进行一些转化，从而可以以全新的视角考虑问题。虽然上面提到的这些对偶的过程可能没有改变问题的本质，但是它的转化给我们提供了化简或者优化的机会。
希望本文能够让大家提升对这一类问题的理解，也欢迎感兴趣的同学来讨论（虽然我可能并不是很精通这一类问题）。

评论

共 25 条评论，欢迎与作者交流。

正在加载评论...