Dada's WIKI

· · 算法·理论

Dada's WIKI（持续更新）

前言

鉴于此前做题记录几乎断更，而且又没有时间去重新整理一遍，于是决定写 Dada's wiki，当作做题记录。

本文更加侧重于记录思路上的突破口，以及细节实现时要注意的点。

目前更新至 20250117.5。

缺了 20241211～20250103。

完成的还有 20250201~20250211，20250222。

Part. 0 性质挖掘

这部分主要用于记录那些“显然的性质”。

  1. P3344 —— 一些容易忽略的性质
    • 看上去题面很网络流，假了之后感觉很难以下手，因为你并不知道每个圆是否被选过。
    • 但是，如果每个圆要求覆盖一个区间的话，这个问题就好做的。
    • 对于单侧而言确实是这样，因为我们每个圆的半径要求相同，但是两侧就不符合了。此时我们仍然应该记录下这个性质。
    • 注意对于DP而言，如果我们设 F(i,j,k) 表示第 i 个点上面上一个用的是 j，下面用的是 k 的状态的时候，我们不需要两侧一起的时候符合，我们只需要单侧符合即可。
    • 然后就很能DP了。

Part. 1 贡献计算

对于很多计数问题，我们需要去计若干函数的和；对于很多最优化问题，我们需要计算若干形式的函数的最优。

此部分讲述的内容是转化这个要处理的函数，使得问题变得更加可做。

1. 贡献函数为 F(x) = W(x) \times C(x)，即关于一个值的系数和这个值出现的次数。

考虑把任何一个函数拆开：

尝试把 W(x) 拆开

此时我们可能需要做的事情是数另一个 C'(x)，这样不仅能够避开计算 W(x)，还能够使得 C'(x) 比 C(x) 更可数。

例题：
  1. P2481
    • 考虑把每个数拆成 1\cdots 1 + 1\cdots 1 的形式，再进行dp。

2. 贡献函数为 F(x) = W(x)^k，即多次方型贡献。

本来计数一个 u 是容易的，但他非要让你数 u^v。

两种思路：

1. 变成选多个的方案数。

例题：

2. 多项式优化：

这个另谈。

类似问题：F()=\sum A_x \times A_y：

方法：已算进贡献\times未算进贡献+未算进贡献\times已算进贡献。

3. 固定其中一个函数值。

通过固定一个维度来求多个维度都有关的贡献。

例子：

  1. P5115

    • 这题就是把 LCP\times LCS 中任意一个固定下来，然后对另一个进行统计。

  2. nfls1007

    • 题面：你取出了这个字符串中所有长度为m的子串。你想知道，对于每个长度为m的子串，有多少个其它长度为m的子串与它相似，相似定义为至多一个不同。n,m \le 10^6。

    • 转成SA数组。

      笛卡尔树启发式合并，转换成矩阵加或矩阵求和形式，然后用数据结构维护。

4. 贡献函数为 F(x) = A(x)+B(x) ，即贡献独立。

其实这部分难点在于观察到贡献独立。

准确的说，当贡献独立的时候，我们可以拆开。

一定要检查贡献是否独立

  1. nfls12384

    • 题面：有一个长度为 2n 的链，你需要给每个点新匹配一个点并连上边，使得整个链上的每一条边都被至少一个匹配连的覆盖。

      如果一个两个匹配时嵌套的，贡献为右边那个匹配的两个点的权值和。

      求所有合法匹配方案的权值和 n\le4000。

    • 把两个点的权值和拆出来，分别考虑：一个点能够有多少种方法让他产生贡献。

  2. gym105170J

    • 如果我们维护重心的位置的话不可做。
    • 我们把带权重心的大小放在每条边上，发现：一条边一定会带来权重和更小的那边的贡献
    • 发现一条边带来的代价是分成两段的一次函数；每次修改也只会对一条边的一次函数产生影响。
    • 考虑用优先队列维护转折点以及函数变化的方式，发现复杂度可做到 O(n\log n)。

  3. P5987

    • 注意到 x,y 坐标独立（因为我们任意一个矩形的操作都独立），此时最大面积等价于最大化 x 轴覆盖的和 y 轴覆盖的长度。
    • 因此问题就转化为了 x 和 y 轴分别考虑。

