一些想法的记录（from TC/ATC/CF..)

OI

DP

通用优化

SRM 473 L3
2018ECFinal E

• 对于一类状态 $O(T)$，转移总复杂度为 $O(Tm^2)$ 类似于二重和式的转移，可以将 重复用到的部分 记录下来。优化为 $O(Tm)$。
• DP求最小前缀和恰好为 $[0,x]$ 的方案数，如果直接两位附加状态记录就是 $O(n^3)$ 的，原因在于每一次加入一个值之后这个新增的前缀和是$O(n)$的。实际上我们倒过来DP就能做到$O(n^2)$了
• 树上背包的小套路：要从 $n$ 个点的树中取 $k$ 个做背包DP，复杂度是 $O(nk)$ 的（证明：考虑在lca处计算贡献，每次取前一个子树的dfs最大$k$个点，后一个子树的最小$k$个点，每个点最多产生$2k$的贡献）

生成函数

CC SIGFIB

• 线性递推式与母函数逆元是可以互推的
• 可以结合一些微积分（或者其他一些代数技巧），例如把指数取下来可以通过求导得到
• 斐波那契卷积具有特殊性质（参见CM）

二阶递推式的一个性质

• More generally, any Lucas sequence of the first kind Un(P,Q) is a divisibility sequence. Moreover, it is a strong divisibility sequence when gcd(P,Q)=1.
• 参考论文

置换上的DP

JOI2016 摩天大楼

• 按照特定顺序插入，维护 相对位置，可以看出是与一个置换等价的。
• 处理相邻的关系，可以针对当前序列在最后序列中的连通性，将连通块个数记录在状态内。

倍增DP

2012集训队作业calc

• 一般来说，需要DP的东西有很强的规律性。存在 $n=10^9$ 之类的很大数据范围。

一类树形DP问题

SRM 562 L3

• 重心对于树来说，是一个及其重要的不变量
• 例如树的同构中，改变编号后重心仍然不变。
• 有一些树上的DP，利用重心为根可能就不需要枚举其他根从而降低时间复杂度。

计数 & 概率期望

随机游走系列

SRM 614 L3
rng_58 round H
SRM 641 L3
- 高斯消元。特殊的图（最简单的像树），可以考虑每个变量用主变量表出，本质上就是进行了一部分手动消元。
- 容斥。这类经过格子期望数的题，可以对应到形成了一个环，结合期望线性性解决。
- 线段树。对于一位的情况，应该还是很套路的。
- 合并等价类。上述的T3强调序列其实是迷惑眼球，考虑计算i->j的期望次数，剩下的都是等价的。

几何 / 代数上的一些trick

• 凸包面积期望。发现凸包面积可以拆成凸包上相邻点的叉积之和。

三元环与四元环的计数

• 三元环的计数
• 四元环只能在比较优秀的复杂度内进行计数。考虑在三元环计数的时候，每次访问最后一个点在数组上打上标记，后面访问的时候再次计算

一个有趣的小定理

CF 653G

• 有n个物品，两两不相同。它们被分成两堆，左边那堆x个，右边那堆n−x个。从左边那堆拿出p个物品，从右边拿出q个物品，要求p>q。方案数为$∑^{x−1}_i=\binom n i$。
• 把s1的前x个字符反转，即0变成1，1变成0，就可以对应到s2；同理s2→s1也是这个映射。- 或者考虑生成函数 $(1+{1\over x})^{i-1}(1+x)^{n-i}={(1+x)^{n-1}\over x^{i-1}}$

超度量矩阵计数

Codechef SPMATRIX

• 求这样的无向完全图的个数：边权$\in [1,n)$，每种边权都出现了，并且对于任意$x,y,z$均有$w(x,y)\le\max\{w(x,z),w(z,y)\}$。
• 注意到$x \sim y:w(x,y) < n-1$是个等价关系，且只能有一次划分。
• 所以是一个类似于笛卡尔树的东西，枚举一下端点和排列，最后的柿子就是$\frac{n!(n-1)!}{2^{n-1}}$

