重要公式
矩阵树
无向图
矩阵形式：
$A(i,i)=\deg(i)$，$A(i,j)=-\operatorname {cnt}(i,j)\text{（i 到 j 的边权/重边数量）}$
有向图
矩阵形式：
- 内向树：$A_{out}(i,i)=\deg_{out}(i)$，$A(i,j)=-\operatorname {cnt}(i,j)\text{（i 到 j 的边权/重边数量）}$
- 外向树：$A_{in}(i,i)=\deg_{in}(i)$，$A(i,j)=-\operatorname {cnt}(i,j)\text{（i 到 j 的边权/重边数量）}$
以 $i$ 为根的生成树数量为 $A$ 删去第 i 行以及第 i 列，之后求行列式。
行列式
定义式： \(\operatorname{det}(A)=\sum_{排列 P} (-1)^\text{P 中逆序对数}\prod_{i=1}^{n} a_{i, P(i)}\)
- 交换两行，结果取反
- 某行乘 k，结果乘 k
- 某行减去另一行乘一个系数，结果不变，直观理解：
trick
dp
- dp 提前算贡献
- 分阶段 dp（寿司晚宴&皮配）
- 时光倒流（常用于从环、序列上删数，且过程与所删数当前的前驱、后继相关的时候，或者贪心的候选集合递减（蔬菜））
- 消消乐 dp
- 子树合并 dp 复杂度
- dp 变为 dag 路径计数（然后可以搞一些操作，比如在反图上跑）
图论/网络流
- 模拟最大流转模拟最小割
- 切糕模型
- i 行 j 列转化为 i 行向 j 列连边。
- prim 最小生成树
- 在生成树上构造。
- 将完全图分为两个点集，求 $A团内边权和-B团内点权和$ 等价于 A 中所有点到其他所有点的距离和，减去 B 中所有点到其他所有点的距离和。
计数
- 点减边容斥。求连通块个数转化为求包含每个点连通块个数-包含每个边连通块个数
- 利用 Lucas 定理， $\binom{x}{y} \pmod{2} =[y\subset x]$
- 把统计某个东西转化为统计图上的边
- 求不同颜色序列数的一些技巧：
- Min-Max 容斥
- 带组合数的求和，比如求 $f_i=\sum_{j=0}^n a_j{j\choose i}$，可以拆成 $f_i=\frac{1}{i!} \sum_{j=0}^n a_j j!\cdot \frac{1}{(j-i)!}$ 可以 fft 快速求。
奇怪操作/一些找规律
- 找不变量（交换差分，逆序对个数奇偶性….）
- 按余数分类（定长区间异或 1）
- 棋盘异或行列之和的奇偶数
- 一个01序列，可以对其进行若干次奇怪操作（包含异或运算），最终要变成另一个序列，考虑先算出每个位置的操作奇偶性，然后再考虑构造1操作顺序
- 对一个0/1序列多次进行某种操作——尝试对每个0/1段或者0/1交错段单独考虑
- 图上若有 i->j, j->k 则加边 k->i ，求边数：手玩，发现图可以分成三个集合 A,B,C，所有A中点往B连，B向C，C向A
- N种卡牌，每次取k张颜色不同的，能恰好取完的充要条件是卡牌数最多的不超过总数的 $\frac{1}{k}$.
最优化
- n 选 k 使得和最大，n 很大，k 很小，考虑排除没有可能的方案（CF1572D）
- 取关键点（字符串循环节/答案对应的长度不超过 $B$，并支持 $n^2$ 计算，则可取若干关键区间计算 $[1,2B],[B,3B],[2B,4B]\cdots$）
- 不带删除的合并（比如有n个bitset,要求其中每连续k个的交集）可以隔k个求一个关键点，然后求前后缀交。这样每k个只需要再求一次交集即可合并。
- 比如说，求满足某个序关系的最小的点对，可以考虑是否有少数支配对，用类似单调栈的思想解决，例子：
- https://codeforces.com/gym/104076/problem/L（在树上，经典套路！）
数据结构
- 二进制分组斜率优化（当斜率不递增时，可以分别开若干个大小为 $2^0,2^1,2^2\cdots$ 的单调栈，加的时候先在最小的里面加，一旦大小撑爆了就跟下一个单调栈合并）
- 线段树 tag 不会合并？考虑变成矩阵乘法。（可以维护历史和）
- 如下的序列递推 $a_i=\max(b_i,a_i-1+c_i)$ 是可以维护的，只需要维护这段区间中顶过上界的答案和没有顶过上界的答案。
- 环上均分纸牌：首先假定两堆纸牌之间经过了x个纸牌，则其他堆之间经过的纸牌数都确定了，可以表示为$|x+c_i|$加起来是一个单谷函数，二分即可
- 维护前缀max,支持前缀+正数，后缀append元素，可以用并查集维护前缀max的连续段，发现只会合并，不会分裂，$O(\alpha(n))$ 实现。
- 两个凸函数，+max 卷积可以维护差分数组，然后启发式合并。
优雅暴力/一些思想
- 问题转化成实时维护一个集合，并判断集合是否与某个目标集合相等，然后就可以哈希。
- 不仅有二进制分组，还可以随机分组，比如随机分k组就可以解决k个不同点
- 支持交换相邻元素，将数组排序，操作次数为逆序对数
- 通过邻项交换实现的任意两项交换用的交换次数均为奇数，根据这个结论，置换环长度-1之和与上述答案的奇偶性相同。
- 若二叉树上的值满足 $f(u)=2\min(f(ls),f(rs))$ 则 $\sum f(i)=O(n\log n)$ 如果这个f是某个集合的大小，那么不用启发式合并就能直接维护。
- 找本质不同的 xxx 数量，考虑能否给每个等价类找一个代表元
- 例：agc008_f 求树上的不同的 $B(v,l)$ 集合数量，可以找到若干个等价类，每个类由最小的 $s\, \mathrm{s.t.} B(v,l) =S$ 代表。
我的常犯错误
做题策略（惨痛教训）
- 开始把题全看一遍（15 min 左右）
- 开始想题前手玩样例（5 min 以内可以玩的话）
- 除非分数有保障，想题超过 30 min 考虑换换，不要有心理负担，暴力也能搞好多分
- 思路较复杂，且不好调的题，重新回忆下算法，不一定是写错了，可能是假了。不要一心认为某nb做法是对的，其他做法是假的。
重大错误
2021省选
\[\large{\text{我 tm {\color{purple}RE} 了！}}\]- 爆搜不要瞎加剪枝，引起不必要的 RE，导致 60+分 -> 0分
- 暴力拼起来的题全打挂
- 想出算法开始打，打完发现算法假，灵机一动新想法，又写了个假算法。
- 诸如两个数的和，这类边界特判要特别注意，最大值是原来两倍
2020NOIP
- 求 lcm 注意要 先除后乘
NOI 笔试易错
RAM=Random Access Memory，ROM=Read-Only Memory分不清- Lazarus 是 Pascal IDE，GUIDE 和 Anjuta（AG）是 C++ IDE
（然而我用 vim）
STL
multimap的erase(x)会把所有值等于 x 的删掉
细节
- 建图把无向图建成有向图
- 组合数计算函数忘记特判
x>y，x,y<0，开 O2 后 UB 爆零了。。 - 预处理阶乘/扫描线分开存储修改查询时，数组忘 开两倍
数据结构
- 线段树着急写错左右儿子
- 值域线段树
pushdown忘记把空节点新建出来
fhqTreap 专栏
pushdown时要 判空节点- 按
rank分裂时应该判断sz[ls]+1>=rank push_up时sz[p]=sz[ls]+sz[rs]+1忘记写+1- 把
split复制粘贴改成splitrk忘记改递归的函数名 split(rt,b,c)之后应该split(b,a,b)，写成split(rt,a,b)
算法
- 求树的直径时忘记把父亲的跟儿子取 max
- 线段树合并忘记 判断叶子节点
- 点分治忘记考虑 分治中心的贡献
- 扫描线先改后查
- 莫队排序写挂
- AC 自动机，在把 fail 树上子树加起来的时候，必须显式建图，倒着遍历所有节点，并加到自己的 father 上不对
- dinic 中 bfs 的 queue 忘记清零
- 写线性基形式的高斯消元时，消元这一步：
inline void eli(double *x,double *y,int ind){
if(is0(x[ind]))return;
double rate=x[ind]/y[ind];
for(int i=0;i<=ind;i++)//第四行
x[i]-=y[i]*rate;
}
第 4 行不可以循环到 n，否则会被卡精度。
其他
- 函数内开大数组 RE 了
- 对拍时要把
std中的小数据暴力注释掉 - 编译不会开 O2 的命令
g++ -O2 -Wall *.cpp -o *
Tarjan 专栏
- 有向图建成无向图
- 缩完点后建图把原来的点和缩成的点搞混。。。
instack数组应该在弹栈时置零
判断条件
- 强连通：
dfn[p]==low[p]，弹到p。 - 点双：
low[nx]==dfn[p]，则如果p不是搜索树的根，或者p在搜索树上有多个儿子，p为割点，弹栈直到nx（nx要保留，因为割点可能在多个点双中） - 边双：
dfn[p]==low[p]，弹到p，当前边为桥。
总是忘记的
- sa 中求 h 数组时：
h[rk[i]]>=h[rk[i-1]]-1 - 2-SAT 中最终应该选择编号小的强连通分量
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: