杂技篇【长期更新】

1.在O(n)时间内处理出一个字符串的所有循环字符串的hash值：将字符串倍长，然后通过取模运算实现

　　for(int j=0;j<=(n<<1)-1;j++) f[j+1]=f[j]*base+s[j%n]-'a'+1;

2.一个图是不是二分图的充要条件为是不是含有奇环。

3.如果将一个n个点的树染色保证任意直接相连的两个点颜色不同，那么可以保证颜色种类最少值至多有logn个。

4.有些建图题，比如网络流啊，图论啥的，本来一条边所代表的含义有（一万字），然后代价（unsigned ll），我们可以将边拆开，拆成一些简单的边，满足简单的边聚合起来仍然保留着复杂边的含义，而有时简单的边往往会使复杂度随之降下来。   bzoj-2259

5.如果你发现有的题，其实dp方程很简单，但是发现自己的转移方程需要儿子们枚举一下子集啥的..这时思考一下多叉树转二叉树可能有奇效 bzoj-1812

6.对于一个dp方程或者什么推导的时候遇到的式子，如果遇到了绝对值，我们一般有两种做法：1.两侧平方。2.(bzoj2131)拆开分两个式子讨论即可。

7.求lis的时候可以二分达到$nlogn$，不用非要$n^2$。

8.图论题中，我们发现这样的情景：每一个点有一个种类，每个种类又多个点。同个种类的点几乎是一样的，然后答案是依据点与点之间的路径，我们考虑多源bfs

9.如果一个题直接处理极其复杂，我们考虑拟对象

10.静态二维数点我们可以把所有点排序然后扔到一个树状数组里。

11.当每个点的信息可能有时间戳小于它的影响，也有大于它的影响。而且时间戳最靠前的元素我们非常容易处理，这个时候我们可以考虑双向链表。

12.求一个序列的满足条件子序列个数，即等于第二个序列，我们考虑逆向dp。

13.如果碰见一个问题根本不会处理，可以从三种方法作为切入点：从暴力下手寻找优化；从拟对象下手逐渐扩展；从数据范围下手缩小考虑范围。

网络流篇

最大流：

如果碰见针对一个对象的条件有多个，即某单个对象有多个不包含的约束条件，我们考虑拆点。

建图的时候如果碰见了很大的问题可以试试将抽象的东西划成点。

对于点的限制通常变成把点拆开，并将其之间连边从而转化成边的限制。

最大流的多条路是互不包含的。

有一种建图方式是怎么暴力怎么来，然后把多余的点删掉。

如果发现有这样的情况：$i$的出边有多个。我们要求它最多只能选择一条出边但是它的出边权值大于1。即可能存在分成两条边的情况。

　　这个时候我们发现如果我们的边的容量是0或1而且进来的流量最大是1的话就可以了。所以考虑模型的转化。

无向图有向图的问题开始有一个特别有效的办法就是先把判定肯定没有用的点直接删掉。

最大流问题常常和二分一起搭配使用。也就是说最大流很多时候作为一个判定手段。

最小割：

关于最小割其实应用的比最大流还要更广泛因为其简单理解。

最小割有一个非常重要的性质就是：求完最小割之后一个点不是和S连通就是和T连通。

它有几个比较常见的模型：

第一个就是地图题的时候相邻的方格如果怎么怎么滴，比如说如果相邻的方格如果都选A或者都选B有收益啊，或者有代价啊什么的。

我们就黑白染色然后白点反转源汇，这是一个非常常见的套路。

第二个的话是如果几个点同时满足一个相同的条件可能有贡献啊有代价啊，我们用最大权闭合图的想法，新建出来一个点表示这个集合，然后向这些点连inf的容量即可。

还有一些比如说删掉的点个数什么的就是拆点然后求最小割。

说一下最小割树的事：

　　最小割树就是求出一棵树，满足任意两个点在树上的路径最小值为原图中他俩的最小割。

　　这东西还是很有用的，求法是分治。任选两点跑一边最小割，两点之间的边权就是它（最小割的大小），然后把S集和T集分开，分治即可。

还有一些东西比如说一个点选另一个点不许选的话就在他们俩之间连一条inf的边。