容斥求一类一一映射的数量

ZJOI2016 小星星

• 平常的思路可能难以保证映射不存在重复，转化为容斥“哪些点不能被映射到”

prufer序列的一个扩展

• 对于当前已经有 $m$ 个联通块的有标号生成树的数量
• $$n^{m-2}\prod_{i=1}^msize_i$$
• 原理就是考虑 prufer 编码，先把每个联通块看成一个点，那么序列中每出现一个第 i 联通块缩成的点，能连的边的数量是 size[i] ，所以序列每一位的方案数是 ∑size[i]=n，考虑每一个点的度数是在序列中的出现次数+1，所以对于每一个联通块还要补上一条连边的方案数.

卡特兰数的映射 及 树的计数

XJOI 19.2.23 A

• 普通有根树，二叉树都与卡特兰数存在映射。它们之间的映射是“左儿子右兄弟”
• 也就是两个计算方法之间的映射（对称容斥、n^2DP）
• 这道题从序列角度考虑难以DP（每次按dfs序增加），但是从路径计数角度（每次增加深度）就能满足性质两个DP合并之后的sz是之前的sz之和，可以做到$O(n^2)$

事件的独立性

2018 GP of Korea C

• 事件之间，如果存在某种相关性，往往会难以解决。这个时候，换个角度来考察，很有可能会得到事件之间的独立性，分别解决就能简单很多。
• 例如这道C题，通过观察最终存活的元素满足的性质，发现前后缀之间是独立的，就能分别解决了。

多项式

组合数的多项式视角

• 对于一些比较复杂度的组合数柿子，往往可以看做一个多项式。
• 再结合各种多项式的处理方法解决，需要注意仅限于非负整数

单位根反演

[18集训队胡策] 复读机