5. 容斥

大板块：

1. 钦定不合法状态容斥（常考）

我们数一定 合法/不合法 是困难的，但是我们可以钦定有几个不合法最后跑二项式反演求出恰有即可。

一定要仔细分析容斥系数！ 一定要仔细分析容斥系数！ 一定要仔细分析容斥系数！ 一定要仔细分析容斥系数！

  1. P8329
    • 首先，我们可以得到一个不考虑前面前面非叶子节点具体选了几个的做法，但是如果考虑上，这需要 O(n^5) 状态，不可做。
    • 如果我们钦定了每个点非叶子但又没有东西连他的时候，这就可以刻画了。
    • 乍一看，这并没有用处，但是我们能够把容斥系数放进转移里面，如果新一个点我们钦定他非叶子又不连边，我们就把他的转移系数乘上 -1。这样我们就省掉容斥过程了。
    • 剩下就是一些基础的dp优化。
2. 固定套路容斥

  1. 子集容斥

  2. 二项式反演容斥

  3. minmax 容斥

    1. nfls12393&&CF1392H

      • minmax容斥模板

  4. 莫比乌斯反演容斥（提防一下）

Part. 2 状态刻画

这是一些常用的刻画题目的办法。准确的说，是对题意的转化使得更好地利用上各个条件。

一 钦定端点刻画

通过一个信息的特殊点来入手，通常可能是极值，极点等特殊位置。

  1. NFLS17617 && HDU ZCC loves traffic lights
    • 红绿灯题性质通常很多，我们注意到他肯定是通过了一个绿灯的边界，因此我们枚举这个绿灯的边界，然后正反向考虑最短路。
    • 对于正向而言，我们肯定考虑不等红绿灯，是简单的。
    • 对于反向而言，我们只需要做出发时间固定的最小值，这也是好求的。

二 图论建模刻画

1. 普通图论建模：

把二元信息看作连边，在抓住图的性质分析。

  1. P9257

    • 注意到，我们可以把不知道的两个人之间连一条边。
    • 发现是最小点覆盖和能够形成最小点覆盖的位置。

  2. NFLSP512

    • 题面：有若干条某个时间打第几个鼓获得的收获这样的贡献。每次可以拓展区间地打一个鼓，然后多次询问从某个点开始能获得多少收获。
    • 把问题先倒着考虑，然后考虑建图，由 [l,r]\to[l+1,r],[l,r-1] 的问题。
    • 发现只有关键点有用（优化状态数量），因此我们对于只对关键点进行dp。

专题：树结构

1. 重构树

我们都知道，可以通过按一定顺序加点连通后的连通块可以解决一些问题。

但是当你如果要同时处理另一个毫不关联的信息呢？

怎么办？

这时候，我们可以把这个过程按树结构建出来，这样你就能够动态的查看这个过程了。

  1. nfls12574

    • 题面：在树上求路径 P(x,y) 的数量使得 x 是这之中最小的， y 是这之中最大的。

    • 我们考虑从小往大加点，这样我们就能够保证其中一个限制。

      但是如何注意另一个限制？

    • 我们可以对另一个限制建重构树，再用动态数据结构动态维护。当然第一棵树也可以重构树，就能够用轻量化的数据结构维护第二棵树了。

2. 奇怪建模

  1. AT_ddcc2017_final_e

    • 边拆点建模
3. 树上圆理论

树上同样可以进行圆并圆交

专题：网络流

1. 图论拆入点出点建模

