Tips
-
对于\(a_i\le n\),可以连边\((i,a_i)\),然后就变成一棵内向基环树森林
-
一种图论题目可以把边挂在点上(可以挂一半,也可以挂全部),当然也可以把点权挂在边上
-
要求图的度都为奇数,等价于要求图的连通块大小都为偶数
证明:
必要性:反证,考虑若有一个连通块大小奇数,那么图的总度数为奇数,不成立,证毕
充分性:若有把一个偶数大小连通块变成树,一个点若有奇数个儿子,就断父亲的边,否则就上传,可以发现上传的子树大小为奇数,独立的子树大小为偶数,所以到根节点的度一定为奇数,证毕
-
动态判断图是否为二分图,把每个点拆成两个\(x_1,x_2\),然后用可撤回并查集交叉连边,若\(x_1,x_2\)联通,则不是二分图
-
全局+整数,可以离线下来,变成全局+非负数
-
a[++cnt]=b[cnt]=x
要慎用,linux下好像等价于b[cnt]=x,a[++cnt]=x
,但在windows下是a[++cnt]=x,b[cnt]=x
- 补充:
a[x]=a[++x]
或者a[x]=a[--x]
也要慎用(其实是不能用,2024.1.25又因为它调了1h)
- 补充:
-
如链覆盖的网络流模型,如果有类似但无法处理的问题,可以考虑转化为费用流(如k条互不相交的链最多覆盖几个点)
-
dp中出现了偏序关系可以考虑分治,先处理左半边,然后把左半边贡献在右半边,在处理右半边
-
当dp出现枚举子集\(O(3^n)\)时,用sosdp优化成\(n2^n\),巧妙利用高维前缀和、差分
-
最大流转最小割:ABC332G,芙蓉王(源)
-
\(max(a_i,a_{i+1},a_{i+2})-min(a_i,a_{i+1},a_{i+2})\)可以转化为\(b_i=a_i-a_{i+1},max(|b_i|,|b_{i+1}|,|b_i+b_{i+1}|)\)
-
树上有很多问题,如背包...,跟子树大小(或叶子节点个数)有关,而且子树大小相等时贡献一样时,可以发现最多只有 \(\sqrt n\) 种
-
排列的容斥:
\[(|S|=n的方案数)-(|S|=n-1的方案数)+(|S|=n-2的方案数)... \] - \[\sum_{i=1}^n \frac 1i=\ln n+C\\ \sum_{i=1}^n \frac 1{i^2}=\frac{\pi^2}6 \]
-
如同统计答案和,方案数的dp,我们常把它相乘进行转移,计算期望和概率也是这个原理
-
有向强连通图中最小平均权值回路:一种简单做法,01分数规划+SPFA判负环