• 写出生成函数的形式，用来解决一类..是某个数$d$倍数的计数问题
• $$[n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_{n}^{ki}$$

数据结构

利用性质 降维

• 一类题目中可能会出现形如 恰好为$k$或$k+1$的有多少个 的询问，同时满足性质所有值$\ge k$。可以维护区间最小值，及最小值个数达到目标。
• 对于最优化问题有效：删除某些条件后仍然能求出最优解

维度之间的转化

CF 1083C

• 很多需要考虑值域的题应该很容易看出来。
• 但是例如一些树上的问题，很容易思维定势没往这方面考虑。
• 因为是全局的mex询问，从值域角度考虑就可以直接线段树上二分。

杨表

CC BB

• 两维都单调的一个东西。具体参见wiki

虚树

CF 1111E

• 这东西似乎还能换根（求lca和排序都能解决）
• lct可以参考

贪心

不靠谱的贪心写之前一定要慎重，最好有个证明的概要，否则就写暴力贪心使劲拍

结合构造

CF 578E

• 通过贪心得到上/下界，构造对应的方案

最小乘积生成树

• 考虑令 $x=\sum a$ 且 $y=\sum b$，平面上作出所有方案的 $x,y$，一定是第一个相切的最优，每次分治下去即可。
• 可以证明一定是最优化 $\sum a+k \sum b$，相对次序至多改变 $O(n^2)$ 次。

图论

建图

SRM 472 L2

• 如果题目中存在 二元关系 的时候，套用图论的模型很有用
• 每个点一个出边 —— 环套树森林 / 限制度数为$2$ —— 环
• 边 重定向 模型

DFS树

• DFS树是解决图连通性问题强有力的工具，特殊图在DFS树上都会具有一些良好的性质
• 一个常用的trick是给每个非树边随机一个权值，给经过的树边xor上

计数

APIO 2017 T3, IOI2018 D1T2

• 最常用的trick是结合欧拉公式，点，边，面之间的数量关系
• 一些推论有：对于森林，网格图的连通块计数

缩链&去重边

2018 GP of Korea E

• 除了常见的缩点，一类图论问题往往可以将一条长链缩起来。即不断合并度为2的点的两个邻居。
• 去重边也是同理。上述这题串联与并联的逆操作（判断能否通过给定操作得到输入）就是缩链与去重边。

字符串

一类循环串的子串问题

CF 1038F

• 常见的套路是在AC自动机上跑，初始的状态与结束的状态相同。

分治

整体二分的一类应用

• 有这样一类问题：每次加边，动态维护互达点对数。
• 存在这样一种分治做法：每次取 $mid$ 加入 $[l,mid]$ 中的边后做tarjan。注意到左边在强连通分量中的边只对左边有用；不在之中的边只对右边有用。所以这样分治下去复杂度就是对的。

网络流 & 匹配

一般这种看起来限制十分强，而且限制也没什么明显方向性，数据范围不大不小的题目都是网络流模型

网格图与二分图

SRM 570 L3
SRM 558 L3

• 一种是将格点当做边 / 或者将网格 黑白染色
• 表示格子的状态时可以 拆点，这些点之间连边表示 转移费用

凸性

• 很多代价函数为凸、凹函数的都可以联系网络流解决
• 比如有这样一类问题：某个元素赋为某个值的函数是导数非增的函数，有一些<=的限制；这种情况下可以分治$x$，然后跑在$x$时导数下的最小权闭合子图，可以根据是否在最小权闭合子图中来进行划分。

多源多汇的一个问题

SRM 556 L3

• 对于每对源汇，要达到指定流量
• 对于两对源汇的情况，可以 $\{a_1,b_1\}$ 与 $\{a_1,b_2\}$ 分别为超级源来判断（形式上类似于 曼哈顿距离 与 切比雪夫距离 的转化）

流量的叠加

[Ahoi2009]Mincut

• 对于一个流，可以分解为若干个流
• 于是两个两个流量相同的流网络之间可以通过跑环来变换。
• 从这个角度可以得到 关于割的唯一性 结论。

最小割树

• 对于任意三个不同的点a,b,c,有mincut(a,b)>=min{mincut(a,c),mincut(c,b)}
• 令mincut(a,b)是三个最小割中的最小值设c在a与b最小割的b集中，那么mincut(a,c)<=mincut(c,b)，那么𝑚𝑖𝑛𝑐𝑢𝑡(𝑎,𝑏)=𝑚𝑖𝑛𝑐𝑢𝑡(𝑎,𝑐)
• 所以这是两个相同的较小值和一个较大值
• 于是𝑚𝑖𝑛𝑐𝑢𝑡(𝑎,𝑏)≥min⁡{𝑚𝑖𝑛𝑐𝑢𝑡(𝑎,𝑐1),𝑚𝑖𝑛𝑐𝑢𝑡(𝑐1,𝑐2),…,𝑚𝑖𝑛𝑐𝑢𝑡(𝑐𝑘,𝑏)}

分层图记录状态的trick

• 每个点可以拆点，通过一些限制可以分成两段，用于表示在此处的状态。
• 同时结合拆成出点入点可以限制在点内的权值改变。
• 记住最小割的权是S集合到T集合的边之和

模拟费用流问题

参见WC2018课件

• 基本的问题模型：直线上的匹配，有 附加权 / 容量限制 / balabala..
• 拓展至树上（各种数据结构，可并堆？具体见WF2018C）
• 两个角度

从 DP / 图像 角度入手

• 写出 DP 转移方程，往往具有某种凸性 / 或者是相邻段斜率差1的折线
• 结合 堆 / 线段树 可以很方便地进行维护（单点搞，区间平移，之类的）

从 可撤销贪心（反向弧） 角度考虑

• 维护了两个增广集合，分别代表老鼠的增广和洞的增广。当老鼠匹配完左边一个洞后，老鼠可以反悔改为匹配右边的洞。当一个洞匹配完左边一个老鼠后，也可以反悔匹配右边的老鼠。
• 小trick：最小费用流（不一定要流量最大），可以先带上$-\infty$

存在容量限制时的扩展

• 分为两种情况：只有一方有容量 / 双方均有容量
• 对于第一种case，直接做复杂的就是对的（基于简单的均摊）
• 对于第二种case，性质是一对匹配中至少一个必选点，不能同时反悔（具体见IOI2017D1T2）

双方均会反悔且一方有容量

• 这种情况出现在洞需要一定代价，却不一定要有匹配时
• 同样同时发生反悔时，匹配交叉

最优化

基本的函数性质

SRM 560 L3

• 往往都是老生常谈却又极易遗忘
• 函数的连续性可以搞事情
• 一次函数最值在端点中取得

条件的增删

搜索

两个角度考虑

SRM 555 L3

• 存在这样一类题目：并不能快速合并两个状态，不能Meet in Middle
• 常用的方法是从两个角度考虑，在两种情况下各有优劣的算法；尝试在算法上增加某些剪枝，从两个角度证明其复杂度（往往是取min）

交互题

平面上的交互

CF 788D
- 可以考虑一些特殊的直线，例如 $x=\inf,x=y,y=0$ 之类。

计算几何

映射

CF 618G

• 一类圆相交的问题，可以以一个点为圆心，建立起到圆周的映射，变为圆周上的线段覆盖
• 类似的还有性质：不相交的凸多边形有且仅有两条共切线。
• 中垂线，可以作圆。等等。

通用Trick

曼哈顿距离，切比雪夫距离

• 两种距离可以通过旋转坐标系变换
• 对于一类 需要枚举坐标系中的点，可以通过切比雪夫距离变换。从而 两个维度无关 可以分别解决

倍增 / 二分

• 在一类可合并的二分处理中，换成 倍增 很可能得到更好的复杂度
• 一个例子：每次check的代价为二分出的长度。如果换成倍增，先1,2,4..找到第一个超出的，再逐步减小尝试增加，可优化一个$n$。
• 减少 二分次数 的一个小trick，随机一个排列的前缀最值个数是$O(\log n)$，于是check一下已有的最值，否则再二分。

异或的性质

Gym102114I

• 异或具有一些良好的性质 $S=\{0,1,2,\cdots,2^k-1\}$ 异或上任意一个 $t\in S$ 都是一个自己到自己的一一映射，且对于不同的 $t \in S$ 映射到的东西都是不同的。
• 于是一些异或类的统计问题可以考虑这个性质。

Dilworth定理和一个推广

Gym102114F

• 用来描述偏序集宽度的一个东西。
• 考虑集合幂集的偏序，有个定理叫Sperner's theorem。选择幂集的一个子集使得这些集合不存在包含关系。
• 推广可以给出本问题的答案：选择满足所有坐标之和等于$M=\sum (p+1)/2$ 的位置即可达到最大的数量。（所有以$(0,0,..,0)$为做下角的超立方体都构成集合）
• wiki上的一个有趣证明：
  

  令 $n=|U|,A \subset U = 2^X$，考虑 $X$ 中所有元素的排列，可以建立一个到 $S \in A$ 的映射（唯一一个前缀构成 $S$，否则$A$就是不合法的）
  而显然 （$a_k$就是$A$中大小为$k$的集合个数）
  于是就有 也就是 （LYM不等式）
  
  $$|A| = \sum a_k \le \binom n {n/2}$$

利用已有条件缩小范围

• 就像在这里给出的拓扑序限制，能够通过扫描将每个人的可能范围缩小。
• 进而保证了 $L_u<L_v<R_u<R_v$ 使得贪心策略能符合拓扑序的要求。

想题策略

• 看到题目，联想对应的关键字，套用已有的知识。建立一个映射表
• 除了易证明的结论，千万不要期望自己能从以前从未 接触/学习/研究 过的方向入手解决问题，有可能成功了，但是代价也是极大的。

• 全场AC题首先考虑，争取AC；不可做/码量极大的题果断暴力；用于区分的中档题先暴力再尝试用已有知识解决。

• 一般化

• 特殊化，考虑 极大、极小 的元素
• 算两次
• 容斥（边DP边容斥的模型，降低思维难度）