最最最典型的题目：DAG最小链覆盖

  1. nfls13272

    • 题面：给出一个图，给每条边染两种颜色1，2，代价为 c1,c2，求最小代价。(n\le5\times 10^4)

      限制：t,x,w,l,r N(x) 表示 x 强连通分量。

      若 t = 1，则表示 out(N(x)) 这些边中，颜色为 w 的边的数量在 [l, r] 之间。

      若 t = 2，则表示 in(N(x)) 这些边中，颜色为 w 的边的数量在 [l, r] 之间。

      若 t = 3，则表示 out({x}) 这些边中，颜色为 w 的边的数量在 [l, r] 之间。

      若 t = 4，则表示 in({x}) 这些边中，颜色为 w 的边的数量在 [l, r] 之间。

2. 最小割

每个东西有两种决策的时候，可以考虑最小割。

  1. gym105173B
    • 发现三类点也有两种决策，把二类点的决策拆成两个部分，然后建图最小割。
3. 费用流&&模拟费用流

直接上例题：

  1. P7425
    • 对时间线拆点建图，一条流表示一个人走。
    • 此时只需要对 A 地方的每个时刻限流即可。

三 概率期望刻画

注意我们是用概率还是期望转移，这取决于我们的问题问什么。

  1. uva12164
    • 略

四 缩放限制

放宽限制！放宽限制！放宽限制！

有时候，你会注意到一些更多的东西，而这些情况不好刻画的时候？

我们就可以考虑放宽限制。

五 多项式刻画

板块太大了，这里写不下，就放一些题目算了。。。

六 构建映射

对于很多问题，如果我们能够构建出这个问题和另一个已知问题的某种映射方式，那我们就赢了。

其实容斥的本质也是映射？似乎是的。

  1. P8058
    • 对于分数的排名是简单的，重要的是我们怎么考虑对分数二分。
    • 注意到我们如果同底分数二分是简单的，但是若以 n 为底，我们是没办法区分出所有的分数的。
    • 但是注意到我们的差值一定是 \ge \frac{1}{n^2} 的，因此我们以 n^2 为底即可。
    • 这里本质上是 分数 到 同底分数 之间的映射。

Part. 3 解决问题

记录一些实质性解决问题的办法。

一、构造

若干种办法，但是取决于你的脑子。

  1. P11337
    • 我们可以先确定树形，然后再染色
    • 构造很神秘

1. 增强限制构造

方法：

  1. 你需要拥有一个良好的脑子
  2. 考虑我们仅使用某一类操作，并试图发现只通过这类操作将原问题解决
  3. 最后再考虑能否都操作进行进一步的扩展

例题：

  1. UOJ810 比特迷宫
    • 思路：我们限制操作使得他全部不进位，此时发现这些操作可以完全改变某一位的状态，然后发现这些状态的和的最大值可以符合题目限制。
  2. CF1693F I Might Be Wrong
    • 思路：我们注意到在他那个限制之下，我们只需要做 01 相等的区间就行了。

2. 增量构造

方法：通过已经维护的东西增加调整。

例题：

  1. P3561
    • 思路：我们通过一点一点的加东西来构造哈密顿路径，最后再调整使得它变成哈密顿回路。
    • 过程中有非常多的证明点。
    • 这是个经典题。

3. 求出操作上下界

方法：我们直接声称需要多少次操作能够解决。至于为什么要这么想，可能是有人脑子比较好吧。

例题：

  1. CF1685C
  2. QOJ9768
    • 首先，能够注意到我们只有当 pA|\operatorname{lcm}(pB,pC)，pB|\operatorname{lcm}(pA,pC)，pC|\operatorname{lcm}(pA,pB) 等等的时候才有解。
    • 注意到 pA=bc, pB=ac, pC=ab。
    • 我们想尽一切办法去利用上 b,c。观察到如果我们让 A 每个位置都和 b,c 整除异或有关，B，C 同理，那么一定合法。
    • 除了特殊情况外（有两个以上的 a,b,c = 1），其他时候直接让每个序列都像 A_i=[i \mod b = 0] \bigoplus [i \mod c = 0] 一样构造就一定可以。

4. 随意填

似乎，这种情况更加普遍一点。

此部分更注重于证明。

