暴力就完事辽_-`’辽

刘汝佳2005OI讲稿

任何问题都有涉及的范围（状态空间），求解问题就是在这个状态空间里遍历与映射。遍历顺序、遍历中的决策方法、状态空间中各种状态的之间的映射方式。枚举、模拟是按照问题直接表述形式对状态空间最朴素的遍历；搜索是带有一定选择性、决策性的遍历；贪心是在每步决策时采用局部最优策略的遍历；动态规划是基于全局考量的分阶段、按维度、无重复遍历；二分、倍增、排序可以对状态空间进行划分、等价、代表、拼接等手段，直接降低遍历时需要面对的时空规模。

(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧(๑•̀ㅂ•́)و✧

朴素遍历->空间需要优化：用时间换空间/有些不用存；
->时间要优化-> 找规律->离线处理、数据结构（数据结构的设计思路来源于各种基本算法思想（优化的过程），分为线性数据结构和树形数据结构，思考数据结构是如何优化的）

状态空间（实际问题的各种可能情况构成的集合）就是，长的和解形式一样但是内容不一样的东西，先确定解的形式和内容，依此考虑状态空间。例如：任意时刻的局面就是状态，任意时刻哪些点没被经过哪些点已经被经过，状态里要有全局的轮廓（已经经过的点），也要有当前的位置（现在在哪个点）
表示系统在现在、过去、未来时刻的状况，由一组变量描述
a. 先确定所有的状态（状态空间，如果找不见考虑模拟过程）（有时候要分类讨论、以（扫描的）当前状态为视角），想到朴素的枚举遍历（就是在这个解空间里找到我需要的解），然后从答案（解）出发，找我需要的信息去维护；如果题目描述的解不好处理就换一个角度转化一下题目或者建立模型去思考（怎么转化这个也要积累），如：如果数据差特别大，选择数据小的这一元素进行枚举
b. 二维的会枚举一维，另一维优化枚举
c. 优化就是：跳过或剪去我已经知道的不是解的情况/用数据结构集中有用的信息和我需要的信息（了解数据结构可以维护哪类信息、怎么维护、怎么跳过冗余状态的）/找到有冗余、拖慢计算速度的状态处理掉/重复的记下来下次用
算法和数据结构通过划分、归纳、提取、抽象提高遍历的效率，如何划分归纳？考虑题目的性质，子问题，平凡情况，找到内在规律，转化为与原问题等价的问题
d. 做题时逐步优化的过程就是经验要积累下来
e. 有些是自己想不到的优化方式，一般采用已有的算法求解
f. 各种模型之间的简化、拓展、联系
现在问题就是想不到除了朴素地遍历，还能用什么优化方法遍历
所以跑来积累一下ヽ(✿ﾟ▽ﾟ)ノ
……有时候连状态都枚举不出来，状态是啥都不知道……
g. 如果找不出状态则往模拟上面考虑
h. 正向不易考虑，从逆向考虑等价的情况，如删去变为选择、uva11925（从1234……变为给定的是1对多的映射关系，但是从给定的变成1234……是1对1，比较容易，两种操作是为了将大的换到后面）

函数图像绘制工具
质数发生器和校验器

思路方向（自己构造例子思考，不要完全沿用样例）

从枚举的角度出发，思考要枚举什么，什么顺序枚举，以枚举的顺序这种动态的开点思想
0. 子问题和平凡的情况是两回事，平凡的情况是原问题的一种情况（状态），子问题不是原问题，而是原问题的化简，缩小规模后的问题

1. 遇到函数，要考虑他的性质，如单调性，极值等等，将几个x的取值放在一起考虑，不会就打表
2. n个数（比较小）选不选的问题，可以状压位运算，用01二进制表示，状压有两个数一个是参照，另一个是题目表示的数
3. 二分图行列匹配：行和列不互相影响就可以分开考虑
4. n很小的话（如<=20），可以选择状态压缩：用二进制表示每一种状态（有序无序均可），（尤其是几个元素选还是不选）或是一个集合（没有顺序的）（poj1143）等
5. 逆向考虑，如删除->添加；从特殊点枚举得到非特殊点->非特殊点搜索到特殊点；……
6. 要求很小的比如三个点，两个元素这种且n^2不T，就可以直接枚举（T可以换二分、倍增一类优化）；可以枚举边则代替了两个点
7. 环状序列可以考虑断成线性的，或考虑正常线性和环的首尾相接处
8. 取反操作（建反图，边取反等等（继续积累这方面））可以将求最小转化为求最大
9. 状态空间是两个变量的，枚举一个变量，优化另一个的枚举，比如矩形最大面积单调栈
10. 用0，1来表示该位有没有，统计1的个数可转化为面积……
11. 二维地图一般以模拟坐标、搜索、图论各算法等方向考虑
12. 用堆求最小值->采用线性结构（如栈）保存每个时刻的最小值
13. 大的问题不能解，就分解成小问题，如快速幂思想，利用二进制分解为一小段一小段
14. 把对区间的操作（该区间每个数都要操作）转化为对左右两个端点的操作，通过前缀和得到原问题的解。（要操作的影响从左端点+1开始，从右端点结束 poj3263）
15. 回溯：一个问题在小问题即边界处答案已知，且拓展步骤相似，则用递归的方法转移至下一个小问题，还原现场：求解子问题失败，则求解它时的影响都要消除，即回到原来的状态。（**回溯和dfs是两码事！！！**递归是一种手段、方式，dfs用递归的方式遍历，回溯用递归的方式求解，但回溯！=dfs）
16. 注意思考行、列是否可以分开
17. 区间贪心，一般是端点排序；有两个维度的贪心，可以考虑差值，思考的时候取两个物品比较看看什么样的策略正确
18. 所有情况大的小的都要考虑！！！全面分类讨论！！！
19. 将一种关系看成一条有向/无向边建立图模型思考
20. 一个01串，可以往二进制上考虑，如果交换、反转……可以考虑图建模、贪心，思考性质
21. 有的可以枚举一行，然后后面的所有行就确定了uva11464,一般n很小，对每一个位置，上下左右都有关系
22. 如果答案只有一个，但是5备选答案有特别多，就选择二分答案，在判定的时候也可以通过二分的手段（按次数二分1要明确最后选的是 l 还是 r ，不确定就都输出看看）
23. 最小表示思想poj 1509：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它一般们都用于按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可。一般用于字符串
24. 将环拆开成链，将1s复制两次：11ssS+=做为主串，则任何与1s循环同构的字符串至少都可以在S中出现一次，于是可以说S就是循环串1s的一般字符串形式
25. uva 1588 cut:其实是两个串的最大匹配长度即可，将另一个反向
26. 标准化（最小表示的思想），为元素标号，hash
27. 递推思想 如：约瑟夫环、UVALIVE 3029
28. 映射思想 字符串hash、二进制编号（uva 213）等，利用映射以后的值去遍历
29. 预处理思想：一次筛选，多次查找

int go(int p, int d, int step) {
    while(step--) {
        do {
            p = (p + d + n - 1) % n + 1;//p位置按方向d走一格，然后绕一圈到下一个位置，再加一
        } while(a[p] == 0);
    }
    return p;
}
1
2
3
4
5
6
7
8

30. 输入格式可以编写一个read函数 uva 548

小技巧

1. 取浮点数x最近的整数：(int)floor(x+0.5)
2. 异或和可以找出一堆数中唯一的那个数
3. 一堆数的gcd=x，则他们的线性组合可以到达x的倍数的点
4. 反转的问题，两个nm的矩阵，要反转成一样的，且只能反转22以上大小的矩阵的四个角，则遇到不同的就反转以该位置为左上角的2*2的矩阵，一直到最后判断不能反转的情况是否合法 cf 1119C
5. 矩阵/二维的东西有时候考虑是不是可以单独考虑行列，如uva11992,
6. 循环i内部一定要判断i<n这种越界
7. %3d %03d 前者是 空格空格1，后者是001；

快速枚举

状态：“多少种合法位置方案”->具体合法方案就是状态
充分考虑题目里的已知性质，对于答案有什么影响，是否可以排除掉某些状态
状态是用多个维度去描述一种情况，状态的设计一般从解的结构形式和内容（维度的内涵）考虑，更像描述一种存放题目中各个具体元素的容器（poj 2279）
不想一个一个的枚举，要优化速度可以：二分、倍增、预处理、排序、

1. 二分：单调性，从某位置以后/前全都不是
2. 倍增：
3. 统计个数（预处理）：如果枚举是为了统计某个东西的个数，可以考虑预处理出来一些别的值使得要统计的个数可以通过计算这些别的值算出来，O（1）得到答案（cf156B），预处理这些值可以O（n）扫一遍，它属于哪个就放在哪个数组里
4. 排序：如果某些状态一定是不用考虑的，则按照他们的性质排序，使得他们放在后面省去考虑
5. 利用问题的可划分性、子问题之间的相似性进行归纳
6. 利用问题的子问题之间的相似性
7. 枚举起来状态特别多的，考虑dp 或者预处理，dp也是利用子问题相似归纳，利用已经解决的子问题
8. 预处理：避免一个一个地去统计，而是用计算值的方式得出答案。处理什么呢：如果有重复的东西，看什么时候出现重复，从长度、个数等去考虑出现重复的情况，一般如果数值特别大，就考虑预处理一些东西
9. 如果枚举位置，可以维护前缀和、后缀和O（1）查询答案。例如：gcd，如果不能质因数分解，也无法预处理（n^2），则可以用前缀和、后缀和维护gcd
10. 有时候可以以题目给的形式和结构考虑枚举顺序和方案
11. 如果有重复的计算，用递推、维护信息的方式来利用之前的信息，不要每次都计算
12. 一般都要按顺序去枚举考虑、所以点按极角的顺序，最左下的点开始；线等以时间顺序；边按矩形顺序……

特殊样例 （全面地考虑状态空间）

1. n=0、1等边界的情况
2. 要考虑没有答案的情况，是0还是别的
3. 多组样例一定要重置数组，清空空间
4. 负数不能做下标，所以要存a[-x]，否则会re

前（后）缀和

1. 一维前缀和（某段区间内找某个条件）
   a.给你一个长度不超过1000000 (1e6 ) 的一个整数，让你将其分成两个段（不包含前导0），使得第一个数是a的倍数，第二个数是b的倍数。(a,b 1e8) 思路：前缀%a，后缀%b，枚举每个点如果前缀模、后缀模均为0，则满足题意
   b.将数组分三份，使每段和相等。思路：双指针，cnt指sum/3和ans（sum/3）<<1,cnt++，ans+=cnt 统计前后对
2. 二维前缀和
   a.求二维坐标（平面）某长（正）方形区域内的值的和、最值（1e3）
   b.将一矩阵划分为k*k的正方形，如果没法分，那么就在它的最右边以及最下边进行补充，补充的一行或一列均为0。让每个方块里均为0/1最少要变换多少次（1e3）
   c.一个矩阵找a * b的长方形使得其中1的个数尽量少（50）（可以暴力）
3. 对区间操作转化为对端点操作，前缀和累计答案

归并排序

一般求逆序对时使用。什么情况是求逆序对呢？
1、冒泡排序的次数即为逆序对个数
2、一个数组置换、交叉（即不同的排列）后，可能考虑逆序对

尺取（也是因为单调性）

针对区间的问题：1 连续的一段 2 对该段有条件限制 即：需要在给的一组数据中找到不大于某一个上限的“最优连续子序列”
思路：l=0，r=1；l每右移一个，就去找r的合法位置 poj 3061

 for(int l=1,r=0,now=0;l<=n;){
      while(now<k&&r<n) now+=a[++r];//r<n,若是r<=n,则r会越界
      if(now<k) break;
      ans=min(ans,r-l+1);
      now-=a[l++];
 }
  if(ans==inf) ans=0;
1
2
3
4
5
6
7

二分(一堆数中找一个数 单调数组 按循环64次二分，不会死循环)！！二分之前一定先排序！！

状态空间特别大，答案范围也特别大的时候就要考虑二分
注意答案范围：l=0，r=inf
(double 用eps，精度可能会炸，int 用 l<r )

1. 单调数列求最大值（lf），一般答案的范围不确定
   a.给定一个正整数数列A , 求一个平均数（前缀和，和一定是递增的）最大,长度不小于 L 的字段。(平均数常见处理，每个数都 - 平均数) 思路：是否存在一个长度不小于L的字段 ,平均数不小于二分的值 -> 把数列解中 的每个数都减去二分的值 -> 判定" 是否存在一个长度不小于 L 的子段 ,子段和非负"

bool judge(double x){
    rep(i,1,n+1) tmp[i]=a[i]-x;
    rep(i,1,n+1) sum[i]=sum[i-1]+tmp[i];
    double ans=-1e10;
    double mival=1e10;
    rep(i,f,n+1){
        mival=min(mival,sum[i-f]);//不用两层循环，左端一直选最小值，右端一直选最大值即可
        ans=max(ans,sum[i]-mival);
    }
    if(ans>=0) return true;
    else return false;
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 单调数列求最小值 （rt）
   aa. cf 51C 区间包含范围，奶牛放栅栏这种，贪心策略都是维护一个范围，如果该范围不够，就从下一个点开始维护新范围，以保证最小
   a.平面上给n个点，问能将所有点包含进去且与x轴相切的圆最小半径是多少。思路：按循环次数二分答案：相切：圆心在y=r的线上；点在圆内：因为不确定圆心的x坐标，所以只能用与所有点相对位置，对于每个点(xi,yi)(xi​,yi​)来说，以(xi,yi)(xi​,yi​)为圆心，R为半径作一个圆CiCi​，那么CiCi​截直线y=R的那条线段，圆心处在这条线段上才是符合条件的（将包含所有点转化为线段交集）。因此将所有这样的线段找出来看有没有交集。

bool judge(double r){
    double xl=-inf,xr=inf;
    rep(i,0,n){
        double d=fabs(p[i].y-r);
        if(d>r) return false;
        double xxl,xxr;
        xxl=p[i].x-sqrt(r-d)*sqrt(r+d);
        xxr=p[i].x+sqrt(r-d)*sqrt(r+d);//先乘再sqrt会炸精度，sqrt数越大精度越差，所以先开方再乘
        if(xr<xxl||xxr<xl)
            return false;
        xl=max(xl,xxl);
        xr=min(xr,xxr);
    }
    return true;
}

	double l=0.0,r=10000000000000000;
// 按循环次数二分
    rep(i,0,100){
        double mid=(l+r)/2.0;
        if(judge(mid)){
            r=mid;
        }
        else
            l=mid;
    }
    printf("%.6f\n",r);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3. 优化一个一个的暴力，加快寻找速度
   a.总共有n台电脑，Moath找一台电脑需要x分钟，Saif找一台电脑需要y分钟，问你找n台电脑需要多少分钟 。思路：二分答案
   b.一个字符串，字符串中不是’a’就是’b’,可以修改最多k个位置,问能够得到的最长相同字符的序列。思路：求a、b的前缀和，枚举左端点，二分右端点，judge(这一段的值用前缀和表示，是否<=k )
   c.找二元组。例求数组中和=k的数对。（一个确定了另一个也确定了）

三分（一般三次函数）

1. 枚举超时，根据答案、各状态性质去优化（hdu 4355） 枚举每个点作为基准点，发现左边开始ans逐渐减小到极值，从极值点到右ans逐渐增大，

树

1. 树的直径（2次dfs）
   a.给一棵树，求任意走k个点的最短路。
   b.给一棵树，已知有人一开始在C点，要到达A点和B点（那个近先去哪）。求最坏的情况所需的时间。思路：求max(dis[A][B]+min(dis[C][A],dis[C][B]))，要dis[A][B]最大，求树的直径；min(dis[C][A],dis[C][B])dfs暴力（暂时） https://blog.csdn.net/xuxiayang/article/details/84992184
2. 树的遍历
   2.1 点染色
   a.给n个节点染色（点有颜色），第i个点染成c[i],能否删去一个节点使得剩下所有子树只包含一种颜色。
   b.给一棵树n个点，最多能加多少边使它仍是二分图。思路：dfs二分图染色，一共二分图的边是num1*num2(2号颜色的点个数)，还能加的边是 一共的 -（n-1）
   2.2 树上路径(1e2,大数据一般用树链剖分、树上dp)
   a…n点m边无向图，每条边颜色是c[i]（边有颜色）,q次询问，有几条能u到v(颜色相同)的路径。（可能有重边（重边上的信息用三维数组记下来 color[u][v][cnt]、color[y][x][cnt]））思路：按每种颜色对u、v的路径暴力找路径是否存在

bool dfs(int u,int vv,int color1)
{
    if(!vis[u])
    {
        vis[u] = 1;
        if(u == vv)
            return true;
        for(int i = 0 ; i < G[u].size(); i++)
        {
            int v = G[u][i];
            for(int j = 1 ; j <= vis1[u][v]; j++)//对所有重边都讨论
            {
                if(color[u][v][j] == color1)
                {
                    if( dfs(v, vv, color1))
                        return true;
                }
            }
        }
    }
    return false ;
}

for(int  i= 1; i <= m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            G[a].push_back(b);
            G[b].push_back(a);
            vis1[a][b]++;
            vis1[b][a]++;
            color[a][b][vis1[a][b]] = c;
            color[b][a][vis1[b][a]] = c;
        }
        scanf("%d", &k);
        int v1, v2;
        while(k--)
        {
            sum = 0;
            scanf("%d%d", &v1, &v2);
            for(int i = 1; i <= m; i++)
            {
                memset(vis, 0, sizeof(vis));
                if(dfs(v1, v2, i))
                {
                    sum++;
                }
            }
            printf("%d\n", sum);
        }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

2.3 树的大小
a.给你一棵N个结点的树，问最多剪掉多少条边之后，剩下的连通分量的size都为偶数，如果一条也没法剪掉输出-1。思路：按奇偶讨论，什么情况-1？奇数；否则就遇到偶数的子树就剪掉。dfs求树的大小。

int dfs(int x) {
    int son=0; //计算子节点个数
    vis[x]=1;
    for(int i=0; i<v[x].size(); ++i) {
        if(!vis[v[x][i]]) {
            son+=dfs(v[x][i]); //对每个没搜过的节点搜，记录子树顶点。 }
        }
        if((son+1)%2==0)
            ans++; //偶数点的就++，因为整棵树还要加上根节点1个，所以son要+1。
        return son+1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

并查集（如果能用祖先代表的，就不用记并查集里有谁）

有合并、优化两个功能，用根代表整个集合，遍历森林就是遍历每个根，这样不用遍历集合里有什么所以降低了复杂度。因此时刻都想着根，用根表示集合和集合的各种信息。

1. 普通并查集（维护无向图中点的连通性）
   1.1 维护点之间的连通性（点可以是抽象的，如数组中的数、位置等等）
   1.2 判有没有环、统计环（集合）的大小
2. 种类并查集
3. 二维并查集（加上对边的维护）
   3.1 维护无向图点之间路径的信息
   a…n点m边无向图，每条边颜色是c[i]（边有颜色）,q次询问，有几条能u到v(颜色相同)的路径（可能有重边)。思路：虽然是路径但没有问先后关系（路有几条），所以用集合表示也可以。二维并查集<=>建m个颜色的一维并查集，多了一维属性w

int f[200][200];
int getf(int v,int w)  //就是多了w，其他的都不变
{
    if(f[v][w]==v)
        return v;
    else
    {
        f[v][w]=getf(f[v][w],w);
        return f[v][w];
    }
}
void merge(int v,int u,int w)
{
    int t1=getf(v,w);
    int t2=getf(u,w);
    if(t1!=t2)
        f[t2][w]=t1;
}
//初始化的时候就相当于
for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                f[i][j]=i;
        int a,b,c,q,x,y;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            merge(a,b,c);
        }
        scanf("%d",&q);
        for(int i=1; i<=q; i++)
        {
            int ans=0;
            scanf("%d%d",&x,&y);
            for(int j=1; j<=m; j++)
            {
                int a=getf(x,j);
                int b=getf(y,j);
                if(a==b)ans++;
            }
            printf("%d\n",ans);
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

3.2. 维护二维地图上的联通块（dfs也可）
一般二维地图还是采用搜索比较好。
5. 带权并查集（路径压缩时统计点到根的路径上的信息）
6. 维护传递关系（floyd）

图论（要先考虑：有向/无向、有无重边、有无环，然后从点的度数、点数和边数的关系等 这些性质出发考虑）

0. 判断图的形状：考虑点的度数、叶子结点开始、联通块个数、点数与边数的关系等等性质
   a. cf 103B （判断一个图是不是由>=3棵树构成，这些树的根在同一个环上。思路：仅有一个连通块，且边数==n才只有一个简单环）
   b. 求每个点到唯一环的距离 cf 131D

1. 传递关系 floyd更新传递关系里的花费最值 poj1125

2. 二分图匹配：关键是如何识别如何建图
   a. 完美匹配（最大匹配，匹配组数最多）匈牙利算法
   b. 最优匹配（匹配以后权值最右，不一定最大）km算法
   c. 最小点覆盖
   d. 最小边覆盖
   e. 最大独立集

3. dijsktra 及堆优化

4. 拓扑序 将一种关系看成是一条有向/无向边

5. 欧拉路 dfs实现，找奇数度的点 欧拉路的条件
   构造欧拉回路：对每一个连通图来说，如果有2k个度为奇数的节点，那+k-1条边可以使它成为欧拉回路；如果有2k+1个度为奇数的节点，那+k-1条边可以使它成为欧拉路径。
   uva12118
   分析：当每条边仅经过一次时，路径最短。给出的边可能构成若干棵树。
   在一棵树中，奇点个数总为偶数，若一棵树的奇点个数为0，则这棵树可以构成欧拉回路，若不为0，则必有走不到的边（每条边仅经过一次，下同）。
   在一棵树中，设奇点个数为n，则走不到的边数为(n-2)/2 （n-2为除去起点和终点的奇点个数），这意味着，还需要走额外的(n-2)/2条边才能将这(n-2)/2条指定的但走不到的边走完。并且，这(n-2)/2条走不到的边是不共点的，这意味着，一棵树还是多棵树是无关紧要的。但是，如果有的树中奇点个数恰为0，没有走不到的边，此时这棵树成了孤立的了，要注意这种情况。（所以就给他加两个奇数点，让这个联通块也能和其他块连上） 代码里max(0,(ans-2)/2)是指如果有0个奇点则已经是欧拉回路不需要加边，特判n=0的情况

6. 拓扑排序（判环、处理信息冲突问题）
   拓扑排序处理信息不完整和冲突
   1.如果出现两个同时入度为0的，并且根是自己就是信息不完整。
   2.至于信息冲突的情况就是出现了环，这时候会发现查询入度为0的循环执行不下去了，也就是sum>0.

7. 邻接矩阵幂：A^m 所代表的意义就是从点与点之间走m步能够到达的方案总数

网络流

最大流最小割

//当前弧优化、多路增广
struct dinic {
    struct node {
        int to, nxt, w;
        void get(int a, int b, int c) {
            to = a, w = b, nxt = c;
        }
    } edge[maxm << 1];
    int s, t, dep[maxn];
    int head[maxn], tot;
    
    void init() {
        tot = 0;
        memset(head, -1, sizeof(head));
    }
    
    void addedge(int u, int v, int w) {
        edge[tot].get(v, w, head[u]), head[u] = tot++;
        edge[tot].get(u, 0, head[v]), head[v] = tot++;
    }
    int q[maxm];
    bool bfs() {
        int fr = 0, tail = 0;
        memset(dep, -1, sizeof(dep));
        dep[s] = 0;
        q[tail++] = s;
        while(fr < tail) {
            int u = q[fr++];
            for(int i = head[u]; ~i; i = edge[i].nxt) {
                int v = edge[i].to;
                if(dep[v] == -1 && edge[i].w) {
                    dep[v] = dep[u] + 1;
                    if(v == t) return 1;
                    q[tail++] = v;
                }
            }
        }
        return 0;
    }
    
    int dfs(int u, int fl) {
        int flow = 0;
        if(fl == 0 || u == t) return fl;
        for(int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if(dep[u] + 1 == dep[v] && edge[i].w) {
                int f = dfs(v, min(fl, edge[i].w));
                if(f > 0) {
                    edge[i].w -= f;
                    edge[i^1].w += f;
                    flow += f;
                    fl -= f;
                    if(!fl) break;
                }
            }
        }
        if(!fl) dep[u] = -1;
        return flow;
    }
    
    int dinic() {
        int flow = 0;
        while(bfs()) {
            flow += dfs(s, inf);
        }
        return flow;
    }
} di;


struct Dinic {
    static const int maxn = 1e6+5;
    static const int maxm = 4e6+5;

    struct Edge {
        int u, v, next, flow, cap;
    } edge[maxm];

    int head[maxn], level[maxn], cur[maxn], eg;

    void addedge(int u, int v, int cap) {
        edge[eg]={u,v,head[u],0,cap},head[u]=eg++;
        edge[eg]={v,u,head[v],0,  0},head[v]=eg++;
    }

    void init() {
        eg = 0;
        memset(head, -1, sizeof head);
    }

    bool makeLevel(int s, int t, int n) {
        for(int i = 0; i < n; i++) level[i] = 0, cur[i] = head[i];
        queue<int> q; q.push(s);
        level[s] = 1;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i = head[u]; ~i; i = edge[i].next) {
                Edge &e = edge[i];
                if(e.flow < e.cap && level[e.v] == 0) {
                    level[e.v] = level[u] + 1;
                    if(e.v == t) return 1;
                    q.push(e.v);
                }
            }
        }
        return 0;
    }

    int findpath(int s, int t, int limit = INT_MAX) {
        if(s == t || limit == 0) return limit;
        for(int i = cur[s]; ~i; i = edge[i].next) {
            cur[edge[i].u] = i;
            Edge &e = edge[i], &rev = edge[i^1];
            if(e.flow < e.cap && level[e.v] == level[s] + 1) {
                int flow = findpath(e.v, t, min(limit, e.cap - e.flow));
                if(flow > 0) {
                    e.flow += flow;
                    rev.flow -= flow;
                    return flow;
                }
            }
        }
        return 0;
    }

    int max_flow(int s, int t, int n) {
        int ans = 0;
        while(makeLevel(s, t, n)) {
            int flow;
            while((flow = findpath(s, t)) > 0) ans += flow;
        }
        return ans;
    }
} di;
int ans = di.max_flow(s, t, 点个数+10);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

搜索

1. 联通块
   1.1 联通块个数dfs标记
   1.2 联通块大小（int）dfs

回溯

之前是什么状态，回来的时候要一模一样的。

模拟

1. 等差数列/差是等差数列的数列（1，2，4，7，11……）模拟n每次减掉差，若最后是首项，则说明n在数组里，否则不在。
2. 如果一个问题是多方同时开始的，但模拟的时候要按轮数模拟，多人一组这样模拟

找规律(n特别大可能有规律)

1. 差分找规律
2. 斐波那契数列（矩阵快速幂）

dp

dp就是在减小问题规模，dfs（x）就是问题规模不是n了而是x的答案
图上的dp都用记忆化搜索！！！
记a1,a2,……为规模为1，2，……的问题的解，则动态规划是用a1,a2……ai-1去推导ai
贪心是用ai-1推导ai
概述：
解决多阶段决策（当前这个选不选）问题，即每个阶段都要做一个决策，全部的决策是一个决策序列，要你求一个最好的决策序列使得这个问题有最优解。
将待求解的问题分为若干个相互联系的子问题，只在第一次遇到的时候求解，然后将这个子问题的答案保存下来（记忆化），下次又遇到的时候直接拿过来用即可。
dp在选择的时候是从以前求出的若干个与本步骤相关的子问题中选最优的那个，加上这一步的值来构成这一步那个子问题的最优解。
具体想法：（记忆化搜索）

1. 分析问题的最优解，找出最优解的性质，并刻画其结构特征：
   问题最优解：目标
   最优解性质与结构特征：写方程式的基础
2. 递归的定义最优值：
   要求a的，就得求b的；要求b的，就得求c的……
   递归定义规定了是自底向上还是自顶向下，最后推出的要求的问题是最小的子问题，从该处往后推，递归顺序与问题性质决定了正推还是逆推
3. 找子问题：大量的重复子问题
4. 阶段->状态->决策
   ps：不一定最后一个就是答案，最长公共子序列最后一个是答案，因为越往后公共的子序列长度可能越长；但lis不是，最后一个不一定是最长的，要遍历一遍
5. 利用已经处理好的部分
6. 一个已知状态应该更新哪些后续状态/如何计算出一个状态
   a. 发现有重复用的数值就记下来，是dp思想
7. DAG图上的路径如果有起点终点，dp值就是结果（？？？），否则要在所有状态中找最值才是答案（？？？）
8. DAG图上问题一般定义为从结点i出发的（最长路径长度），容易推出方案
9. 一般dp[i]][j]表示的是从该状态出发的结果，“时刻i，在车站j 最少还需等待的时间”、“表示从结点i出发还需要凑到的面值”
   10.考虑会影响决策的东西，是二元组、一元组 ……这样的东西一般接近状态的定义

贪心

贪心主要就是在证明问题整体最优可以由局部最优推导出来。策略考虑当前这一步的策略的作用范围扩展到后续状态产生的影响
贪心法是每步选择局部最优解，然后一步一步向目标迈进。这个“目标”两字很关键，说明贪心法是目标导向的，每一步的方向一定是目标

1. 多线程互斥场景（线段交集） 被经过最多次数的点 poj1083
2. 区间贪心：（一般直接枚举会超时（1e4、5），又是求最值，可以用贪心）区间贪心的一个定理，选择不相交的区间：数轴上有n个开区间(ai, bi)。选择尽量多的区间，使得这些区间两两不相交，贪心策略是，一定是选bi小的
   排序以后可以跳过一些冗余的一定不是答案的状态，如何排就是要看如何排除这些答案。
   eg：51nod1091 线段重叠
   最朴素想法：枚举两条线，求交集最大值->发现枚举一条线 i 就行，另一条线如果对答案有贡献，只可能 i 的起点<=其起点<=i 的终点，所以排序后只在这段范围考虑就行->发现如果该线段被i 包含，则不用再枚举这条线作为 i ，因为它不可能再使答案变大了
3. 将要求的问题转化为数学表达式（如：max（an+b(n-1)+……）），从该方面考虑
4. 贪心的排序方式，可以假定一种，然后固定一端看按照该排序方式的另一端会不会有不满足条件的解。

数学

0. 1~n里x的倍数n/x个
1. 因子、质因子、因数分解等：质数筛
2. 欧拉函数（不是质因数）
   线性筛：https://www.cnblogs.com/gshdyjz/p/7678361.html

void getol()
{
    mm(isprim,0);
    phi[1]=0;
    int r=0;
    for(int i=2;i<maxn;i++)
    {
        if(!isprim[i])
        {
            prime[r++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<r&&i*prime[j]<maxn;j++)
        {
            isprim[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

大一点的数求欧拉函数值

ll phi(ll n){
    ll ans=n;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)//n是质数
        ans=ans/n*(n-1);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 乘法逆元 an(mod m) =1 则n的乘法逆元是a
   费马小定理求逆元：若a,p互质,因为aap-2≡1(mod p)且a*x≡1(mod p),则x=ap-2(mod p),用快速幂可快速求之。
   求组合数
4. 容斥原理(计数一类的问题，往集合上考虑)（poj 1091）
   eg：51nod1284 问1~n里有多少数不是2、3、5、7的倍数。
   是2的倍数有n/2个……其他同理，但其中有重复计6，因此要去掉。用容斥原理排除重复计数。
   统计有公因数d的n元组有 (m/d)^n 个。（ (m ^ n) - （有公因数2的n元组）- （有公因数3的n元组）- （有公因数5的n元组）+ （有公因数2，3的n元组） +（有公因数2，5的n元组） + （有公因数3，5的n元组）- （有公因数2，3，5的n元组）。这个比公式形象些有公因数d的n元组，每个位置上有 (m/d)个选择（1 ~ m里面有m/d个d的倍数），根据乘法原理，可以得出有公因数d的n元组有 (m/d)^n 个。
   ）
5. 概率和期望：一般用dp做，有时推出公式（与组合数相关）直接求也可
   因为期望具有线性，所以可以求出子期望
   http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html
   a. 找到所有可能的情况和它的概率，则如果某结果概率为正无穷，则期望就是该结果本身 ？？？（51nod 1381）
   b. 概率dp：
   （不需要把所有可能的情况都枚举出来，而是用已经知道的状态的期望推出其他的状态的期望，或是根据一些特点和结果相同的期望情况求其概率）
6. 米勒罗宾大素数判定（1e18的需判定数）hdu2138板子
7. 矩阵快速幂 uva10870 记住公式
   8. 中国剩余定理
   求解线性同余方程组
   中国剩余定理&&拓展中国剩余定理

数据结构

1. 单调栈：（栈可以集中某一特定性质的一个序列，并保留顺序 51nod 1289 如果让向右走的鱼入栈就从前往后扫；如果让向左走的入栈，就从后往前扫，这个有先后顺序，如果从前往后扫，出现了向右的鱼，那么下一个（在新出现鱼），这里有一个动态的思想，扫描的当前是什么情况，下一个会是什么情况，贪心里也有这种如果是向左走的，他就必须和新出现的鱼作比较，如果没有向左走的，他就可以一直向右走）
   功能：找到从左到右找到第一个比x小/大的位置（栈里存下标）。一个元素向左遍历的第一个比它小的数的位置就是将它插入单调栈时栈顶元素的值，若栈为空，则说明不存在这么一个数。然后将此元素的下标存入栈，就能类似迭代般地求解后面的元素
   作用：求矩形最大面积（一块一块的这种，需要四层暴力枚举的）、求全1最大子矩阵（转化为求矩形最大面积）（c.f.最大子矩阵和）（1可以转化当作成面积）：从第一行开始，一行一行向下扫描，记录每一列当前的1的个数（碰到0时候清零，可以理解为高度，记录其为h[i ]），然后计算每一列的符合该列高度的矩形有多宽（对第j列而言，宽度为r[j]-l[j]+1）最后遍历完所有行得到的最大面积就是答案。
2. 线段树
   功能：查询、修改区间最值，区间和
   动态开点建树操作：

int id[1010];
struct node {
    int fa, lch, rch;
    char ans[1010];
    int val, len;
}tree[maxn];//从1开始有效
int rt, tot;
void init(){
    rt = 0;
    tot = 0;
    tree[0].ans[0] = '\0';
    tree[0].fa = 0;
    tree[0].lch = tree[0].rch =0;
    tree[0].len = -1;
}

char judge(int x) {
    int fa = tree[x].fa;
    if(tree[fa].rch == x) return 'W';
    else return 'E';
}
void insrt(int &now, int fa, int val) {
    //还没有过这个点
    printf("now1: %d\n", now);
    if(now == 0) {
        now = ++tot;
        printf("now2: %d\n", now);
        tree[now].fa = fa;
        tree[now].lch = tree[now].rch = 0;//作为下一个点的now,类似空指针
        tree[now].val = val;
        rep(i, 0, tree[fa].len) {
            tree[now].ans[i] = tree[fa].ans[i];
        }
        tree[now].len = tree[fa].len + 1;
        //fa不是根
        int tmp = tree[now].len - 1;
        if(fa) tree[now].ans[tmp] = judge(tot);
        tree[now].ans[tmp + 1] = '\0';
        return;
    }
    if(val < tree[now].val) insrt(tree[now].lch, now, val);//这次就传当前点的lch，所以修改的就是lch，不是rt了
    else insrt(tree[now].rch, now, val);
}

int main(){
    //freopen("../result.txt","w",stdout);
    int t;
    sd(t);
    while(t--) {
        int n;
        sd(n);
        init();
        rep(i, 0, n) {
            int val;
            sd(val);
            printf("rt: %d\n", rt);
            insrt(rt, 0, val);//传这个rt以后，因为是传引用，所以rt的值被修改了，每次都变成++tot

        }
        rep(i, 1, tot + 1) id[tree[i].val] = i;

        rep(i, 0, tot + 1) {
            printf("%d: val: %d fa: %d lch: %d rch: %d\n", i, tree[i].val, tree[i].fa, tree[i].lch, tree[i].rch);
        }

        int q;
        sd(q);
        while(q--) {
            int x;
            sd(x);
            printf("%s\n", tree[id[x]].ans);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

！！！动态开点的所有fa，lch，rch的表示都用tree[maxn]里的下标，id用来映射结点的val值（一般用于表示点权）对应的tree中的下标
3. 字典树
用于统计大量字符串、查询某个字符串、关于字符串的子串、前缀等
4. 树状数组
x+=lowbit(x) 从x一直上到他的祖先（x<=n）（数字越来越大）
x-=lowbit(x) 从x一直下到他的叶子结点（x>0）（数字越来越小）
a. 求 i 位置前（后可以per求）有多少个比他小（大可以用i-1-x计算出来）的数，原数组是cnt[i]，表示i的个数

最大限度地减少无谓的字符串比较

博弈

添加链接描述