证明很多，注意一下抽屉原理。

  1. P3557

    • 发现：随意填是正确的

  2. NFLS16329

    • 给定一张DAG，保证不存在长度为 k 倍数的极长链。求出划分成 k 个独立集的办法。
    • 注意到，当我们给一个点染色的时候，前面一定不能够吧所有模 k 的余数都覆盖的路径，这样就一定存在长度为 k 倍数的极长链了。
    • 因此，我们可以直接染第一个余数的。这样一定合法。

5. 纯操作构造

  1. NFLSP1323
    • 题面：给出一个排列和一个数x，一次操作时可以选择排列中的一个不是x的数，满足其位置和x所在的位置的奇偶性不同，然后交换x和这个选中的数。需要在5n次操作内完成对排列的排序，即得到1,2,⋯ ,n或说明不可能做到。
    • 注意到操作可逆，此时我们显然是尽可能简化问题更好。
    • 在剩下至少四个的时候，我们都还能让东西归位。
    • 对于我们剩下三个且无法进行操作的时候，我们需要证明他一定不存在方案，通过 经典思路：一次操作无法改变什么 来证明。

二、贪心

这个太多了，根据感觉选择一种非常正确的做法，然后如果有问题再修改（反悔等）

如果发现不太对的话也可以对其他做法有帮助。

  1. NFLSP4518 & Topcoder Barracks
    • 考虑贪心策略，每次当你不能够把别人城干掉的时候一定是尽可能干掉别人的士兵，然后对城刮痧。
    • 为什么是对的呢？因为每次都会有人对你的兵力造成影响，这肯定不是我们希望的。反正他这一轮都会产兵，不如先把他剩下的兵干掉再想办法。

三、容斥

  1. nfls965
    • 题面：n\le10^5 个位置有 l_i,r_i 实数范围内的值独立随机，求期望逆序对数。
    • 考虑如何求两个位置的贡献，发现可以 calc(r_i,r_j)-calc(r_i,l_j)-calc(l_i,r_j)+calc(l_i,l_j)。
    • 然后就非常好树状数组维护了。

四、分治

各种分治，只要你能够把贡献拆开来或者合并起来，那么分治就是最好的选择。

1. 根号分治

这是一个挂。有些时候还是要想想的，在没有任何做法的时候。

  1. nfls12404
    • 有 n \sum s\le 3\times 10^5 个模式串，加很多个匹配串，看有多少个模式串里出现匹配串，然后带权带修。
    • 考虑：建出询问的 ACAM，然后对于 \ge \sqrt n 的串只有 \le \sqrt n 个，直接暴力去fail树上做，查询直接一个一个查，而对于 \le \sqrt n 的直接在树上用 O(1)\sim O(\sqrt n ) 数据结构维护。
  2. P8330
    • 有关众数，而且我们能够设计出有关数的数量的算法，那我们就可以考虑根号分治。
    • 做出两个做法，发现其中一个做法有优化空间，然后搞定了。

2. 线段树分治

有时候，我们对于原问题的数据结构支持插入而不支持删除。这时候，我们可以上线段树分治，通过一个 log 来规避删除。

五、数据结构硬维护

这也是通常最常用的办法。注意到，我们数据结构维护东西不一定是板子，很可能是一些奇妙的改变应用。

本栏目更新一些巧妙的数据结构做法

  1. NFLSP528
    • 题面：维护全局单点加，区间和，全局与、或、异或 合并。
    • 直接上线段树合并，维护的操作有交换子树和合并子树，发现复杂度是对的。
  2. NFLS17596
    • 题面：有 n 种糖果，第 i 种糖果有 a_i 个，分给两个人，要求总数相同，问方案数。
    • 考虑DP，很容易写出一个 O(n^3) 状态，O(n) 转移的DP。
    • 但是，当你考虑开始拆步骤转移的时候就走偏了。
    • 正确的应该是发现这个转移是等差数列求和？！！直接硬做就完了。

六、哈希

近期似乎很喜欢考，原因未知。

有一些哈希的办法，待补充。

例题：

  1. P10785【NOI2024D1T1】
    • 直接将问题转换成 多重集 相同，然后做 多重集哈希。
  2. QOJ 9459
    • 比较神秘的题。
    • 首先，通过求出字数大小得到一个指标，再对这个指标进行 树哈希。
  3. P5987
    • 对于每一维坐标，注意到我们每个格子对应的操作集合固定，因此我们可以哈希维护相同操作集合的格子即可。

bitset

这也算哈希吧！

  1. nfls13270

    • 题面：对于一个01序列，定义 f(A) = [sum1-sum0>0]。

      你有两个序列 A,B，问有那些 k 使得 \forall_{i\in[k,n]} f(A[i-k+1,i])=B[i]

    • 首先处理01序列变成一个折线，然后你会发现，合法段和k是两个分离的信息。

    • 因此就不存在线性或线性对数算法，只能考虑 bitset。

      考虑维护一个bitset表示每个位置是否不行，这样只需要把每个位置维护的或上就行了。

    • 发现按顺序加还是不行，因此我们考虑从小到大加，这样就能够很快速维护出每个位置前面那些比他小的，然后就OK了。

特殊套路

求逆运算

虽然大多数时候问题都不支持求逆，但是当遇到支持求逆的问题的时候需要考虑一下。

Part. 4 分化子问题（转移）

需要考虑的情形：

  1. 首尾界不明导致算重
  2. 本身同一状态会通过很多次转移
  3. 会有情况转移不到
  4. 转移顺序导致利用了一些未知值

方法如下：

1. 钦定首尾界

方法：硬点首尾界选或不选。

类似于 dp_{S,0/1,0/1,\dots} 这样。

例子：

  1. mxoi20240825：需要注意的就是r决策不明导致重复进入统计

2. 按某种顺序枚举转移

比较玄学和思维，看题。

  1. nfls17072

    求染色方案数使得 **同色点对的距离的最小值** $\in [L,R]$。 - 注意到，我们可以如果能够钦定顺序的话，我们就可以清楚每个点染的颜色了。但是发现dfs序不行，因为你 $k$ 邻域可能会有重点。 - 因此就试一下bfs序，然后就行了。

  2. P11343

    • 类似于APIO2024T2 的题目。
    • 我们按照 B_i 从大往小考虑。

3. 钦定最值转移

当你发现钦定前面，后面都不好的时候，我们就可以通过钦定最值了。

这种情况下，我们可能需要记录值域了。

特殊问题

1. 走路题

这一类题目就是，我们设计出很多个状态，每个状态的转移边是有序的，求第 k 小类。

首先，处理出每个点走下去的方案总和。

其次，求出往某个边走所需要的数量区间。

然后，对于可以压缩状态的情况，我们需要考虑快速地冲过一些点，这需要用数据结构维护。

  1. NFLSP16576 && Topcoder CompressedStringSearch

    • 典型例题，注意开 int128。

Part. 5 优化技巧

这部分不全是“优化"技巧，更多的可能是题目的突破口。

尽可能得利用上题面的全部信息，思考构建信息之间的联系。

准确的说，这个是在更好地利用信息。

第一类：分析无用状态

在很多时候，状态和答案的表示是松散的，这之中可能会带来量级的优化，而且极有可能会成为某道题做法中重要的一部分。

遇到的时候会产生这些感觉：

这个时候，就引导我们去构造一些情况并归纳来分析了。

此外，钦定转移关键点也是一种方法，我们只需要通过关键点转移，可以大大降低复杂度。

例子

  1. 动态维护两串反转一个区间之后是否相等。
    • 首先发现，两个字符集一定相同。
    • 发现：当串完全一样的时候是好做的。
    • 感觉串不一样的时候方案很少，而且和最左最右不一样的有关。
    • 得出结论：发现只有一个位置能够作为中心点翻转。

第二类：分析数值分布

数学规律？可能需要结合打表

专题：背包类型

当你把一个问题化成背包的时候，说明他一定是没有别的解法了。此时你就需要结合题目信息进一步的分析。

  1. nfls13271
    • 题面：给定一棵 n 个点的树，1 号点为根。给定一个整数 m。 对于树上的每个结点 u，有三个参数 X_u, Y_u, Z_u，你需要在 u 到根的路径上（不包括 u）选择至少 X_u 个结点，在 u 的子树（不包括 u）中选择至少 Y_u 个结点。你需要保证你总共选择了 m 个结 点。然后，令 S1 表示 u 上面被选择的结点到 u 的距离和，S2 表示 u 子树中被选择的结点到 u 的距离和，你需要求出 |S1 − S2 + Zu| 的最小值。 两点之间的距离为两点之间简单路径上的边数。n\le10^5
    • 首先发现，式子可以变化成 |m\times dep(\{x\})+Zu-dep(\{S1\cup S2\})|。
    • 发现对于右边是一个背包，不可做。考虑由于是树，所以覆盖的值应该比较连续，求出最大值和最小值之后考虑调整。此时发现只有两种内的情况是取不到的，特判即可。

Part.7 杂项

  1. AT_agc009_e

    “多退少补“的思想来转化状态，把数量状态换成两个都是数值状态。

  2. nfls12482

    题面：求 m\le 10^5 条线段把平面图 V\le 10^9 划分成多少个格连通块。

    由于格点量级太大了，所以我们考虑怎么样把状态转换乘和线有关

    平面图欧拉定理：F(\text{面积}) = E(边数)-V(\text{点数})+C(\text{连通块数})

    然后扫描线维护连通块即可，因为只会有效合并 m 次，所以复杂度是可以均摊的。

    写线段树。

  3. nfls12731

    题面：为了让这场比赛更加有趣，于是你给出题人出了你的威力加强版：现在有 q 组 询问。在每组询问中你需要对于 [l_i , r_i] 的区间求出如果恰好选 k_i 个连续子段，和最大为多少。

    我们能够得到一个 WQS二分 的做法，但是你需要合并凸包的复杂度是 O(n) 的。

    因此，我们先建出线段树维护区间凸包，然后在二分就能够在 O(nlog^3n) 时间内完成了。

    但是发现：如果整体二分之后，每次移动也只是 O(nlogn) 的，于是乎总复杂度就变成了 O(nlognlogV) 了。

    重点，闵可夫斯基和维护 (\min,+) 凸包。

  4. P11094

    重点：对于一个带修序列 A，要求每次找出 R 以前的最大的 x 使得 \forall_{i\in [x+1,R]} a[i]\ge x

    变成区间加和找零位，相当于 ban 掉了一些位置然后剩下的找合法位置

  5. gym105143C

    数学

    • 考虑用两个互质的数来填充较大的数，注意到 小凯的疑惑 ，对于后面的数我们是覆盖的比较满的。这样能缩小问题规模。这也可以用于一些奇怪 1e9 值域的背包。
    • 构造

  6. P4581

    经典随机化结论

  7. NFLS5050

    • 题面：多次区间本质不同子序列数量。 n\le5\times 10^5
    • 我们可以转换成动态dp的形式，做到 O(n \log n V^3)。
    • 注意到我们可以做矩阵逆元（具体的，我们把逆元序列从前面倒着接过来，就能够消掉前缀）做到 O(n V^3)。
    • 发现很多位置没有，做到 O(nV)。

  8. 从模数入手

    对于奇怪的模数，我们需要分析模数的性质。

    1. NFLS16323 && P10175
      • 对于此题而言，注意到修改可以变成 k \times u + b 的形式，在多项式的角度下可以优化。
    2. NFLS17614
      • 模数是三个小质数的乘积，我们就可以拆开做完之后用CRT合并起来。
      • 对于模数很小的情况，很多变量都会出现循环节。

  9. AT_s8pc_5_f

    • 将最大值区别化。由于复杂度瓶颈在于多个最大值，最大值的实际大小不影响答案，因此我们可以将最大值区别开来，变成只有一个最大值的情况，于是就能够优化了。