清北学堂集训笔记

模拟只会猜题意,贪心只能过样例。
数学上来先打表,ＤＰ一般看规律。
组合数学靠运气,计算几何瞎暴力。
图论一顿套模板,数论只会ＧＣＤ。

---

倍增

定义：以F[i][j]表示，以i位置出发2^j个位置的状态 
【为什么只乘2？】如果按照k来查的话，实际上为(k-1)logk的复杂度，可证明k=2的时候复杂度最小2333333

应用1 ST表

• 应用：ST表（用来解决RMQ问题：从i到i+2^j-1这2^j个位置的最大值）//其实可以用线段树的……但是ST表好写.
• 初始化：f[i][0]=z[i];
• 转移：f[i][j]=max[f[i][j-1],f[i+2^(j-1)][j-1]);（相当准确的二分）
• 限制：不能算区间和：中间有重复的部分
  不支持修改。
• 询问：两种情况： n个数，m个询问，询问l->r最大值
  1）若区间长度正好是2^k，那么就直接访问f[l][k];
  2）若区间长度是2^k+p（p<2^k)，则当前最大值=max(f[l][k]，f[r-2^k+1][k]）；

//build
for(int a=1;a<=n;a++) f[a][0]=z[a];
for(int j=1;j<=logn;j++)
{
    for(int i=1;i+z^j-1<=n;i++)
        f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]);、
        //乘方是伪代码！
}
//solve
ans=max(f[l][k]，f[r-2^k+1][k]）；
*/

应用2 LCA

树上倍增LCA:

有一种叫做动态树的结构（LCT）可以解决这个问题，树链剖分，于是能够动态修改，noip用不着，但是还是要好好学学……

求最近公共祖先。
f[i][j]表示从树上编号为i的点向上走2^j步会走到哪个点
j大概20-30就行0 0 2^j>点数差不多就行……

• 初始化：f[i][0]=father[i];
• 转移：f[i][j]=f[f[i][j-1]][j-1];
  从i往上走2^(j-1)到的那个点再往上走2^(j-1)步到的点即为从i往上走2^j到的点
  tarjan是线性的。。。为什么不用tarjan呢……
• 询问：得到两个点p1,p2；
• 首先建树的时候要记录一下深度。
  两种情况：
  1）depth[p1]==depth[p2]，则具有性质：往上走同样的距离，深度仍然相同,如果走到了最近公共祖先，那么再往上走，就一定有p1==p2;

for(int x=19;x>=0;x--)
    if(f[p1][x]!=f[p2][x])
        p1=f[p1][x];
        p2=f[p2][x];
    //如果没有走到公共祖先处，就使劲往上跳
    //因为x的值是逆序的，所以会尽可能地上跳，接下来的长度一定不大于2^(x-1)

2）depth[p1]!=depth[p2]
若P1深度比较深，就让P1上跳，跳到深度一样的地方。
如何利用f数组在倍增上跳呢?
step=depth[p1]-depth[p2];
举例：step=13,二进制中：1101：先走八步，再走四步，再走一步就可以了

int get_lca(int p1,int p2)
{
    if(dpeth[p1]<depth[p2]) swap(p1,p2);
    for(int x=19;x>=0;x--)
    {
    if((2^x)<=depth[p1]-depth[p2]) p1=f[p1][x];
    }
}

应用3 快速幂（kissme) 【也有分治】

求A^x；[O(logx)]
如果每次把a*a*a*a*a*……真的好麻烦qwq还费时间
所以如果我们要求x(x=2*k)个a的乘积，就可以分解为x/2个a的乘积的平方。就省去了一半的计算量~
x如果是奇数，就在原先的基础上再乘一次a就行了。递归代码可以改循环~

int ksm(int a,int x,int mod)
{
    ans=1;
    while(x)
    {
        if (x&1) ans=(ans*a) % mod;//位运算：x&1==1则x为奇数
        A=(a*a) % mod;
        x>>1;//位运算，右移一位，即将X除以2
    }
}

引申：快速乘法 
求a*x=a+a+a+a+…… 
把ksm里面所有的乘号都变成加号就行了- =

分治

应用1 二分查找

给定一个排序后的数组，查询某个数是否在数组中

bool find(int x)
{
    l=0,r=n;
    while(l+1!=r)
    {
        m=(l+r)>>1;
        if(z[m]>=x) r=m;
        else l=m;
    }
}

可以用lowerbound或者upperbound

应用2 归并排序(nlogn)

先砍成两半再说！ 

把这边归并排序 那边归并排序 搞俩指针转悠转悠- = 把小值排到上面区间的下一个就行了……

应用3 快速排序(nlogn)

• sort【快排】（c艹的特性：不会退化成n*n，有奇怪的优化，而且比下面三个快……）
• qsort(最坏会退化成n*n，最好n，期望nlogn)
• merge_sort【归并排序】(无论何时都是nlogn，稳定）
• heap_sort【堆排】（同上）

贪心

以某种方式将所有物品排序 
排序后按照从小到大进行选择 

给你n个数，要求选出K个数使他们的和最大

<< 例： [noip2012] 国王游戏

• Description
  恰逢 H 国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整 数，国王自己也在左、右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队 后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左 手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
  国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

• Input
  第一行包含一个整数 n，表示大臣的人数。
  第二行包含两个整数a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。 接下来n行，每行包含两个整数a和b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

• Output
  输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

• Sample Input
  3
  1 1
  2 3
  7 4
  4 6

• Sample Output
  2
  Hint
  【输入输出样例说明】
  按1、2、3号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为2； 按1、3、2这样排列队伍，获得奖赏最多的大臣所获得金币数为2； 按2、1、3这样排列队伍，获得奖赏最多的大臣所获得金币数为2； 按2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为9；
  按3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为2；
  按3、2、1这样排列队伍，获得奖赏最多的大臣所获得金币数为9。
  因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。
  对于 20%的数据，有 1≤ n≤ 10，0 < a、b < 8；
  对于 40%的数据，有 1≤ n≤20，0 < a、b < 8；
  对于 60%的数据，有 1≤ n≤100； 对于 60%的数据，保证答案不超过 10^9；
  对于 100%的数据，有 1 ≤ n ≤1,000，0 < a、b < 10000。
  只考虑两个人
  第i个人左右手数字：l[i],r[i];第二个人：l[i+1],r[i+1];两人金币数为w[i],w[i+1];
  记P[i]=l[1]*l[2]l[3]...*l[i]
  可得：
  w[i]=P[i-1]/r[i];
  w[i+1]=P[i]/r[i+1];
  又P[i]=P[i-1]*l[i]；
  那么 w[i+1]=P[i-1]*l[i]/r[i+1]=w[i]*l[i]*r[i]/r[i+1]；
  于是乎 按a[i]*b[i]为关键字从小到大排序就好啦。
  乘除法都要写高精度，且答案有10000多位。//国王真有钱

所有的贪心题都可以用拟证来证明

搜索

• 两种不同的搜索问题
  1.最优性
  2.计数

• 两种不同的搜索方法
  1.DFS
  2.BFS

剪枝

卡时：（一般不用在树上）（OJ上不建议这么做）看到快超时的时候就退出程序，从只能得零分变成了至少得零分了……

include //去官网看能不能用，否则就会变成至多零分了……
void dfs()
{
if(clock()-t>=1998)//以毫秒为单位
{
shuchujie();exit(0);
}
}
int main()
{
t=clock();
}
数据结构维护（一般不会出到这么难）

搜索的优化技巧

1.剪枝
2.BFS：双向搜索meet in the middle（前提条件：必须知道你最终需要的状态长什么样）
从初始状态扩展出来n个状态后，不再扩展出n*n个状态，而是从最后一个在扩展出来n个。再从原来的方向搜索。从原来的O(X)变成O(sqrt(X))
3.计数问题：重复结构利用
4.最优化问题：卡时
5.数据结构优化

搜索

N皇后问题[状压DP优化]
数独问题[卡时] 启发式搜索：从个数最少的开始搜索（跳舞链dancing links是啥？）
noip 2012 mayann

奇怪的东西
读入优化：(读int超快！)
int getint()
C=' ';
while(c<'0' || c>'9') c=getchar();
X=0;
while(c>='0' && c<='9') X=X*10+c-'0',c=getchar()

模拟

今天模拟三道题，我真是太菜了……

第一题：
枚举换哪几个格子，真的就是无脑枚举模拟，我也不知道为什么我居然错了，就这样吧ovo
（这种题能够快速提高代码能力，建议闲的没事多做做）
第二题：
二分答案+暴力
比如知道当前二分出来的答案是m，要求出是否存在这样一个矩阵，使其四个点都大于等于m。往右延伸一定的距离，再往下延伸，就能确定整个矩形，算出来最小值，和答案进行对比就可以了- =
可以这么操作：把大于等于r的值都变成0，小于r的变成0，可以等价为是否存在矩阵是四个点都是1。可以提前预处理出来哪些位置是1，就不需要枚举其它位置了。

还有另外一个方法：
将所有的点权值从大到小一个一个加到矩形中，如果出现了新的矩形就输出
第三题：
杨辉三角…………………………生气

杨辉三角的补充：

组合数：从n个物体中选m个的方案数
Cnm=n!/(m!(n-m)!)
Cnm=C(n-1)(m-1)+C(n-i)(m)//可以不断拆开
Cnm=sigma(j=0->i) C(n-2)(m-i+j)*cij;
cnm=cn(n-m)
如果把它们都列出来，就是一个杨辉三角，是右上方和左上方两个数的和

lucas:
cnm%p 可以逆元，或者把n,m变成p进制的数，则cnm%p=cn1m1*cn2m2*cn3m3%p

ummmm我觉得我现在做题还比较稚嫩……就像我都想到正解或者接近正解，就是不敢写……要么就写挂，果然要锻炼代码能力啊……

day 2

素数的判定

1)弱智才会用的办法

bool prime(int x)
{
    if (x<2) return 0;
    for(int a=2; a*a<x; a++) if(x % a==0) return 0;
    return 1;
}

2)费马小定理

p为一个素数且p不是a的倍数，则a^(p-1)=1(mod p);[不能反推]
多次选取a，检验p是否满足费马小定理。
O(klogp)
卡迈尔数

3)miller-rabin(MR定理【听不懂】）

如果n为素数，取a < n,设n-1=d*2^r,则要么a^d≡1(mod n)，要么30<=i < r,s.t.a ^(d*s^t)≡-1(mod n)

int prime=[3,7,11,23,37];
bool miller_rabin(int x)
{
    n-1=d*2^r;
    for(int a=1;a<=5;a++)
    {
        if(ksm(a,d) %n !=1)
        {
            for(int i=0;i<r;i++)
            {
                if(ksm(a,d*2^i)%n==-1) return 1;
            }
            return 0;
        }
    }
}

钟神：“背结论吧。”
4)筛法

用来处理连续区间内有哪些质数。
a.非线性筛法(nlogn=1/1+1/2+1/3+···+1/n)
质数的倍数一定是合数。

bool not_prime[1000005];
not_prime[1]=true;
for(int a=2;a<=n;a++）
{
    if(!not_prime[a]) for(int b=a+a;b<=n;b+=a) not_prime[b]=true;//如果有那个if优化的话，就是nloglogn
}

b.线性筛法（欧拉筛法）
每个合数都由它最小的质因数筛掉。一个数会被拆成几个质数相乘，最小的质数就直接筛了，就避免了重复筛的过程。接近于O(n)

memset(notprime,0,sizeof(notprime)),notprime[1]=true;
for(int i=2;i<=n;i++)
{
if(!notprime[i]) prime[++ prime_count]=i;
    for(int j=1;j<=prime_count;++j)
    {
        if(prime[j]*i>n) break;
        not_prime[prime[j]*i]=true;//用来筛质数的倍数的数
        if(i%prime[j]==0) break;//保证了只会找到最小的质因子来筛掉它
    }
}

欧几里得定理：

求n个不超过m的正整数复杂度：O(n+logm);
通过辗转相除法求最大公因数。

int gcd(int a,int b)
{
return b?gcd(b,a%b):a;//一行代码就是爽
}
扩展欧几里得定理

欢迎访问我的博客，讲的和钟神一样清晰233
扩展欧几里得算法

求解同余方程

题目描述求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入数据输入只有一行，包含两个正整数 a, b，用一个空格隔开。
输出数据输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。
输入样例3 10
输出样例7
数据范围
对于 40%的数据，2 ≤b≤ 1,000；
对于 60%的数据，2 ≤b≤ 50,000,000；
对于 100%的数据，2 ≤a, b≤ 2,000,000,000。

ax%b=1 <=> ax-by=1;
可由此求出一组x,y的解，转移得到正整数最小解就行啦
求解一次同余式组：中国剩余定理

有一个数 x≡a1(b1 mod p1),x≡a2(mod p2),x≡a3(mod p3)……,x≡ak(mod pk);
求解最小x。
x=k1p1+a1,x=k2p2+a2……
k1p1+a1=k2p2+a2 -> k1p1-k2p2=a2-a1;
将好多好多的这样的方程加在一起。

大数翻倍法

x=a1(mod p1);
x=a2(mod p2);
假设P1 < P2；
复杂度O(min(p1,p2));

int fanbei(int a1,int p1,int a2,int p2)//p1 {
ans=a2;
while(ans % p1 != a1) ans+=p2;
return ans;
}
大体的意思就是，找到一个最大的P，然后不断翻倍，使它能够整除其它所有的P

逆元

在模的意义下通过逆元也能做除法。
如果gcd(a,m)=1,且存在唯一的b，使得a*b≡1(mod m)且1<=b < m,则b为a在模m意义下的逆元
当m为质数的时候，直接使用费马小定理

$$a^(p-1)≡1$$
m非质数时，使用欧拉定理 $$a^φ(m)≡1$$
φ(m)：欧拉函数，表示小于等于m的质数的个数

积性函数

如果对于(n,m)=1,有f(nm)=f(n)f(m)，则称f为积性函数

$$σ(n)=Σd|n$$ d 从1到n的加和
$$τ(n)=Σd|n$$ 1 n的因子个数
φ(n) 欧拉函数 1-n当中与n互质的数的个数 $$ϕ(n)=n∗∏(pi−1)/pi$（∏：乘积）$$
μ(n) 莫比乌斯函数 n=p1^k1*p2^k2*p3^k3……

当n=1时，μ(n)=1
当k1=k2=k3=……=kr=1时，

$$μ(n)=(-1)^r$$
否则μ(n)=0;
在数论的容斥原理中多有使用。
求积性函数只需要在线性筛中加上函数就行。
举例子：欧拉函数

memset(notprime,0,sizeof(notprime)),notprime[1]=true;
for(int i=2;i<=n;i++)
{
    if(!notprime[i])
    {
        prime[++ prime_count]=i;
        phi[i]=i-1;
    }
    for(int j=1;j<=prime_count;++j)
    {
        if(prime[j]*i>n) break;
        not_prime[prime[j]*i]=true;
        if(i%prime[j]!=0)//积性必须满足gcd(n,m)=1
        {
            phi[prime[j]*i]=phi[prime[j]]*phi[i];//a与b互质的话，a+b与b也互质
        }
        else phi[i*prime[j]]=phi[i]*prime[j];
        if(i%prime[j]==0) break;
    }
}

留着看：欧拉函数
如果你看到这行文字……代表我的图挂了QAQ

例题：求a^x≡b(mod m)的最小正整数解。
BSGS（北上广深）算法：
a^φ(m)≡1(mod m),所以解一定在a^1,a^2,a^3……a^m之间
可以每次两个两个枚举，如果没有答案就乘上a^2,再继续枚举下去。
最高效的方式：k=sqrt(m)，写成一个k*k的矩阵形式

a^1 a^2 a^k
a^(k+1) a^(k+2) a^(k+3)
a^(2k+1) a^(2k+2) a^(2k+3)
每行询问klogk，第一行排序klongk，O(sqrt(m)log(m)）.
在每一行是否出现，可以直接通过除以a^nk（乘法逆元），转移到第一行

作业：给一个n,m,for(int i=1,i<=n;i++) for(int j=1;j<=m;j++) 求Σgcd(i,j);

概率

基本知识

Pr[i]表示事件i发生的概率 Σi=1->N Pr[i]=1； xi表示事件i的权重 E[x]=Σi=1->N Pr[i]*xi 有x个人没有人生日相同的概率：366/366+365/366+364/366……+366-x+1/366
对于独立事件i和j，Pr[i^j]=pr[i]*pr[j] 事件i和事件j的期望是可加的。
条件概率： 当事件j已经发生时，事件i发生的几率 pr[i|j]=pr[i^j]/pr[j] 一个有趣的结论: 当太阳已经从东边升起n天后，第n+1天从东边升起的概率：(n+1)/(n+2)
题目

1)problem 1
甲乙面前三瓶药，两瓶毒药，每人喝一瓶。
甲喝了一瓶，挂掉了
为了活下去，乙应该喝手上的这瓶，还是另外剩下的一瓶呢？
喝哪个都一样，因为乙不知道哪个有毒。

2)problem 2

小胡站在原点，手里拿着两枚硬币。抛第一枚硬币正面向上的概率为𝑝，第二枚正面向上的概率为𝑞。
小胡开始抛第一枚硬币，每次抛到反面小胡就向𝑥轴正方向走一步，直到抛到正面。
接下来小胡继续抛第一枚硬币，每次抛到反面小胡就向𝑦轴正方向走一步，直到抛到正面。
现在小胡想回来了，于是他开始抛第二枚硬币，如果小胡抛到正面小胡就向𝑥轴的负方向走一步，否则小胡就向𝑦轴的负方向走一步。
现在小胡想知道他在往回走的时候经过原点的概率是多少呢？
假设小胡走到(x,y)又回到原点。首先往x正方向走x步又抛到正面的概率是p*(1-p)^x,在往y轴正方向走y步的又抛到正面的概率是(1-p)^y*p。往回走的时候：往X负方向走x步的概率是q^x,往Y负方向走y步的概率是(1-q)^y。总的概率是：
p*(1-p)^x*(1-p)^y*p*q^x*(1-q)^y=p^2*(1-p)^(x+y)q^x(1-q)^y;
一共走x+y步，其中不知道x有几步，于是我们要枚举x+y和x。每对x+y,x都有c(x+y)x种方式。在原来的概率上加上组合数就行啦。
最后的概率：
图挂了qwq
化简以后:
图跪了qwq
注意这个公式的运用：
图炸了qwq

2.3) problem 2.3

小葱想要过河，过河有两条路
一条路有100个石头，每个石头有1/100的概率会挂掉
一条路有1000个石头，每个石头有1/1000的概率会挂掉
小葱应该走哪边呢？
请勿使用计算器
显然：
Markdown

3) problem 3
这道题被抛弃了……

4) problem 4

小泽在数轴上的0点处
小泽每次有𝑟的概率向右走，有1−𝑟的概率向左走
问小泽走到−1处的概率
试着枚举步数www

步数 概率
一步 1-r
两步 0
三步 r*(1-r)^2
四步 0
五步 r^2*(1-r)^3*卡特兰数（保证前缀和>=0)
PS：刚刚翻到一个超棒的浅谈卡特兰数

如果按照上面那种一步步加上来的办法，特别麻烦……
所以换个思路，设概率试试。
设从x出发到达x-1的概率为p,第一步向左的概率是1-r,第一步向右到x，再从x到x-1的概率是rp^2。则有p=(1-r)+rp^2。
解得：
p=1 (r<=1/2),
p=(1-r)/r (r>1/2);

5) problem 5

小胡有一棵一个点的树，小胡会给这个点浇水，于是这个点会有𝑝的概率长出两个儿子节点。
每次长出新的节点之后，小胡又会给新的节点浇水，它们也都有𝑝的概率长出两个新的儿子节点。
小胡不希望自己被累死，所以小胡希望知道这棵树的大小是有限的的概率。
这道题和problem4是一样的……

6) problem 6
老师又弃题啦QAQ

给一堆点的坐标。在平面内画个圆，把所有的点都包含进去，问最小半径
第一种方法：
三点可以确定一个圆，所以暴力方法：枚举三个点，再把剩下的点一个一个扔进去，看看在不在圆里面
O(n^4)
如何优化？
举个例子，通过a,b,c三个点你确定了一个圆，圆包含x,y,z三点，但是不符合条件，于是你开始重新枚举。但是未来就没有枚举x,y,z的必要了……这样就浪费了很多。
那么不如一个个往里面加点，加点后再扩张~

for（int a=1;a<=n;a++)
{
    if(!in(p[a])) circle=cir(p[a]);
    for(int b=1;b<=a;b++)
    {
        if(!in(p[b])) circle=cir(p[a],p[b]);
        for(int c=1;c<=b;c++)
        {
            if(!in(c)) circle=cir(p[a],p[b],p[c]);
        }
    }
}

第二种方法
c++有个函数叫random_shuffle，作用是随机打乱n个点的顺序。
可以将它优化到O(n)。
随机选三个点形成一个圆。
于是接下里的点进入下面两个循环的概率实际上很小233所以复杂度就会变得很玄学很诡异……

代数

排列和逆序对

逆序对：对于一个排列a1,a2,a3……an，若存在一个1<=i < j<=n，存在ai > aj，则这个有序对成为一个逆序对，也称为逆序数。
对换：在一个排列中，对换其中某两个数，其余的数不动，得到另一个排列，这种操作称为一个对换。
奇偶排列：如果一个排列的逆序数是偶数，则称此排列为偶排列，否则称为奇排列。

行列式

我没有弄明白这个东西的原理和用途。希望能有大佬给我一点指导
QQ:1183940941

矩阵

乘法
定义：设A=aij(m*r),B=bij(r*n),则矩阵C=cij(m*n).其中cij=ai1*b1j+ai2*b2j+……+ain*bnj。
C称为𝐴与𝐵的乘积，记做𝐶=𝐴𝐵
第一个矩阵的列数必须等于第二个矩阵的行数！

矩阵乘法运算律
missed emage!qwq

特殊的矩阵
零矩阵

0 0 0
0 0 0
0 0 0
对角矩阵

1 0 0
0 0 0
0 0 3
单位矩阵

1 0 0
0 1 0
0 0 1
上三角矩阵

1 2 3
0 4 5
0 0 6
下三角矩阵

1 0 0
2 3 0
4 5 6
对称矩阵

1 2 6
2 3 5
6 5 7
递推与矩阵
斐波那契和矩阵乘法的关系？
|fn-1 fn| × |0 1| =|fn fn+fn-1|
|1 1| (fn+1)
如果换了一个递推公式，要怎么写这个矩阵呢？
f(n)=af(n-1)+bf(n-2);
|fn fn-1| × |w x|=[fn+1 fn];
|y z|
通过矩阵乘法的特点，可得到关系式：
fn+1=wfn+yfn-1
fn=xfn+zfn-1
于是可得：a=w,b=y,x=1,z=0;
于是原矩阵中值可以由上面的等值代替啦。

矩阵在解方程上的应用
一般线性方程组：

a11x1+a12x2+……+a1nxn=b1
a21x1+a22x2+……+a2nxn=b2
···
an1x1+an2x2+……+annxn=bn
高斯消元法
即加减消元法。在计算机中，方法则不同。

x1+x2+x3=6
x1+2x2+3x3=9
x1+4x2+9x3=36
将系数变成一个矩阵

1 1 1 6
1 2 3 9
1 4 9 36
用第二行，第三行分别减去第一行得到

1 1 1 6
0 1 2 3
0 3 8 30
用第三行减去三倍的第二行得到

1 1 1 6
0 1 2 3
0 0 2 21
最后一行21/2=x3;
倒数第二行x2+2x3=3，解得x2=-18;
同理可得x1值。

如果当前方程系数是0，那就在下面找个不是0的跟它换一下就好了……

//矩阵：m

for(int a=1;a<=n;a++)
{
    if(fabs(m[a][a])<=eps)
    {
        for(int b=a+1;b<=n;b++)
        {
            if(fabs(m[b][a])>eps) swap(m[a],m[b]);//fabs用于浮点数,m[a],m[b]是引用//此处有问题，请大佬指正
            break;
        }
    }
    for(int b=a+1;b<=n;b++)
    {
        ratio=m[b][a]/m[a][a];
        for(int c=1;c<=n+1;c++)
        {
            m[b][c]-=m[a][c]*ratio;
        }
    }
}
for(int a=n;a>=1;a--)
{
    solution[a]=m[a][n+1];
    for(int b=a+1;b<=n;b++)
    {
        solution/=m[a][a];
    }
}

举个栗子
f(x)=ax^5+bx^4+vx^3+dx^2+ex+f
可以得到f(1),f(2),f(3),f(4),f(5),f(6),然后利用高斯消元法就可以解决这个问题了

高斯消元法自动找规律机
1.打表
2.枚举次数，符合表就可以

ps:一个小技巧，读入long long的时候不知道什么系统，就这么干：

#ifdef WIN32
#define LL "%I64d"
#else
#define LL"%lld"
#endif//编译开关
long long gg;
printf(LL,gg);

day 3

动态规划

记忆化搜索

举例：数字金字塔。求一条权值最大的路径

状态：x行，y列
下一个状态：向左走，向右走
//暴力搜索法

void dfs(int x, int y, int val)
{
    val += a[x][y];
    if(x == n-1)
    {
        if(val > ans) ans = val;
        return;
    }
    dfs(x+1, y, val);
    dfs(x+1, y+1, val);
}

冗余搜索：到达同一个点时的权值比之前搜的小。
从而剪枝：利用数组F记录到达该点的权值最大值，如果搜到这儿小于F，就不继续往下搜啦。
这种通过记录状态从而减去冗余搜索的方法，叫做记忆化搜索。
在以上的例子中，记忆的是到达该点最大的权值和~

//记忆化搜索

void dfs(int x, int y, int val) 
{
    val += a[x][y];//记忆化过程
    if(val <= f[x][y]) return;
    f[x][y] = val;
    if(x == n-1) 
    {
        if(val > ans) ans = val;
        return;
    }
    dfs(x+1, y, val);
    dfs(x+1, y+1, val);
}

背包问题

例题：

Luogu 1048 : 采药
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，
他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个
难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山
洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的
价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你
是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

总时间：70
草药1 ：时间71；价值100
草药2 ：时间69；价值1
草药3 ：时间1 ；价值2

最优选择：草药2+3：总时间70；总价值3
回忆搜索的实现：

• 状态：目前已经决定到第x件物品，当前背包中物品总重量为w，总价值为v；
• 行动：这件物品取不取；
• 约束：物品的总重量不超过W(背包总重量)；
• 目标：物品总价值最大；

冗余搜索：
当前搜索到同一件物品，且物品的总重相等时，若v1< v2,则状态1为冗余的，因为它肯定比状态2要差。
记忆化：对于每个状态(x,w)，记录对应的v的最大值。

//记忆化搜索

void dfs(int t, int x, int val) // t 为剩余时间，val 为总价值
{
    if(val <= f[t][x]) return;// 记忆化
    f[t][x] = val;
    if(x == n)
    {
        if(val > ans) ans = val;
        return;
    }
    dfs(t, x+1, val);
    if(t >= w[x]) dfs(t - w[x], x+1, val + v[x]);
}
bitset优化：
//原来写01背包的时候，循环是这么写的：
for(int i=1;i<=n;i++)
{
    for(j=m;j>=a[i];j--) if(f[j-a[i]]) f[j]=1;
}
//可以改成位运算版本的
for(int i=1;i<=n;i++)
{
    f=f|f<<a[i];
}

DP

回到数字金字塔，我们可以看到，每一步其实都走到了最大值
所以对于任意的点，它如果要到达最优值，一定是从左上方或者右上方的最大值推来的。所以利用动态规划（DP）有如下思路：
DP记录状态的最优值，并用最优值来推导出其他的最优值。
记录F[i][j] 为第i 行第j 列的路径最大值。有两种方法可以推导：
顺推：用F[i][j] 来计算F[i+1][j],F[i+1][j+1]；
逆推：用F[i-1][j],F[i-1][j-1] 来计算F[i][j]。

DP转移方程：
顺推

F[i+1][j] = MAX (F[i][j] + a[i+1][j]); 
F[i+1][j+1] = MAX (F[i][j] + a[i+1][j+1]); 

逆推
F[i][j] = MAX (F[i-1][j], F[i-1][j-1]) + a[i][j];//注意边界
顺推和逆推本质上是一样的；顺推和搜索的顺序类似；而逆推则是将顺序
反过来；顺推考虑的是“我这个状态的下一步去哪里”，逆推的考虑的是
“从什么状态可以到达我这里”。

//顺推
f[0][0] = a[0][0];
for(int i = 0; i < n - 1; ++ i)
for(int j = 0; j <= i; ++ j)//分别用最优值来更新左下方和右下方
{
f[i+1][j] = max(f[i+1][j], f[i][j] + a[i+1][j]);
f[i+1][j+1] = max(f[i+1][j+1], f[i][j] + a[i+1][j+1]);
}
}
//逆推
f[0][0] = a[0][0];
for(int i = 0; i < n; ++ i)
{
f[i][0] = f[i-1][0] + a[i][0]; //最左的位置没有左上方
f[i][i] = f[i-1][i-1] + a[i][i]; //最右的位置没有右上方
for(int j = 1; j < i; ++ j) //在左上方和右上方取较大的
f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
}
// 答案可能是最第一行的任意一列
ans = 0;
for(int i = 0; i < n; ++ i) ans = max(ans, f[n-1][i]);
还有一种思路，既然这条路一定经过最后的某个点和0,0点，那么完全可以从下往上走。权值和还是相同的w

//逆推/ 路径自底向上
//改变顺序：记录从底部向上走的路径最优值
for(int i = 0; i < n; ++ i) f[n-1][i] = a[n-1][i];
//逆推过程：可以从左下方或右下方走过来；没有边界情况
for(int i = n-2; i >= 0; -- i)
for(int j = 0; j <= i; ++ j)
f[i][j] = max(f[i+1][j+1], f[i+1][j]) + a[i][j];
// 答案则是顶端
ans = f[0][0];
在数字金字塔中使用DP的基础：有明确的顺序（可以划分出阶段），因此顺推逆推都可以。

动态规划(DP)：只记录状态的最优值，并用最优值来推导出其他的最优
值。
那么再看背包问题，分析一下如何使用DP
- 状态设计：记录F[i][j] 为，已经决定前i 件物品的情况，在总重量
为j 的情况下，物品总价值的最大值。同样也是有两种方法可以推导：
顺推：“我这个状态的下一步去哪里”
逆推：“从什么状态可以到达我这里”

顺推思路：对于每个状态的下一个状态，可以看为“取不取下一件物品”。
如果不取的话，可以达到状态F[i+1][j]；
如果取的话，可以达到状态F[i+1]j+w[i+1];
取上面两种状态的最大值就行了。

逆推思路：对于当前状态的上一个状态，可以看为“当前这件物品取没取”
如果没有取，那可以从F[i-1][j] 推导而来；
如果取了的话，可以从F[i-1][j-w[i]] 推导而来(需要满足重量约
束)。
同理，取上面两种状态的最大值。

采药问题的代码如下：

//DP/顺推
for(int i = 0; i < n; ++ i)
for(int j = 0; j <= t; ++ j)
{
f[i+1][j] = max(f[i+1][j], f[i][j]); // 不取
if(j + w[i] <= t)
f[i+1][j+w[i]] = max(f[i+1][j+w[i]], f[i][j]+v[i]);// 取
}
ans = 0;
for(int i = 0; i <= t; ++ i) ans = max(ans, f[n][i]);
//DP/逆推
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= t; ++ j)
{
f[i][j] = f[i-1][j];// 不取
if(j >= w[i]) f[i][j] = max(f[i][j], f[i-1][j-w[i]] + v[i]);// 取
}
ans = 0;
for(int i = 0; i <= t; ++ i) ans = max(ans, f[n][i]);
可以看到，F数组是一个二维数组，使用的空间非常的大……有个奇妙的压缩空间的技巧：数组压缩（滚动数组）。
观察状态转移方程，可以发现F[i] 只由F[i-1] 决定。也就是说，前
面的很多状态对后面都是没有影响的。所以我们可以只保留前一行的状
态。
Markdown

例如，F[4] 中的状态只和F[3] 中的两个状态A、B 相关
所以一个直观的做法是，记录两个数组，分别记录F[i-1] 与F[i] 的
值。
但更进一步，我们可以甚至不记录两行，只记录一行的状态。
我们倒着枚举，在F[i-1] 数组中逐步更新，让它逐步变为F[i]。
Markdown

粗框中记录的是F 数组对应的值
因为是倒着枚举的，先枚举的位置都已经无用了，可以直接用F[i] 的
元素来替换。
Markdown

//DP/逆推/数组压缩
// 用一个一维数组来代替二维数组
for(int i = 1; i <= n; ++ i)
for(int j = t; j >= 0; -- j) // 重量：倒着枚举
{
// 不取：对数组没有影响,不用讨论了
if(j >= w[i]) f[j] = max(f[j], f[j - w[i]] + v[i]);
}
// 在枚举过程中，大于j 的位置等于f[i][j]，小于j 的位置等于f[i-1][j]
完全背包问题

POJ 1384 : Piggy-Bank
现在有n 种硬币, 每种硬币有特定的重量cost[i] 和它对应的价值val[i]. 每种硬币可以无限使用。已知现在一个储蓄罐中所有硬币的总重量正好为m 克, 问你这个储蓄罐中最少有多少价值的硬币? 如果不可能存在m 克的情况, 那么就输出“This is impossible.”
我们也把这类问题归入到背包问题当中：有物品，重量限制，价值最大。
但与采药问题不同的是，每件物品可以无限使用。
当前状态：F[i][j] 为，已经决定前i 件物品的情况，在总重量为j
的情况下，物品总价值的最大值。
顺推：“我这个状态的下一步去哪里”：考虑我这件物品取多少件。

如果是不取的，那可以推导到F[i+1][j]；
如果是取一件，那可以推导到F[i+1][j+w[i]]；
如果是取k 件，那可以推导到F[i+1][j+w[i]*k].
//DP/顺推
// 初值处理：由于问题求的是最小值，所以先把所有状态赋值为最大值
for(int i = 1; i <= n + 1; ++ i)
for(int j = 0; j <= m; ++ j) f[i][j] = INF;
// 第一件还没取，重量为0
f[1][0] = 0;
for(int i = 1; i <= n; ++ i) // i：已经决定的物品
for(int j = 0; j <= m; ++ j) // j：总重量
for(int k = 0; j + w[i] * k <= m; ++ k) // k：这件物品取多少件
f[i+1][j+w[i]*k] =min(f[i+1][j+w[i]*k], f[i][j] + p[i]*k );
// w 重量；p 价值
逆推：“从什么状态可以到达我这里”：考虑我这件物品取多少件。

如果是不取的，那可以从F[i-1][j] 处推导得到；
如果是取一件，那可以从F[i-1][j-w[i]] 处推导得到；
如果是取k 件，那可以从F[i-1][j-w[i]*k] 处推导得到；
// T9 / work1 : Piggy-Bank（DP/逆推）
for(int i = 0; i <= n; ++ i)
for(int j = 0; j <= m; ++ j) g[i][j] = INF;
g[0][0] = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
for(int k = 0; j >= w[i] * k; ++ k)
g[i][j] = min( g[i][j], g[i-1][j-w[i]*k] + p[i]*k );
逆推优化：观察和逆推相关的状态。
假设w[i]=3，则F[i][6] 与F[i-1][0,3,6] 相关；F[i][7] 与
F[i-1][1,4,7] 相关；与此同时，F[i][3] 与F[i-1][0,3] 相关；
F[i][4] 与F[i-1][1,4] 相关。
则可以得到，实际上与F[i][j] 相关的状态只比F[i][j-w[i]] 多一
个。
Markdown
则所以我们可以这样推导：

如果是不取的，那可以从F[i-1][j] 处推导得到；
如果是取一件或更多，那可以从F[i][j-w[i]] 处推导得到；(因为是可以
取任意件，所以从F[i] 中取最优而不是从F[i-1] 中取) 也就是，横着推……
* 而从这种逆推也可以方便的写出数组压缩。
Markdown

//DP/逆推优化
for(int i = 0; i <= n; ++ i)
for(int j = 0; j <= m; ++ j) g[i][j] = INF;
g[0][0] = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
{
g[i][j] = g[i-1][j];
if(j >= w[i]) g[i][j] = min(g[i][j], g[i][j-w[i]] + p[i]);
}
//DP/逆推优化/数组压缩
for(int j = 0; j <= m; ++ j) f[j] = INF;
f[0] = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
if(j >= w[i]) f[j] = min( f[j], f[j-w[i]] + p[i] );
背包计数问题

Luogu 1466 : 集合
* 对于从1 到N (1 <= N <= 39) 的连续整数集合，能划分成两个子集
合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于
[1，2，3] 能划分成两个子集合，每个子集合的所有数字和是相等的：
- [3] 和[1,2]
* 这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增
加划分方案总数）如果N=7，有四种方法能划分集合[1，2，3，4，5，
6，7]，每一种分法的子集合各数字和是相等的:
- [1,6,7] 和[2,3,4,5] (注: 1+6+7=2+3+4+5)
- [2,5,7] 和[1,3,4,6]
- [3,4,7] 和[1,2,5,6]
- [1,2,4,7] 和[3,5,6]
* 给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，
则输出0。程序不能预存结果直接输出（不能打表）。
如何引入背包模型？

物品：可以把所有的数字看作物品。对于数字i，其对应的重量为i，则
我们需要求出装满载重为M 的背包的方案数(其中M 为所有数总和的一
半)。

状态：（仿照之前的方法）设F[i][j] 为已经考虑完数字1-i 了，当前
数字总和为j 的总方案数。

状态转移方程- 顺推：考虑有没有取数字i。
没取：F[i+1][j] += F[i][j]
取了：F[i+1][j+i] += F[i][j] (j+i<=M)

状态转移方程- 逆推：考虑有没有取数字i。
F[i][j] = F[i-1][j] + F[i-1][j-i] (j>=i)

//DP/顺推
// 初值：（什么都不取）和=0，有一种方案
f[1][0] = 1;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
{
f[i+1][j] += f[i][j];
if(i + j <= m) f[i+1][i+j] += f[i][j];
}
//DP/逆推
f[0][0] = 1;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
{
f[i][j] = f[i-1][j];
if(j >= i) f[i][j] += f[i-1][j-i];
}
//DP/逆推/数组压缩
g[0] = 1;
for(int i = 1; i <= n; ++ i)
for(int j = m; j >= i; -- j) // 注意要倒着枚举
g[j] += g[j-i];
完全背包计数问题

Luogu 1474 : 货币系统
母牛们不但创建了它们自己的政府而且选择了建立了自己的货币系统。由于它们特殊的思考方式，它们对货币的数值感到好奇。
传统地，一个货币系统是由1,5,10,20 或25,50, 和100 的单位面值组成的。
母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。
举例来说, 使用一个货币系统[1,2,5,10,...]产生18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。
物品：可以把所有的货币看作物品。对于每种货币，其对应的重量为它的面值(注意到与前一道题目相比，每个物品是可以取任意件的)。
状态：（仿照之前的方法）设F[i][j] 为已经考虑完前i 种货币了，当前钱的总和为j 的总方案数。
状态转移方程- 逆推：考虑货币i 取了多少件。
F[i][j] =ΣF[i-1][j - w[i]*k];
//DP/逆推
f[0][0] = 1;
for(int i = 1; i <= v; ++ i)
for(int j = 0; j <= n; ++ j)
for(int k = 0; k <= j / a[i]; ++ k)
f[i][j] += f[i-1][j - a[i]*k];
//DP/逆推/数组压缩
g[0] = 1;
for(int i = 1; i <= v; ++ i)
for(int j = a[i]; j <= n; ++ j)
g[j] += g[j - a[i]];
总结
* 解决动态规划问题，需要注意以下几点：
- 顺序/状态：与搜索类似，依然需要考虑问题的先后顺序，以及状态的表
示
- 转移方程：有顺推与逆推两种；需要注意初值、边界情况。
* 同时在实现背包问题中，可以使用数组压缩来优化空间。
路径行走问题

Luogu 1004 : 方格取数
设有N*N 的方格图(N<=9)，我们将其中的某些方格中填入正整数，而
其他的方格中则放入数字0。
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到
达右下角的B 点。在走过的路上，他可以取走方格中的数（取走后的方
格中将变为数字0）。
此人从A 点到B 点共走两次，试找出2 条这样的路径，使得取得的数
之和为最大。
与数字金字塔很相似。如果只走一次：
记录P[i][j]为走到第i行第j列的最大值。
但是，我们需要考虑两条道路同时进行的情况，不能单独进行。
所以我们建立一个四维数组F[i][j][k][l]来记录第一条路径走到(i,j),另一条路径走到(k,l)的最大值。对于每条路有两种可能性，2*2=4种。
注意：如果两个点同时走到同一个地方，权值只能被加一次

//DP / 逆推
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
for(int k = 1; k <= n; ++ k)
for(int l = 1; l <= n; ++ l)
{
// 注意，如果走到了一起，只加一次
int cost = a[i][j] + a[k][l] - a[i][j] * (i == k && j == l);//还有这种操作的说
// 四种可能性；考虑：为什么不加边界情况的判断？
f[i][j][k][l] = max
(
max(f[i-1][j][k-1][l], f[i-1][j][k][l-1]),
max(f[i][j-1][k-1][l], f[i][j-1][k][l-1])
) + cost;
}
最长不下降子序列问题

Luogu 1020 : 导弹拦截
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配
备多少套这种导弹拦截系统。
389 207 155 300 299 170 158 65
最多能够拦截：6
最少要配备：2
LIS：一个序列当中一段不下降的子序列。
LDS：一个序列当中一段下降的子序列。
* 这道题目中第一问要求我们找到一段最长的单调下降的子序列。(无论是上升还是下降，可以使用类似的算法解决)
* 状态：我们用F[i] 代表，以i 位置为结尾的一段，最长的下降子序列。
* 最优性：如果某段[q1q2q3……qn]是以qn结尾的最长下降子序列；那么去掉最后一个的序列[q1q2q3……qn-􀀀1]，依然是以
Markdown
F[4]从F[2]转移而来~
逆推：假设我们需要求以X 结尾的最长下降子序列F[X]；

由最优性可得，我们除去最后一个位置(也就是X)，还是一段最长下降子序列。
那我们可以枚举这个子序列的结尾Y，最优值就是F[Y]。
但需要注意的是，必须保证 A[ x] < A[y]，X 比Y 要低，才满足下降的
要求。
我们从所有枚举的结果中找到一个最大的即可。
注意到题目还需要计算‘如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。’
可以直接观察得到，所求的答案至少为原题的最长不下降子序列。
因为它们当中，任意两个都不可能被同一个导弹打中。
事实可以证明，这就是答案。
Markdown
图中的4 个导弹都单独需要一个系统。
//DP / LIS / 逆推
int ansf = 0, ansg = 0; // 记录所有的f(g) 中的最优值
// f 计算下降子序列，g 计算不下降子序列
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j < i; ++ j)
if(a[j] > a[i]) f[i] = max(f[i], f[j]);
else g[i] = max(g[i], g[j]);
++ f[i], ++ g[i]; // 加上自己的一个
ansf = max(ansf, f[i]);
ansg = max(ansg, g[i]);
}
cout << ansf << endl << ansg << endl; // 输出答案
//P（口）S（胡）：这个代码一看就不是我的风格，空格方式完全不同，输入输出方式迥异……我从来不用流输入输出orz
Luogu 1091 : 合唱队形
N 位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1; T2; ……; TK，则他们的身高满足 T1 < ……< Ti > Ti+1 > ……> TK (1 < i < k);
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
186 186 150 200 160 130 197 220
最少需要4 位同学出列
问题转化：最少的同学出列-> 尽量多的同学留在队列

与LIS 的联系：如果确定了中间的“顶尖”，两侧就是“单调上升”和
“单调下降”的。
容易想到枚举每个人为顶尖，分别在两端算最长下降子序列和最长上升子序列长度，加一起就是出列的人的数量。
状态设计：F[i] 与G[i]
预处理得到F[i]，G[i]
F[i]：以i 为端点，左侧的最长的上升子序列长度。
G[i]：以i 为端点，右侧的最长的下降子序列长度。
for(int i = 1; i <= n; ++ i) cin >> a[i], f[i] = g[i] = 1;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j < i; ++ j)
if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
for(int i = n; i; -- i) // g 的计算从反方向进行枚举
for(int j = n; j > i; -- j)
if(a[i] > a[j]) g[i] = max(g[i], g[j] + 1);
int ans = 0;
for(int i = 1; i <= n; ++ i) // 枚举每一个顶点为顶尖
ans = max(ans, f[i] + g[i] - 1);
最长公共子序列

Luogu 1439 : 排列LCS问题
给出1-n 的两个排列P1 和P2，求它们的最长公共子序列。
公共子序列：既是P1 的子序列，也是P2 的子序列。
3 2 1 4 5
1 2 3 4 5
最长公共子序列(LCS)：3([1 4 5])
Markdown

例子中，[1 2 2 3 1] 即为序列的公共子序列
LCS：两个序列的最长公共子序列。

状态：我们用F[i][j] 代表，前一个序列以i 位置为结尾，后一个序
列以j 位置为结尾，它们的最长公共子序列。
最优性：如果某段[q1q2q3……qn] 是分别以i，j 结尾的最长公共子序
列；那么去掉最后一个的序列[q1q2q3……qn-􀀀1]，依然是以i-1,j-1为结尾的最长公共子序列。
Markdown

例子中，去掉结尾的5 后，[1 4] 仍是最长公共子序列.
A[i] 不在公共子序列中，那么长度则等于F[i-1][j]；

B[j] 不在公共子序列中，那么长度则等于F[i][j-1]；
A[i] 与B[j] 都在子序列中，并且两者匹配，那么长度等于
F[i-1][j-1]+1；
我们从所有枚举的结果中找到一个最大的即可。
Markdown

//DP / LCS / 50 分数据规模限制
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
{
// 分三种情况进行讨论
f[i][j] = max(f[i-1][j], f[i][j-1]);
if(p[i] == q[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
}
int ans = f[n][n];
在这道题目里，LCS问题是可以转化为LIS的：

假定某一个序列为[1 2 3 ... N]，那么答案则是另一个序列的LIS；
3 2 1 4 5
1 2 3 4 5
但如果两个序列都不是[1 2 3 ... N] 呢？通过转化使一个序列变成
它，而答案不变。
5 3 4 1 2 -> 1 2 3 4 5
3 5 1 2 4 -> 2 1 4 5 3
注意：原题给的序列是1-n不重复的，但是如果有重复元素，就不能这么做啦。乖乖用最长公共子序列吧……
// DP / LCS
// 初值：在遇到最小值的问题，一定要小心初值的处理
f[0][0] = 0;
for(int i = 1; i <= n; ++ i) f[i][0] = i * k;
for(int j = 1; j <= m; ++ j) f[0][j] = j * k;
for(int i = 1; i <= n; ++ i) // n 为第一个串的长度
for(int j = 1; j <= m; ++ j) // m 为第二个串的长度
{
// 三种情况
f[i][j] = min(f[i-1][j], f[i][j-1]) + k;
f[i][j] = min(f[i][j], f[i-1][j-1] + abs(p[i-1] - q[j-1]));
}
int ans = f[n][m];
二维平面问题

Luogu 2733 : 家的范围
农民约翰在一片边长是N (2 <= N <= 250) 英里的正方形牧场上放牧他的奶牛。(因为一些原因，他的奶牛只在正方形的牧场上吃草。) 遗憾的是, 他的奶牛已经毁坏一些土地。( 一些1 平方英里的正方形)
* 农民约翰需要统计那些可以放牧奶牛的正方形牧场(至少是2x2的,在这些较大的正方形中没有一个点是被破坏的，也就是说，所有的点都是“1”)。
* 你的工作要在被供应的数据组里面统计所有不同的正方形放牧区域
(>=2x2) 的个数。当然，放牧区域可能是重叠。
状态设计：设状态F[i][j] 为以(i,j) 位置为右下角，最大的一个正
方形区域。
考虑位置F[i-1][j] 与F[i][j-1]；
则有F[i][j] <= F[i-1][j] + 1; F[i][j] <= F[i][j-1] + 1;
Markdown

考虑* 号位置的最大区域，不可能超过4
很明显，F[i][j-1] 与F[i-1][j] 中较小值限制了最大区域的边长。
Markdown

考虑* 号位置的最大区域，不可能超过3
但在某些情况下，仅考虑F[i][j-1] 与F[i-1][j] 显然不全面,还需要考虑F[i-1][j-1]。
Markdown

在两个区域中，左上边界的还没有考虑入内
所以我们可以得到最终的表达式：
F[i][j] = MIN (F[i-1][j],
F[i][j-1], F[i-1][j-1]) + 1 (当(i,j) 不为障碍时)
Markdown

一个正方形的大小需要考虑A,B,C 三个位置
//DP
//边界初值
for(int i = 0; i < n; ++ i) f[i][0] = (a[i][0] == '1');
for(int j = 0; j < n; ++ j) f[0][j] = (a[0][j] == '1');
for(int i = 1; i < n; ++ i)
for(int j = 1; j < n; ++ j) if(a[i][j] == '1') // 如果是非障碍
{ // 计算
f[i][j] = min( min(f[i-1][j], f[i][j-1]), f[i-1][j-1] ) + 1;
t[ f[i][j] ] ++;
}
for(int i = n; i; i --) // 统计所有方形的数目
t[i-1] += t[i];
for(int i = 2; i <= n; ++ i) if(t[i]) // 输出结果
cout << i << "␣" << t[i] << endl;
区间动态规划

Luogu 2734 : 游戏
有如下一个双人游戏:N(2<=N<=100)个正整数的序列放在一个游戏平台上，游戏由玩家1 开始，两人轮流从序列的任意一端取一个数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。
编一个执行最优策略的程序，最优策略就是使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。
Markdown

如图为最优策略
状态设计方法为：F[i][j] 表示假若只用第i 个数与第j 个数之间的
数进行游戏，先手能获得的最高的分为多少。
* 我们可以根据先手取左边还是取右边来决定哪种情况得分高。
! 当先手取完一件后，先后手发生交换，而问题是类似的。

Markdown

枚举区间长度(2-n)，然后按照上图方式递推。

// T19 : 游戏
cin >> n;
for(int i = 1; i <= n; ++ i)
cin >> a[i],
s[i] = s[i-1] + a[i]; // s 代表前缀和
for(int i = 1; i <= n; ++ i) f[i][i] = a[i]; // 初值
for(int k = 2; k <= n; ++ k) // 按照序列的长度进行枚举
for(int i = 1, j; i + k - 1 <= n; ++ i)
{
j = i + k - 1;
f[i][j] = max ( // 两者取较大值
s[j] - s[i] - f[i+1][j] + a[i],//左边总和-先手玩家得分+自己新得分=总得分
s[j-1] - s[i-1] - f[i][j-1] + a[j]//从另一个方向
);
}
// 输出答案
cout << f[1][n] << "␣" << s[n] - f[1][n] << endl;
加分二叉树

Luogu 1040 : 加分二叉树
设一个n 个节点的二叉树tree 的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree 的左子树的加分× subtree 的右子树的加分＋ subtree 的根的分数。

若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。
不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要
求输出:
1) tree 的最高加分
2) tree 的前序遍历
设F[i][j] 为只用第i 个数到第j 个数构成的加分树的最大权值。
枚举根节点，这样就化成了左子树和右子树的问题，求最优解即可。
状态转移方程：F[i][j] = MAX ( F[i][k-1] * F[k+1][j] + A[k] )
Markdown

for(int i = 1; i <= n; ++ i) f[i][i] = a[i];
for(int i = 0; i <= n; ++ i) f[i+1][i] = 1;
for(int k = 1; k < n; ++ k)
for(int i = 1; i + k <= n; ++ i)
{
int j = i + k;
for(int l = i; l <= j; ++ l)
f[i][j] = max(f[i][j], f[i][l-1] * f[l+1][j] + a[l]);
}
int ans = f[1][n];
问题：如何求出树的前序遍历(树的形态)？
另外记录一个数组G[i][j]，代表F[i][j] 取最大值的时候，根节点
是什么。这样就可以通过递归来求出树的前序遍历。

for(int i = 1; i <= n; ++ i) f[i][i] = a[i], g[i][i] = i; // 边界值
for(int i = 0; i <= n; ++ i) f[i+1][i] = 1;
for(int k = 1; k < n; ++ k)
for(int i = 1; i + k <= n; ++ i)
{
int j = i + k;
for(int l = i; l <= j; ++ l)
{
LL t = f[i][l-1] * f[l+1][j] + a[l];
if(t > f[i][j]) f[i][j] = t, g[i][j] = l; // 记录最优的根
}
}
// T25 : 加分二叉树
// 递归输出x 到y 这个树的前缀遍历
void dfs(int x, int y)
{
if(x > y) return;
int l = g[x][y]; // l 为根
cout << l << "␣"; // 先输出l
dfs(x, l-1), dfs(l+1, y); // 再输出子树的值
}
...
// 输出答案
dfs(1, n);
过程型状态划分

Luogu 1057 : 传球游戏
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师在此吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m 次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1 号、2 号、3 号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1 和1->3->2->1，共2 种。
分析：这道题目十分容易用搜索解决。为什么？

因为题目已经明确给定了过程：传球的次数。
因为这个过程是一定按照顺序进行的，所以可以直接写出状态：
设状态F[i][j] 为传到第i 次，现在在第j 个人手上的方案数。
很显然F[i] 只和F[i-1] 有关；因为题目已经规定好了传递顺序。
这一类的过程型问题只需要找出事情发展的顺序，就可以很简单的写出状
态与转移方程。
// T26 : 传球游戏
f[0][1] = 1; // 初值
for(int i = 1; i <= m; ++ i)
{
f[i][1] = f[i-1][2] + f[i-1][n]; // 头与尾需要特殊处理
f[i][n] = f[i-1][n-1] + f[i-1][1];
for(int j = 2; j < n; ++ j) // 转移只和i-1 有关系
f[i][j] = f[i-1][j-1] + f[i-1][j+1];
}
int ans = f[m][1];
序列型状态划分

Luogu 1018 : 乘积最大
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1 个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
例如，有一个数字串：312，当N=3，K=1时会有以下两种分法：
1) 3×12=36
2) 31×2=62
符合题目要求的结果是：31×2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
题目中要求把整个序列有序地切分成K+1 个部分。

状态设计：设我们把前F[i][j]为前i个数字切成j部分所能得到的最大乘积。
很显然这时候我们只需要通过枚举最后一部分的数字有多大，就能得到结果乘积了。(满足最优性)
// T20 : 乘积最大（DP）
++ k; // K+1
f[0][0] = 1; // 初值（后面有调用）
for(int i = 1; i <= n; ++ i) // 枚举长度
for(int j = 1; j <= k; ++ j) // 枚举切割部分
for(int l = 0; l < i; ++ l) //枚举前一块的最后位置（可以为0）
f[i][j] = max(f[i][j], f[l][j-1] * val(l+1, i));
// 答案
cout << f[n][k] << endl;
为什么不枚举i,j,k？
不会需要中间一块需要被截开的情况，所以没有必要求出中间一块[i,j]的最大乘积。

Luogu 1043 : 数字游戏
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。
游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m 个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k 最大或者最小。
例如，对于下面这圈数字（n=4，m=2）：
要求最小值时，((2-1)mod10)×((4+3)mod10)=1×7=7，要求最大值时，为((2+4+3)mod10)×(-1mod10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。
环形序列：第一个位置不一定是开头，有可能位于序列的中间。
解决方法：枚举每一个位置，把它当作开头算一遍，得到的结果取最大值即为答案。
Markdown

复制序列一次，以每个数为开头算一次
O(n^3)

//DP
void work(int *a)
{
s[0] = 0; // 预处理前缀和
for(int i = 1; i <= n; ++ i) s[i] = s[i-1] + a[i];
for(int i = 0; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
f[i][j] = 0, g[i][j] = INF; // 初值
f[0][0] = g[0][0] = 1; // 初值
... // DP 过程
//DP
void work(int *a) //传指针
{
... // 初值，预处理
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
for(int k = 0; k < i; ++ k)
{ // 分别计算最大值和最小值
// 问题：为什么f 不用判断而g 需要判断
f[i][j] = max(f[i][j], f[k][j-1] * (((s[i] - s[k]) % 10 + 10) % 10));
if(g[k][j-1] != INF) // g[k][j-1] = INF 代表什么
g[i][j] = min(g[i][j], g[k][j-1] * (((s[i]-s[k]) % 10 + 10) % 10));//防止为负数
}
amax = max(amax, f[n][m]);
amin = min(amin, g[n][m]);
}
//DP
// 主程序
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
cin >> a[i], a[n+i] = a[i]; // 复制一遍
amax = 0;
amin = INF; // 初值
// 以每个位置开始计算
for(int i = 1; i <= n; ++ i) work(a + i - 1);//传指针，从特定位开始
cout << amin << endl << amax << endl;
Luogu 1063 : 能量项链
在Mars 星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。
需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4 颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号#表示两颗珠子的聚合操作，(j#k) 表示第j，k 两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4#1)=10*2*3=60
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4#1)#2)#3）=10*2*3+10*3*5+10*5*10=710
环形序列：枚举每一个位置，把它当作开头算一遍，得到的结果取最大值即为答案。
那么我们只需要考虑线性序列的问题了.

状态设计：设F[i][j]为把i到j之间的珠子合并起来，所能释放的最大能量。

问题：为什么不能只设F[i] 代表前i 个珠子合并的最大能量。
和合并的方式有关。
状态转移：枚举最后一颗和i，j 一同合并的珠子k。
Markdown

//DP
int work(int *a) // 对一段线性序列进行DP
{
for(int i = 0; i <= n; ++ i)
for(int j = 0; j <= n; ++ j) f[i][j] = 0;
for(int s = 2; s <= n; ++ s) // 动态规划
for(int i = 0; i + s <= n; ++ i)
{
int j = i + s;
for(int k = i + 1; k < j; ++ k) // 枚举中间的一颗
f[i][j] = max(f[i][j],
f[i][k] + f[k][j] + a[i] * a[k] * a[j]);
}
return f[0][n]; // 答案
}
Luogu 1077 : 摆花
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n 种花，从1 到n 标号。为了在门口展出更多种花，规定第i 种花不能超过ai 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
2 种花，要摆4 盆
第一种花不超过3 盆，第二种花不超过2 盆
答案：2
状态设计：设F[i][j] 为摆到第i 种花，共摆了j 盆，的总方案数
可以用前缀和优化。

//DP
f[0][0] = 1;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
for(int k = 0; k <= j && k <= a[i]; ++ k)
f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;
int ans = f[n][m];

Luogu 1103 : 书本整理
Frank 是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k 本书，使得书架可以看起来整齐一点。
书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有4 本书：
1x2 5x3 2x4 3x1 那么Frank 将其排列整齐后是：
1x2 2x4 3x1 5x3 不整齐度就是2+3+2=7
已知每本书的高度都不一样，请你求出去掉k本书后的最小的不整齐度。
第一种思路：
第一步：先把书本按照高度排序！

状态设计：从N 本书选出N-k 本书；设F[i][j] 为从前i 本书选出j 本书的最小的不整齐度。
状态转移：讨论第i 本书选不选？
上一种方法行不通！

为什么？我们需要计算选出相邻两本书之间的宽度的差的绝对值。
状态设计：从N 本书选出N-k 本书；设F[i][j] 为从前i 本书选出j 本书的最小的不整齐度，并且第i 本书必须要选。
状态转移：上一本书选的是什么？
// T23 : 书本整理(DP)
int m = n - k; // 共选出m 本书
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
f[i][j] = INF; // 初值
for(int i = 1; i <= n; ++ i) f[i][1] = 0;
// 初值，第一本书没有前一本，为0
for(int i = 2; i <= n; ++ i)
for(int j = 2; j <= m; ++ j)
for(int l = 1; l < i; ++ l) // l 为上一本书
f[i][j] = min(f[i][j], f[l][j-1] + abs(a[i] - a[l]));
int ans = INF;
for(int i = 1; i <= n; ++ i) ans = min(ans, f[i][m]);
// 答案：最后一本书可以是任意一本
树形DP

Luogu 1472 : 奶牛家谱
农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3<=N<200)。这些二叉树有如下性质:每一个节点的度是0 或2。度是这个节点的孩子的数目。
树的高度等于K(1 有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的,那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901 的余数。
5 个节点，高度为3
答案：可能的家谱树个数为2
Markdown
状态设计：看题说话（十分简单），设F[i][j]为i个节点高度为j的树，一共有多少种方案。

问题：如何进行状态转移？
分成左右两棵子树。
Markdown'
状态转移：枚举子树的状态
限制：注意要满足深度的限制

Markdown

如图所示，必须保证一棵子树的深度为j-1
Markdown

如图所示，右子树也是可以的
状态转移：F[i][j] =Σ(k 为左子树大小，l为右子树深度)+ F[k][j-1 ]*F[i-k-1][l]*2 (l < j-1) (左右子树只有一棵深度为j-1，直接翻倍)+F[k][j-1]*F[i-k-1]j-1

可以用前缀和优化。

//DP O(n^4)
f[1][1] = 1; // 初值，深度为1 的子树只有一种情况
for(int i = 3; i <= n; ++ i)
for(int j = 2; j <= m; ++ j)
for(int k = 1; k < i; ++ k)
{
for(int l = 1; l < j - 1; ++ l) // l < j-1，结果乘2
f[i][j] = (f[i][j] + f[k][j-1] * f[i-k-1][l] * 2 % MOD) % MOD;// 左右子树深度均为j-1
f[i][j] = (f[i][j] + f[k][j-1] * f[i-k-1][j-1] % MOD) % MOD;
}
int ans = f[n][m]; // 答案
//DP / 前缀和优化 O(n^3)
f[1][1] = g[1][1] = 1;
for(int j = 2; j <= m; ++ j) g[1][j] = 1; // 前缀和初始化
for(int i = 3; i <= n; ++ i)
for(int j = 2; j <= m; ++ j)
{
for(int k = 1; k < i; ++ k)
{// 注意到把深度小于j-1的方案全部加起来利用前缀和可以略去枚举过程
f[i][j] = (f[i][j] + f[k][j-1] * g[i-k-1][j-2] * 2 % MOD) % MOD;
f[i][j] = (f[i][j] + f[k][j-1] * f[i-k-1][j-1] % MOD) % MOD;
}
g[i][j] = (g[i][j-1] + f[i][j]) % MOD; // 前缀和计算
}
int ans = f[n][m];
Luogu 1122 : 最大子树和
一株奇怪的花卉，上面共连有N朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。
Markdown

问题转化：在这棵树中取出若干个连通的节点，使得权值之和最大。

观察：如下图，根节点为0。假如我们必须要取根节点0；同时它有三个儿子，权值分别为2，0，-3；则我们能取得的最大的权值是多少？
贪心地，我们只取不小于0 的节点。
算法思想：贪心的只取不小于0 的儿子。
状态设计：设F[i]为只考虑以i为根的这棵子树，并且必定要取i这个点，可能达到的最大权值是多少。
状态转移：把儿子中F[x ] 大于0 的加起来即可。(贪心选取）
Markdown
//DP
void dfs(int x, int y = 0) // y 代表父亲节点
{
f[x] = a[x]; // x 节点必取
for(unsigned i = 0; i < e[x].size(); ++ i)
{
int u = e[x][i];
if(u == y) continue; // 当u 不为父亲节点
dfs(u, x); // 递归求解儿子节点的f 值
// 当儿子权值大于0，则加上
if(f[u] >= 0) f[x] += f[u];
}
}
//DP
//主程序
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int i = 1, x, y; i < n; ++ i)
{
cin >> x >> y; // 树边
e[x].push_back(y); // 增加树边
e[y].push_back(x); // 增加树边
}
dfs(1); // 递归求解f 值
int ans = a[1];
for(int i = 1; i <= n; ++ i) ans = max(ans, f[i]); // 答案取最大的一个
cout << ans << endl;
Luogu 2014 : 选课
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b 的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M 门课程学习，问他能获得的最大学分是多少？
下图所示：每个节点代表一节课；父亲代表他的先修课；红颜色代表选上的课。左边是一种合法的选课方式；而右边则是一种不合法的选课方式，2 的先修课1 没有选上。
Markdown
问题观察：我们可以观察得到，根节点的课一定是要选的；并且选的节点是和根节点联通的。(否则不符合选课规则)
状态设计：设F[i][j]为，对于每节点i，只考虑自己的子树，一共选了j 节课，所能得到的最大权值是多少。
Markdown
状态转移：假设i只有两棵子树，那么我们可以枚举在其中一棵子树中，我们一共选了几门课：
F[i][j] = MAX (F[u][k] + F[v][j-k-1]) + A[i]
Markdown

状态转移：假设i有超过两棵子树，我们可以使用逐次合并的方法：先合并前两棵子树，然后将其视作一棵，再与余下的子树继续合并。

Markdown

//DP
void dfs(int x) // 处理根节点为x 的子树
{
int *dp = f[x]; // 小技巧，用dp 来代替f[x] 数组
for(unsigned i = 0; i < e[x].size(); ++ i)
{
int u = e[x][i];
dfs(u); // 处理儿子节点的子树
// 合并操作
// 将已经合并的子树信息存放到dp 数组当中
for(int j = 0; j <= m; ++ j) tp[j] = 0; //tp：临时数组
for(int j = 0; j <= m; ++ j) // 从已经合并的选j 门
for(int k = 0; j + k <= m; ++ k) // 从u 子树中选k 门
tp[j + k] = max(tp[j + k], dp[j] + f[u][k]);
for(int j = 0; j <= m; ++ j) dp[j] = tp[j]; // 复制过来
}
...
//DP
void dfs(int x) // 处理根节点为x 的子树
{
...
// 必须要选根节点这一门
for(int j = m; j; -- j) dp[j] = dp[j-1] + a[x];
dp[0] = 0;
}
// T30 : 选课(DP)
// 主程序
cin >> n >> m, ++ m;
for(int i = 1, fa; i <= n; ++ i)
cin >> fa >> a[i], e[fa].push_back(i);
// 我们设所有没有先修课的父亲为0 号
// 这样结果是一样的，而且必须要选0 号课程
dfs(0); // 根节点出发，递归
cout << f[0][m] << endl; // 在根节点多取m 门课
状压DP

状态压缩DP：利用位运算来记录状态，并实现动态规划。
问题特点：数据规模较小；不能使用简单的算法解决。

Luogu 1879 : 玉米田
农场主John 新买了一块长方形的新牧场，这块牧场被划分成M 行N列(1≤M≤12;1≤N≤12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
1 1 1
0 1 0 (1 代表这块土地适合种草)
总方案数：9
问题限制：没有哪两块草地有公共边
考虑动态规划：如何划分状态？

从上到下，从左到右？
记录F[i][j] 为(i,j) 选择在这个位置种草的方案数？
问题：如何转移？我们只能限制左边的位置不能种草；不能限制上面的位置不能种草。
划分状态：考虑用行来划分状态；第i行的状态只取决于第i-1 行。
Markdown
状态表示：如何表示一行的种草状态？

二进制位：将一整行看作是一个大的二进制数，其上为1 表示种了草，0表示没有种草。
这样，我们可以用一个数来表示一行的种草状态；
Markdown
例如，在一行的第一个位置和第四个位置种草，则可以用18 来表示这种状态
状态设计：设F[i][j] 为已经处理到第i 行，且第i行的状态是j，的总方案数。(其中j 为一个大的二进制数)

状态转移：枚举前一行的种草状态k，如果没有产生冲突，则加上F[i][j] =ΣF[i-1][k]
问题：如何判断两个状态是否冲突？如何运用二进制运算？
Markdown
解决方案：采取与运算；如果两个状态是冲突的，则肯定有一位上都为1，and 的结果肯定不为0；否则若结果为0，则代表状态不冲突.
Markdown
下一个问题：如何判断当前状态是合法的？
1) 没有占有障碍物：和判断两个状态是否冲突是类似的。
2) 左右位置判断：与上一行判断冲突，我们只考虑到了上下位置不可能同时种草，但还没有考虑左右的情况。
解决方案： j & (j«1) = 0 且j & (j»1) = 0
Markdown
//状态压缩DP
const int N = 13; // 边长
const int S = (1 << N) + 5; // 二进制状态数
int a[N][N]; // 棋盘数组
int s[N]; // 每一行空地的状态
int f[N][S]; // 动态规划数组
int g[S]; // 标记一个状态是否合法
// 主过程
ts = 1 << m; // 总状态数
for(int i = 0; i < ts; ++ i) // 判断左右位置
g[i] = ((i & (i<<1)) == 0) && ((i & (i>>1)) == 0);
// T31 : 玉米田（状态压缩DP）
f[0][0] = 1; // 初值！
for(int i = 1; i <= n; ++ i) // 枚举行
for(int j = 0; j < ts; ++ j) // 枚举这行的状态
if(g[j] && ((j & s[i]) == j)) // 状态本身合法且不占障碍物
for(int k = 0; k < ts; ++ k) // 枚举上一行的状态
if((k & j) == 0) // 如果不冲突
f[i][j] = (f[i][j] + f[i-1][k]) % MOD;
int ans = 0;
for(int j = 0; j < ts; ++ j)
ans = (ans + f[n][j]) % MOD; // 答案加起来
// T31 : 玉米田（状态压缩DP）
// 读入棋盘状态
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j) cin >> a[i][j];
// 预处理每一行的状态
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
s[i] = (s[i] << 1) + a[i][j];
Luogu 1896 : 互不侵犯
在N×N 的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8 个格子。
3 2 (在3×3 的棋盘内放置2 个国王)
总方案数：16
状态设计：设F[i][j][k] 为已经处理到第i 行，且第i 行的状态是j，现在一共放置了k 个国王的总方案数。(其中j 为一个大的二进制数)

状态转移：枚举前一行的放置国王状态为l，如果没有产生冲突，则加上(其中x 为状态j 的国王数)
F[i][j][k] =ΣF[i-1][l][k-x]
问题：如何判断两个状态是否冲突？如何运用二进制运算？
Markdown

//状态压缩DP
const int N = 10;
const int S = (1 << N) + 5; // 二进制状态数
int cnt[S]; // 记录一个状态有多少个1
int g[S]; // 记录一个状态是否合法
int h[S];
LL f[N][S][N*N]; // 动态转移状态
//状态压缩DP
ts = 1 << n;
for(int i = 0; i < ts; ++ i)
{
g[i] = ((i & (i<<1)) == 0) && ((i & (i>>1)) == 0);
h[i] = i | (i << 1) | (i >> 1); // h：一个状态把它左右都占据之后的状态
cnt[i] = cnt[i>>1] + (i&1); // 计算多少个1
}
//状态压缩DP
f[0][0][0] = 1; // 初值
// 顺推
for(int i = 0; i < n; ++ i) // 行数
for(int j = 0; j < ts; ++ j) // 这一行状态
for(int l = 0; l <= k; ++ l) if(f[i][j][l]) // 枚举个数
for(int p = 0; p < ts; ++ p) // 枚举下一行
if(g[p] && ((h[p] & j) == 0))
// 如果是合法状态，且不冲突
f[i+1][p][l + cnt[p]] += f[i][j][l];
LL ans = 0; // 答案
for(int j = 0; j < ts; ++ j) ans += f[n][j][k];
Codeforces 453B : Little Pony and Harmony Chest
我们称一个正整数序列B 是和谐的，当且仅当它们两两互质。
给出一个序列A，求出一个和谐的序列B，使得
Σ|Ai-Bi|最小。
问题思考：一个和谐的序列两两互质，满足什么性质？

它们分解质因数后，没有两个数拥有相同的质因子。
状态构思：如果我已经决定完前i个数是多少，现在要决定下一个数，需要满足什么限制？——不能有和前面重复的质因子。
这代表我们需要记录下，目前已经用了哪些质因子了。
状态设计：设F[i][j]为，已经决定完前i个数是多少，而且已经用了状态为j 的质因子了，现在的最小权值差是多少。
如何状态压缩？2,3,5,7,11,...；一个代表一个二进制位；用了是1，没有是0。
// T35 : CF453B （状态压缩DP）
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
// 预处理质数
for(int i = 2; i < M; ++ i)
{
if(!fg[i]) p[++p[0]] = i;
for(int j = 1; j <= p[0] && i * p[j] < M; ++ j)
fg[i * p[j]] = 1;
}
// 预处理每个数的质因子所代表的状态
for(int i = 1; i < M; ++ i)
{
g[i] = 0;
for(int j = 1; j <= p[0]; ++ j)
if(i % p[j] == 0) g[i] |= 1 << (j-1);
}
// T35 : CF453B （状态压缩DP）
// 动态规划主过程
int ns = 1 << p[0];
// 初值：最大值
for(int i = 1; i <= n + 1; ++ i)
for(int j = 0; j < ns; ++ j) f[i][j] = S;
f[1][0] = 0;
for(int i = 1; i <= n; ++ i) // 枚举位置
for(int j = 0; j < ns; ++ j) if(f[i][j] < S) // 枚举状态
for(int k = 1; k < M; ++ k) // 枚举这个位置的数
if((g[k] & j) == 0) // 如果之前没有出现过
{
// 计算最优值
int t = f[i][j] + absp(k - a[i]);
if(t < f[i+1][g[k] | j]) // 更新最优值
f[i+1][g[k] | j] = t,
opt[i+1][g[k] | j] = k;
}
// T35 : CF453B （状态压缩DP）
// 最优值输出
int ansp = S;
int ansm = 0;
for(int j = 0; j < ns; ++ j) // 记录最优值所对应的状态
if(f[n+1][j] < ansp) ansp = f[n+1][j], ansm = j;
for(int i = n+1; i > 1; -- i) // 依次向前查询
{
b[i-1] = opt[i][ansm];
ansm ^= g[b[i-1]];
}
for(int i = 1; i <= n; ++ i) cout << b[i] << "␣";
cout << endl;
Luogu 2831[noip2016] : 愤怒的小鸟
欢迎访问我的博客看题解233：【noip2016】愤怒的小鸟(angrybird) 思路+代码

分享一个有趣的题面：
Markdown
@zhx学长

day 4

数据结构

队列

（打心眼里不想自己写，墙裂推荐stl queue）
把老师的代码PO上来好了……

void push(int x)
{
q[tail++]=x;
}
void pop()
{
++head;
}
int front()
{
return q[head];
}
void queue()
{
head=tail=0;
push(1), push(2), push(3);
printf("%d\n", front());
pop(), push(4), pop();
printf("%d\n", front());
}
老师讲了三道题。第一道题是铁轨的，直接用栈模拟就行。
栈

（我也不想自己写，同推荐stl stack）

void push(int x)
{
st[tp++]=x;
}
void pop()
{
--tp;
}
int top()
{
return st[tp-1];
}
void stack()
{
tp=0, push(1), push(2), push(3);
printf("%d\n", top());
pop(), pop();
printf("%d\n", top());
push(4);
printf("%d\n", top());
}
没什么特别想说的，有一道题还有点意思

[JSOI2008]最大数
维护一个队列，有m种操作
Q L 查询队列末尾L个中最大的数
A N 将N加上t，其中t是最近一次查询操作的答案，并对D取模，插入到队列末尾
m<200000
首先操作只有在末尾添加数，所以可以想到自底向上递减的单调栈。
查询L个中的最大值：由于栈内元素是单调的，可以利用二分查找，找到对应位置的最大值。
添加元素的时候：并不需要考虑比它还小的值了，直接把栈顶比当前元素小的值弹出就行。
O（nlogn）。

单调队列

处理：连续k个数字中的最大值的最小值

POJ2823 Sliding Window
给定一个长度为N 的数组，一个长度为K的滑动窗口从最左端移至最右端，窗口共有N − K + 1 种可能的位置。对于每种窗口可能的位置，求出窗口覆盖的K个数当中的最小值和最大值。
引入单调队列：队首具有队列的性质，队尾具有栈的性质。
以求最大值为例：

从左到右依次扫描每个滑动窗口
维护一个单调递减队列，同时记录每个元素的位置
将当前元素加入队列，注意维护当前队列的单调性。即从队尾删除那些比该元素靠前，又比该元素小的元素（它们不可能是之后窗口的最大值了）。这样就可以保证队列元素严格递减了。
如果队首元素与当前元素距离大于K（不属于当前窗口），则将其从队列中删除掉（之后再也不会出现在窗口中了）。
算法的复杂度为O(n)。每次输出队首元素就行啦。

//sliding window最大值部分
head = tail = 0;
for(int i=1; i<=n; i++)
{
for(; head < tail && q[head] <= i-w; ++head);
for(; head < tail && a[i] > a[q[tail-1]]; --tail);
q[tail++] = i;
maxa[i] = a[q[head]];
}
DAY 3 作业：https://cn.vjudge.net/contest/171552#overview
Q1:
简述题面：有个卡卡，有一堆信封。要用信封把卡一层层裹起来，卡+信封大小必须严格递增，求最多能包多少层+用哪几张信封包上。
暴力搜索能过（显然我也是暴搜过的）
然而我第一次写的DP代码错了orz……难过
思路好像没问题……？
首先把装不进去卡片的信封都扔掉。然后把所有的信封从小到大排序（结构体双关键字排序），当做最长上升子序列一样做就行……
如何记录用什么包上的？利用pre数组，状态转移的时候顺便记录一下当前的信封里面包了哪个信封。这部分代码这么写就行【自己写的……如果有误请指正qwq】

if(g[j]>=g[i])
{
g[i]=g[j];
pre[i]=j;
}
...
if(g[i]>=ansg)
{
ansg = g[i];
prei=i;
}
...
while(prei)
{
printf("%d ",prei);
prei=pre[prei];
}
Q2：
顺推的话时间复杂度太高，最好用逆推法。
利用前缀和优化。

Q3：状压DP
Q4：序列DP
Q5：树形DP
Q6：树形DP

//就对了一道题啊……qnq希望有人能来看看我的Q1DP代码……告诉我哪儿出问题了（哭泣

链表

扒定义：链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
与数组不同，链表插入|删除元素时间复杂度为O（1）。查询元素复杂度为O(n)。很多时候，我们可以用数组模拟链表。
为什么我把上面那句话划掉：指针才是王道啊，你们仔细想想，要是数组模拟的话，浪费的空间得有多大啊。回收起来多费劲啊……指针用完即回收，方便快捷，不耗时间，其实也不难理解，大家多欣赏欣赏指针的美，自然就会爱上它了//////

[usaco2006 nov] bad hair day
首先把奶牛按照顺序用双端链表连起来，之后从小到大枚举每头奶牛，求出这头奶牛在链表中的左端节点，之后把这个元素从链表中删除。
时间复杂度O(nlogn)

day 5

并查集

在一个博客上面看到了一个挺可爱的例子：
武林上有很多门派。有一天剑客A和法师B狭路相逢吵起来了，正要开打，突然想到万一是自己人打起来就不好了，于是就去问各自的上级。A问左护法，B问右护法，左右护法也不知道，然后就去问教主，发现是同一个教主，于是能够确定是同一个教的人了。A和B就开开心心地一起去喝酒了。
但是教主发愁啊，以后要是每次询问的时候，都要费事一点点找上级，那多不好……于是教主让每个人都改成直属于自己的，这样A,B下次再相遇的时候，只需要看看是不是同一个上级就行了。【路径压缩】
洛谷P1621 集合
枚举所有>=P的质因数，再枚举这个数的背书，将这些数所在的集合都用并查集并起来。
洛谷P2170 选学霸
把实力相当的人看做一个教里的，并成一个点，权值为人数。然后用01背包算就行啦
洛谷P1197 [JSOI2008]星球大战
加点容易删点难，直接一个一个点加就可以用并查集了。
洛谷P2024 食物链
使用并查集不够，选择带权并查集。0表示同类，1表示吃，-1表示被吃，简单相加%3就可以求得关系了。

堆

定义：一棵满足以下两个性质的二叉树：
1.父节点权值大于等于（大根堆）或小于等于（小根堆）任何一个儿子的权值。
2.每个节点的左子树和右子树都是一个堆。

二叉堆
可并堆
斜堆

//上面这些是什么我都不知道

堆是一棵完全二叉树，能够插入节点，删除节点，求最小值等。用数组保存二叉堆，根节点下标为1，左右儿子分别为2n-1,2n。
插入操作插入节点时，（以大根堆为例）为了保持堆的性质，一旦该点大于父节点，就将他与父节点交换，再比较父节点和它的父节点……
删除操作删除节点时，我们用二叉堆的叶子节点替换它，再删去叶子节点。然后再维护一下堆性质，每次和左右儿子中较小的比较，如果儿子比较小就交换两个节点。
查找操作查询时提取数组中第一项元素即可。

NOIP2004 合并果子
正解：双队列（快）
另一种解法：堆

[Usaco2009 Open]工作安排JOB//暂且没有找到这道题的链接
因为每一个工作的开始点都一样，所以可以倒着搜。从后往前每到一个时间点，就将在该点deadline的工作加入堆，再将堆中最大值弹出。

bzoj 2151 种树
首先把整个环用双向链表套起来，之后每次找到环上权值最大的节点，更新答案，之后将它的权值更新为该节点左右两个节点减去该节点权值，最后将左右两个节点从双向链表中删除即可。//求大佬讲解，这个地方不是很明白……

别忘了今天晚上画几个破图放上来！

可并堆

可并堆的优点：可以合并
可并堆有很多种，最常用的一种：左偏树
Markdown
在左偏树中，每个节点包含两个属性：权值和距离（dist）。除了之前二叉堆支持的操作以外，左偏树还支持合并（merge）操作。
左偏树的每个节点都满足做儿子的dist大于右儿子的dist，每个节点的dist的值即为该子树中与该节点最近的点的距离。
【简单粗暴：dist就是它右儿子的dist+1，叶子节点dist=0】
在合并两个左偏树的时候，用x表示根权值较小的左偏树，y表示另一棵左偏树，那么我们就把x的根作为合并后的根，再将x的右子树和y合并，作为合并后的右子树，最后再比较左右子树dist大小进行交换（维护左偏树性质）。
在删除最大|小值（堆顶元素）的时候，只要把根的左右儿子merge起来作为新的左偏树即可。
由于每个节点的左子树深度都大于右子树，所以dist=x的左偏树至少有2^x个节点。
左偏树不过是给原来的堆加了个dist，这样的话能让它多一个合并的功能，其它的性质都是不变的
单次操作时间复杂度O（logn）。

int merge(int x,int y)//x y是要合并的左偏树的两个根 返回值是新树的根
{
if(!x||!y)return x|y;//一个数|0还是那个数，判断是否为空树
if(v[x] rs[x]=merge(rs[x],y);//新的右子树是原来的
if(dist[rs[x]]>dist[ls[x]])swap(rs[x],ls[x]);//根据dist调整
dist[x]=dist[rs[x]]+1;//更新x的dist的值
return x;
}
int add(int x)
{
v[++cnt]=x;//先建一个只有一个节点的树（即建立一个新点）
dist[cnt]=0;
root=merge(cnt,root);//然后把这个数合并
}
int del()
{
root=merge(ls[root],rs[root]);
//合并一个节点的左儿子和右二子，就是删除这个点啦...
}
HDU1512 猴子打架
Markdown
用并查集维护朋友关系，对于每个并查集维护一个可并堆（大根堆），在两个猴子开始打架的时候提取这两个可并堆的最大值，修改后将两个可并堆合并起来并更新并查集信息。
时间复杂度O(nlogn)。

2809: [Apio2012]dispatching
问题相当于要对于每个子树求出最多有多少个最小数的和小于等于M。
考虑对整棵树进行DFS，对于每个子树用最大可并堆维护该子树中最小的和小于等于M的数。
对于任意一个节点，它的可并堆即为它几个子树的可并堆合并起来，之后删去最大的那些数，知道剩下所有数的和满足条件为止。
由于每个元素最多只会被删除一次，所以时间复杂度合法。
时间复杂度O(nlogn)。

void dfs(int x)
{
sum[x]=v[x];//sumbiaoshi 可并堆所有元素和
root[x]=x;//初始化x个只有一个节点的树，表示可并堆的根
//dist=0
num[x]=1;//元素数量
for(i=x的儿子)//处理儿子
{
dfs(i);
root[x]=merge(root[i],root[x]);
sum[x]+=sum[i];
num[x]+=num[i];
}
for(;sum[x]>m;)//处理当前节点
{
sum[x]-=v[root[x]];
root[x]=merge(ls[root[x]],rs[root[x]]);
num[x]--;//可并堆元素数量
}
}
树状数组

树状数组支持单点修改和前缀查询。通过加特技（？？？）可以让它支持更多操作
为了不断一分为二，引入一个辅助量：lowbit
假如有这么个数x，则C[x]=x-lowbit(x)+1~x所有元素权值的和。
lowbit(x)=x&-x 表示x这个数在二进制下的从右到左第一个1及后面的0.
比如4在二进制中是00000100，-4二进制表示为补码(-x=2^32-x)，就是10000100，他们两个通过与运算后的值是

00000100 &
10000100 =
00000100，即为4.所以lowbit(4)=4;
int lowbit(int x){return x&(-x)}
//c[x]=a[x-lowbit(x)+1]+...+a[x]
void add(int x,int y)
{
for(;x<=n;x-=lowbit(x))
{
c[x]+=y;
}
}
int ask(int x,int y)
{
int ans=0;
for(;x<=y;x+=lowbit(x))
{
ans+=c[x];
}
return ans;
}
//改点求段
void ADD(int x, int c)//改点
{
for (int i=x; i<=n; i+=i&(-i)) a[i] += c;//每次加上lowbit[i]，都是找到当前节点的父亲
}
int SUM(int x)//求段
{
int s = 0;
for (int i=x; i>0; i-=i&(-i)) s += a[i];//*1
return s;
}
*1：每次减去一个lowbit，都会得到前一个区间包含数字最多的那个点。比如说x当前为6，那么s+=（5~6）的权值和，减去lowbit以后x变为4，4包含了（1~4）的权值和，于是就非常高效啦
//lazytag,中午回头补
NOIP2013 火柴排队

要让a中第K大的和b中第K大的匹配。移动a,b与只移动一个没有区别，所以可以确定a,只移动b。
首先将a,b离散化，用Ai表示ai是a数组中第几大的，用Bi表示bi是b数组中第几大的。
之后定义数组C满足C[Ai]=i,定义D满足Di=C[Bi],表示b中第i项最终需要移动到哪一位。
发现移动步数相当于对D数组进行排序，只能移动相邻两项的最小步数。等价于求逆序对对数，从前向后枚举每一项，用树状数组维护，求出每一项之前比该项大的数的数量即可。

int main()
{
for(int i=1;i<=n;i++) A[i]=a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)A[i]=lower_bound(a+1,a+n+1,A[i])-a;
for(int i=1;i<=n;i++) B[i]=b[i];
sort(b+1,b+n+1);
for(int i=1;i<=n;i++) B[i]=lower_bound(b+1,b+n+1,B[i])-b;
for(int i=1;i<=n;i++)C[A[i]]=i;
//A[i]表示a[i]在a数组中是第几大的
//C[i]表示a数组中第i大的数的下标
for(int i=1;i<=n;i++)D[i]=C[B[i]];
//C[B[i]]表示a数组中第B[i]大的数的下标
//D[i]表示b数组中第i个数应该移动到哪个位置//一定为1~n的全排列
for(int i=n;i>=1;i--)
{
ans+=ask(D[i]),add(D[i],1);
}
}
野鸡题(???)
区间加一个数，区间求和
数据范围n<=100000;

用两个树状数组解决问题。给[l,r]增加x的权值的时候，在另一个树状数组上i-1处和r处加上x的权值。
注意考虑“0”的问题，因为树状数组算不了0.
在询问前x个数的和的时候只有r>x，l<=x的区间会发生问题，于是利用另一个树状数组来维护，在l加上x的权值，在r+1减去x的权值，就能快速求出满足这个条件的区间和了。
显然第二个树状数组的作用是类似与线段树中的"lazytag"的，思想就是用不到的值先不改，用到了再改。而且这样会很高效：假如当前区间之前减三，后来又加五，如果每次把区间内所有值都改了，那么既要给每个值减三，又要给每个值加五。还不如算好了这个区间总共是加二的，要访问子区间的时候往下传递这个tag：你要加二啦，就能省去很多不必要的麻烦了w

//差分数组【感谢HHM同学的代码赞助！】
/*可以差分数组，差分表示每一项减前一项
例如1 3 2 4 5，差分为1 2 -1 2 1
修改区间时，原数组每项都要变化
但差分数组只在l处权值x,在r+1处权值-x
在上例中，[3,4]+2，原数组变为1 5 4 6 5
但差分数组变为1 4 -1 2 3
/
void add(int x,int y) //添加a[x]并修改前缀和
{
for(;x<=n;x+=x&-x)
c[x]+=y;
}
//ask(r)-ask(l-1)表示[l,r]前缀和
int ask(int x) //询问前x个数的和
{
int y=0;
for(;x;x-=x&-x)
y+=c[x];
return y;
}
while(q--)
{
int t,l,r,x;
scanf("d%",&t);
if(t==1)
{
scanf("d%d%d%",&l,&r,&x);
add(l,x);
add(r+1,-x); //[l,r]增加x权值
}
else
scanf("d",&x),ask(x);//查询x权值
}
/用两个树状数组实现,例：
如1 2 3 4 5//下标
0 0 0 0 0//初值
改0 3 3 3 0//改后
0 3 6 9 9//前缀和
第一个树状数组 -3 0 0 12 0
前缀和：-3 -3 -3 9 9
我们发现此时只有[l-1][r-1]是错误的，其余前缀和不变
第二个用来修正，而其前缀和与原前缀和差为3 6 9，成等差数列
故开另一个树状数组 3 0 0 -3 0
前缀和 3 3 3 0 0
前缀和每一项乘以下标 3 6 9 0 0
加上上一个树状数组的前缀和 0 3 6 9 9
(上例中l=2,x=3)
实现：/
void add1(int x,int y) //添加a[x]并修改前缀和
{
for(;x<=n;x+=x&-x)
c[x]+=y;
}
void add2(int x,int y) //添加a[x]并修改前缀和
{
for(;x<=n;x+=x&-x)
d[x]+=y;
}
int ask1(int x) //询问前x个数的和
{
int y=0;
for(;x;x-=x&-x)
y+=c[x];
return y;
}
int ask2(int x) //询问前x个数的和
{
int y=0;
for(;x;x-=x&-x)
y+=d[x];
return y;
}
add1(l-1,-x(l-1));
add1(r,x*r);
add2(l-1,x);
add2(r,-x);
ask1(r)+ask2(r)r-(ask1(l-1)+ask2(l-1)(l-1))
SDOI2009 HH的项链
将所有询问按照R排序，从前向后枚举每个贝壳。
对于第i个贝壳求出前一个和它相同的贝壳F[i]，之后在树状数组上给[F[i]+1,i]这一段+1即可。
树状数组的区间+1可以变成在点F[i]+1上+1，在点i+1上-1。
询问时只要对于特定的r询问树状数组中l点的值即可。
时间复杂度O(nlogn)。

二叉搜索树

也叫平衡树（BST）。它或者是一棵空数，或者是具有下列性质的二叉树:
1.若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值。
2.若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；它的左，右子树也分别为二叉搜索树。
根据功能和实现上的差异可以分为以下几种：

基于旋转：splay,treap,AVL树……
基于重构：替罪羊树，朝鲜树
基于可并堆：fhq-treap
多数平衡树插入删除的时间复杂度为O(logn)，空间复杂度为O(n)。
treap
treap是一种平衡树，除了平衡树的特点以外，treap中每个结点还有一个随机的额外权值、
treap根据额外权值满足堆的性质，即每个结点左右儿子的额外权值都大于该节点。
在随机权值互不相等的情况下，权值与treap是一一对应的。
由于堆的权值是随机的，所以树的期望深度为logn。
我们主要运用旋转(rotate)来维护平衡树的性质。

Markdown

转一下，然后把右儿子换一下
容易发现旋转操作并不会改变平衡树的性质，只会让两个元素上下位置交换，所以插入点的时候，只要在treap中找到恰好能插入这个点的位置，将这个点插入，再通过rotate操作将他向上移动，直到满足堆的性质。（转来转去让它的左儿子比它小，右儿子比它大）
在删除点的时候，用rotate操作把当前点转移到叶子节点，删掉就行啦
单次操作O（logn）

void right_rotate(int p)//右旋
{
int q=dad[p],s=dad[q];
int b=rs[p];
ls[q]=b;
dad[b]=q;
dad[q]=p;
dad[p]=s;
rs[p]=q;
if(ls[s]==q)ls[s]=p;
else rs[s]=p;
}
void left_rotate(int p)//左旋
{
int q=dad[p];
int s=dad[q];
int t=rs[p];
dad[p]=s;
dad[q]=p;
dad[t]=q;
ls[q]=t;
rs[p]=q;
if(ls[s]==q)
ls[s]=p;
else
rs[s]=p;
}
无DAD版
void left_rotate (int &q,int p){
rs[q]=ls[p];
ls[p]=q;
q=p;
}
void right_rotate (int &q,int p){
ls[q]=rs[p];
rs[p]=q;
q=p;
}
void add(int x,int &cur)
{
if(!cur)
{
cur=++cnt;//cur表示一个节点的编号
v[cnt]=x;
R[cnt]=rand();
return ;//新建节点
}
if(x>V[cur])
{
add(x,rs[cur]);//向右儿子找
if(R[rs[cur]] }
else
{
add(x,ls[cur]);//向左儿子找
if(R[ls[cur]] }
}
void del(int x,int &cur)
{
if(V[cur]==x)
{
if(!ls[cur]||!rs[ur])
{
cur=ls[cur]|rs[cur];
return;
}
if(R[ls[cur]]>R[rs[cur]])
{
left_rotate(cur,rs[cur]);
del(x,ls[cur]);
}
else
{
right_rotate(cur,ls[cur]);
del(x,rs[cur]);
}
}
else if(x else del(x,rs[cur]);
}
add(x,root);
}
splay
splay也是一种平衡树，满足平衡树的所有性质。
它不能可持久化。
与treap不同的是，splay依赖双旋均摊来保证复杂度。
splay的基本操作函数splay(X)表示将x旋转到根。//只要x不是根就不断splay
splay函数中的旋转根据三种不同的情况进行分类讨论：
P：x的父亲

当P为根节点时：zip step操作：
1）当x为p的左儿子时，对x右旋；
2）当x为p的右儿子时，对x左旋。
当P不是根节点，且x和p同为左儿子或右儿子时进行zig-zig操作。
1）当x和p同为左孩子时，依次将p和x右旋；
2）当x和p同为右孩子时，依次将p和x左旋。
当p不是根节点，且x与p不同为左孩子或者右孩子时，进行zig-zag操作。
1）当p为左孩子，X为右孩子的时候，将x左旋以后再右旋。
2）当p为右孩子，X为左孩子的时候，将x右旋后再左旋。
Markdown

void splay(int x)
{
st[t=1]=x;
for(int y=x;!is_root(y);st[++t]=y=dad[y]);
for(;t;t--) if(rev[st[t]]) reverse(st[t]);
for(;!is_root(x);rotate(x))
if(!is_root(dad[x]))
s[0][dad[x]]==x^s[0][dad[dad[x]]]==dad[x]?rotate(x):rotate(dad[x]);
update(x);
}
int find_max(int cur)
{
for(;s[1][cur];cur=s[1][cur]);
return cur;
}
void combine(int cur,int cur1)
{
cur=find_max(cur);
splay(cur);
rs[cur]=cur1;
}
fhp-treap被老师吃辣！

替罪羊树：局部重构【第二快的平衡树】
最快的是RBT（红黑树）
朝鲜树：隔一段时间把树拍成一条链，然后再重构

BZOJ3224 普通平衡树
需要满足插入元素的操作，删除指定元素的操作，查询某数序号的操作，查询排名为x的数（维护子树大小），求x前驱的操作
【线段树多好】

BZOJ3223 文艺平衡树
维护有序数列，能够翻转区间。
利用splay,每次操作将区间[l,r]左侧点l-1旋转到根，将区间右端点r+1旋转到根的右儿子，这时区间对应的就是根右儿子的左儿子。给节点打上翻转标记即可。
//如果使用fhp-treap，我们可以先将区间通过两次split分离出来，打上标记再merge回去。

线段树

//偷偷告诉你们 指针写线段树 超~ ~ ~ ~ ~爽【其实没什么卵用】
//没有lazytag的线段树，和咸段树有什么区别……？

include

using namespace std;
void pushdown(int cur,int x)
{
cov[cur<<1]=cov[cur<<1|1]=cov[cur];
sum[cur<<1]+=cov[cur](x+1>>1);
sum[cur<<1|1]+=cov[cur](x>>1);
cov[cur]=0;
}
void update(int cur)
{
sum[cur]=sum[cur<<1]+sumpcur<<1|1];
}
void add(int l,int r,int L,int R,int x,int cur)//加点
{
if(L==r)
{
cov[cur]+=x;//cov就是lazytag
sum[cur]+=(r-l+1)*x;
return x;
}
int mid=l+r>>1;
if(L<=mid)add(l,mid,L,R,x,cur<<1);
if(R>mid)add(mid+1,r,L,R,x,cur<<1|1);
}
int query(int l,int r,int L,int R,int cur)
{
if(L<=l&&R>=r) return sum[cur];
if(cov[cur]) pushdown(cur,r-l+1);
int mid=l+r>>1,ans=0;
if(L<=mid)ans+=query(l,mid,L,R,cur<<1);
if(R>mid)ans+=query(mid+1,r,L,R,cur<<1|1);
return ans;
}
校门外的树3
相当于询问之前有多少个区间与询问区间有交集。等价于求之前总区间数-和询问区间没有交集的区间数。所以维护右边界<=任意l和左边界>=任意r的区间数就行啦。
用两棵线段树解决。
O(nlogn)

切水果
对于线段树上每个点维护两个值：cover,sum，分别表示这个节点是否被整个切了，和这个节点对应区间内剩余的水果数量。
下传cover标记即可w
O(nlogn)

算术天才⑨与等差数列
区间能组成等差数列的条件有两个。
1.max(l,r)-min(l,r)=(r-l)*k
2.区间[l,r]差分后的gcd为k
以上两项都可以用线段树轻松（？）维护
时间复杂度O(nlognlogn)

trie树

读作：踹树
trie数又称为单次查找树，是一种树形结构。
三个基本性质：
1.根节点不包含字符，除根节点以外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。
跪求帮debug【如果有的话】

//我自己写了个指针trie树……如果有问题请一定一定帮我指出来！

include

include

using namespace std;
struct node
{
char ch;
node son[26];
bool exist=0;
}
node now=new node;
node* root=now;
int add()
{
char c;
scanf("%c",&c);
if(c==' ') return 0;
while(c!=' '&&c!='\n')
{
if(now->son[c-'a']==NULL) now->son[c-'a']=new node;
now=now->son[c-'a'];
now->exist=1;
scanf("%c",&c);
}
now=root;
return 1;
}
bool find()
{
char c[2005];
scanf("%s",c);
int i=0;
int len=strlen(c);
while(c[i]!=' '||c[i]!='\n')
{
if(now->son[c[i]-'a']==NULL) return 0;
else now=now->son[c[i]-'a'];
if(c[i+1]==' '||c[i+1]=='\n')
{
if(now->exist==1) return 1;
}
}
return 0;
}
int main()
{
now->exist=1;
add();
if(find()) printf("yes");
else printf("no");
return 0;
}
HNOI2004 L语言
首先建trie树。
从前向后枚举文章中的每一个字母，再枚举trie树上的每一个节点，用F[i][j]表示trie树上编号为i的节点是否能匹配文章中的第j个字母。
状态转移方程：
F[i][j]=F[dad[i]][j-1]（s[j]=dad[i]=>i)
时间复杂度O(n*m)

USACO08DEC 秘密消息
题意：对于每条密码，求出有多少条信息是他的前缀，以及该密码是多少条信息的前缀。
所以我们可以对于信息建立一棵trie树，在树上的每个节点维护子树大小的信息，这样我们只要枚举每条密码，在trie树上找到对应位置，把访问过的信息数加上子树大小即为答案。
时间复杂度O（∑c[j]+∑b[i]);

//我困了……

最大异或和
用bi表示a数组的前缀异或和。
那么就是求max(bn xor bp-1 x)。由于bn和x固定，所以我们只要找出满足条件的bp-1即可。
对于bi的值建立可持久化trie树即可。
时间复杂度O(nlogn)。

可持久化trie树：

Markdown

这个网站写的超级好！
http://www.jianshu.com/p/e6050f01c4bc

Markdown

还有桶排序什么事儿……真的没懂orz

hash哈希

在算法竞赛中最常见的hash算法就是把它变成一个规模确定的，较小的数据。
在算法竞赛领域，hash算法主要用来对大规模数据进行比较。
应用的hash：
字符串hash
超大数hash
树hash

STL

stl我都是现用现看的orz
NOIP没有O2优化！

pair

include

using namespace std;
paira[100010];
int n,i;
int main()
{
scanf("%d",&n);
}
priority_queue//默认大根堆

include

using namespace std;
priority_queue q;
int n,i;
int main()
{
q.push(3);
q.push(5);
printf("%d\n",q.pop());
}
如何变成大根堆？
三种方法
一、存负数
二、结构体重载小于号
三、priority_queue,greater >

map

单次操作logn

include

include

include

using namespace std;
map mp;
map mmp;
map,int>mmmp;
mapkajfl;
mapmapu;
int main()
{
mmp[1926.1]=1234;
mmp[make_pair(123,233)]=1233;
mmp[asdf]=666;
i=1~n,mapu[x]++;
i=1~m,printfmapu[x];
}
set

功能简单的平衡树

set a;
set::iterator it;
it=a.begin();
for(;it //集合中元素不重复
//multiset里面可以重复，但是删除会把所有的都删掉
day6

图论

树的遍历
BFS：一开始队列中有一个点，将一个点出队，将它的子结点全都入队。
DFS：递归到一个点时，依次递归它的子结点。

无根树变有根树
选择一个点作为根结点，开始遍历。
遍历到一个点时，枚举每一条连接它和另一个点的边。若另一个点不是它的父结点，那就是它的子结点。递归到子结点。

并查集
处理不相交合并和查询问题。

邻接表存图：

const int N=1005;
const int M=10050;
int point[N],to[M],next[M],cc
void AddEdge(int x,int y)
{
cc++;
to[cc]=y;
next[cc]=point[x];
point[x]=cc;
}
void find(int x)
{
int now=point[x];
while(now)
{
printf("%d\n",now);
now=next[now];
}
}
int main()
{
}
链式前向星

struct edge
{
int end;
edge *suc;
edge(int _end,edge *_suc):end(_end),suc(_suc){}
}*head[N];
void add_edge(int u,int v)
{
head[u]=new edge(v,head[u]);
}
最小生成树

稀疏图用kruskal，稠密图用prim

prim:
先随机找一个点x作为根，然后维护一个集合S(存已经连通的点）和一个集合D（存当前连接S中所有点的线段，两端点都在S中的除外）
初始化S={x},D={x所连接的所有边};
每次在D中选一个权值最小的边，然后将该边删去。该边所连接的另一个点放入S中，直到S中点数=全部点数。
这里记顶点数v，边数e
邻接表:O(elog2v)

kruskal:
将边权从小到大排序，每次选择边权最小的，如果当前边连接的点已经连通了，就不选这条边。
利用并查集维护是否连通。
e为图中的边数
邻接表：O(elog2e)

//prim算法
const int N=1050;
const int M=10050;
struct Edge
{
int a,b,c;
} edge[M];
int n,m,ans=0;
bool black[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
black[1]=1;
for(int k=1;k {
int mind,minz=123456789;
for(int i=2;i<=m;i++)
{
if(black[edge[i].a]!=black[edge[i].b]&&edge[i].c mind=i;
minz=edge[i].c;
}
ans+=minz;
black[edge[mind].a]=1;
black[edge[mind].b]=1;
}
printf("%d\n",ans);
}
//kruskal算法
const int N=1050;
const int M=10050;
struct Edge
{
int a,b,c;
} edge[M];
int fa[N];
int n,m,ans=0;
bool cmp(Edge x,Edge y)
{
return x.c /* if(x.c else return 0;
*/
}
int getf(int x)
{
if(fa[x]!=x) fa[x]=getf(fa[x]);
return fa[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
sort(edge+1,edge+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int a=edge[i].a;
int b=edge[i].b;
a=getf(a);
b=getf(b);
if(a!=b)
{
ans+=edge[i].c;
fa[a]=b;
}
}
printf("%d\n",ans);
}
繁忙的都市
最小瓶颈生成树：连通的边只用<=x的。
在kruskal中，因为已经对边权从小到大排序，所以只能用前若干条边。

最短路算法

1.多源最短路
floyd
floyd算法是经典的DP。从i到j有两种可能：
1.i,j直接连通
2.i,j间接连通,其中经过k节点
设dis(i,j)为节点i到节点j之中最短路径的距离。对于每一个节点k，我们检查Dis(i,k)+Dis(k,j)

for(k=1;k<=n;k++)//枚举
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
O(n^3)
2.单源最短路
dijkstra
不能存在负权边！
算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
Markdown

include

include

const int N = 100500;
const int M = 200500;
int point[N],to[M],next[M],len[M],cc;
int dis[N]; //最短路长度
bool ever[N];
int n,m;
void AddEdge(int x,int y,int z)
{
cc++;
next[cc]=point[x];
point[x]=cc;
to[cc]=y;
len[cc]=z;
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
memset(dis,0x3f,sizeof dis);
dis[1]=0;
for(k=1;k<=n;k++)
{
int minp,minz=123456789;
for(i=1;i<=n;i++)
{
if(!ever[i])
{
if(dis[i] {
minz=dis[i];
minp=i;
}
}
}
ever[minp]=1;
int now=point[minp];
while(now)
{
int tox=to[now];
if(dis[tox]>dis[minp]+len[now])
dis[tox]=dis[minp]+len[now];
now=next[now];
}
}
for(i=1;i<=n;i++)
printf("%d\n",dis[i]);
}
//在寻找周围最小点的时候，用最小堆，就可以用O（log n）的时间找出最小的可到达点。
O(n^2+m)//m为边数
spfa
首先建立一个数组s,s[i]代表从始点到i点所需要的最短距离。
利用一个队列进行松弛操作：
初始化s[i]=0x3f3f3f3f;
首先将始点入队，然后将始点所连接的点x入队。入队的时候，将始点到x的距离d赋值给s[i]。对于始点所连接的所有点都进行如下操作，弹出队首元素。
访问队首元素y，将队首元素y所连接的所有的点都入队。假如其中一个点为z，则判定一下s[z]是否大于s[y]+< y,z >边权。如果大于，则松弛一下，把s[y]赋值为较小的那个。

include

include

const int N = 100500;
const int M = 200500;
int point[N],to[M],next[M],len[M],cc;
int dis[N]; //最短路长度
int que[N],top,tail;
bool in[N];
int n,m;
void AddEdge(int x,int y,int z)
{
cc++;
next[cc]=point[x];
point[x]=cc;
to[cc]=y;
len[cc]=z;
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
memset(dis,0x3f,sizeof dis);
dis[1]=0;
top=0;tail=1;que[1]=1;in[1]=1;
while(top!=tail)
{
top++;
top%=N;
int now=que[top];
in[now]=0;
int ed=point[now];
while(ed)
{
int tox=to[ed];
if(dis[tox]>dis[now]+len[ed])
{
dis[tox]=dis[now]+len[ed];
if(!in[tox])
{
tail++;
tail%=N;
que[tail]=tox;
in[tox]=1;
}
}
ed=next[ed];
}
}
for(i=1;i<=n;i++)
printf("%d\n",dis[i]);
}
O(km)//一百万以内数据

拓扑排序

//有向无环图
需要一个栈！
入度：有多少条边指向他
出度：有多少条边从他发出
先统计每个点的入度，假如a->b，则in[b]++;
用栈来维护入度=0的点。
若栈非空，则在栈中弹出一个元素（并输出），然后枚举这个点能到的每一个点将它的入度-1.如果入度=0，则压入栈中。
如果没有输出所有的顶点，则有向图中一定存在环
O(n+m)

//code from TYJ
const int N=100500;
const int M=200500;
int point[N],to[M],next[M],len[M],cc;//to[]和len[]下标匹配
int dis[N];
int xu[N];//stack
int que[M],top,tail;
int n,m;
int in[N];
void AddEdge(int x,int y,int z)
{
cc++;
next[cc]=point[x];
point[x]=cc;
to[cc]=y;
len[cc]=z;
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int a,b;
scanf("%d%d%d",&a,&b);
in[b]++;
AddEdge(a,b,);//单向边只用加一次
}
for(int i=1;i<=m;++i)
{
if(!in[i])
xu[++xu[0]]=i;/[0]是大小；
}
while(xu[0])
{
int now=xu[xu[0]];
xu[0]--;
ans[++ans[0]]=now;
int ed=point[now];
while(ed)
{
int tox=to[ed];
in[tox]--;
if(!in[tox]) xu[++xu[0]]=tox;
ed=next[ed];
}
}
if(ans[0] else for(int i=1;i<=n;++i)
printf("%d ",dis[i]);
}
构造排列：裸题//堆实现

构造排列Ⅱ

强连通分量

DFN[x] 编号为x的点的搜索顺序
LOW[x] x及x的子树通过至多一条不在树上的边能回溯到的最早节点
初始化LOW[x]=DFN[x] (假设只能回到自己）
搞个栈，搜到哪个点就把它入栈
深搜的时候执行
LOW[x]=min(DFN[x],LOW[x的儿子],DFN[x通过不在树上的单向边找到的点（非儿子）]);
若满足LOW[自己]=DFN[自己]，弹出自己和自己上面的所有东西
当dfs再次搜回某点（递归中间部分） 若仍满足初始化条件，则栈中该店及其上某点为一个强连通分量。
（保证没有一个包括该强连通分量中所有点的强连通分量）
最后，将根节点及根节点上方所有的点弹出，即为强连通分量
0->0->0
当1个强连通分量能通过1条单向边到达另一个强连通分量时，这两个强连通分量构成1个半连通分量.
多个强连通分量单向连成一条链时，这些强连通分量同属一个半连通分量
搞个cnt++;

while(1)
{
v=zhan.top();
bel[v]=cnt;
if(v==u) break;
zhan.pop();
}
LOW[x]=min(DFN[x],LOW[x的儿子],DFN[x通过不在树上的单向边找到的点（非儿子）]);

强连通分量的作用：缩点，把一个强连通分量变成一个点
当图里有一个环的时候，可以通过缩点变成一个点。

luogu p2002 消息扩散
查强连通分量的个数就行（缩点法），或者统计入度为0的人的数量。
或者用并查集搞搞……教主的数量就是需要通知的人的数量w

bzoj 1051 受欢迎的牛

连成有向图，然后用tarjan缩点求强连通分量。然后统计出度为0的节点的数量，如果唯一，则：
Markdown——by xcy

vijos 1906 联合权值

30% 枚举两个点，如果两个点之间的距离为2，就将权值加和；
60% 枚举从每个点出发，用dfs求距离
100% 枚举距离为2的两个点的最短路径中间的那个点，求他旁边相邻的节点的连通权值。求一个最大和一个次大，然后就可以计算出以改点为中心的连通权值。

有向无环图上的DP：
先做一遍拓扑排序，或者直接写记忆化搜索

欧拉路径：所有边只能经过一次，所有点必须经过一次
哈密特：所有点只能经过一次，所有边必须经过一次

7.20考试题

T1
DP过O(n)。
设dp[i][j]为必须选i的情况下，i之前的最大区间和。如果j=0，则代表在i之前没有更改为p。如果j=1，则代表在i之前或i时已经将i及之前的某数改为p了。
转移方程：dp[i][0]=max(dp[i-1][0],0)+a[i];
dp[i][1]= max(max(dp[i-1][0],0)+p,max(dp[i-1][1],0)+a[i]);

T2

T3
暴力搜索能过90%点[为什么我没敢开大数组（哭泣）]，打表可以用一个奇妙的方法：
用a-z表示0-25，A-Z表示26-51，则可以使用52进制来表示一个数字了。这样能节省很多空间w
DP：DP[i][j]表示最小操作次数，可以由DP[i][j-1]转移过来，或者DP[i/j][j]转移过来。
对于100%的数据：如果一个数a是有意义的，则它一定不是一个质数。把a分解成质因数以后，a的所有质因数都<50，它才有可能成为一个有意义的数。
使用滚动数组转移。

day 7

trie树

//其实不难……真的简单 比如我左前方的大佬正在逛贴吧
之前讲过一点点trie树，可以上翻找到。

例题：

给定n个互不相同的串，求存在多少对数(i,j)(共n^2对)满足第i个串是第j个串的前缀。
所有串的长度之和<=500000。
构建这棵trie树，然后我们枚举每个红色点，它对答案的贡献是以它为根的子树中红色节点的个数之和。
这个东西可以在一开始遍历这棵树预处理出来。
时间复杂度为线性。

USACO的某题
给定n个串，重排字符之间的大小关系，问哪些串有可能成为字典序最小的串。
所有字符串的长度之和<=100000。
首先对这n个串构建trie树，之后对于每个串，从根走向它，这个路程中遇到的所有兄弟在字典序下都要比它大。
因此可以得到最多26*26个大小关系。
判断是否存在拓扑序即可。
把字符串倒过来就可以啦
时间复杂度为100000*26^2。

KMP

这个我讲的不如胡小兔好，记的笔记也肯定没有她写的教程棒，于是欢迎访问我的(女)好朋友【24OI最强者：rabbithu】的博客：图解KMP算法——特殊的字符串匹配技巧
代码很短……不会的话就背代码吧qwq

AC自动机

有n个模式串(长度之和T），一个主串，求哪些模式串是主串的子串
如果直接跑KMP，是O(n*S) 。AC自动机 O(T+S)
对于n个串，搞个trie树出来，然后在trie树上做KMP。
对于每个点，求一个P（即为nxt[])，如果不能匹配再跳到P处。
其实就是trie+KMP。
(昨天T2就是AC自动机啊啊！为什么不早点讲！）

POJ3080 blue jeans

给定m个串，求字典序最小的公共子串。
m<=10, 每个串的长度<=60。
枚举所有子串，复杂度为60*60。
验证其它串是否包含这个子串，复杂度为10*60。
每次更新答案即可。
时间复杂度为60^3*10。
给定一个字符串S，求所有既是S的前缀又是S的后缀的子串，从小到大输出这些串的长度。

POJ2752

给定一个字符串S，求所有既是S的前缀又是S的后缀的子串，从小到大输出这些串的长度。
|S|<=500000。
先回到KMP算法：我们令P[j]表示找最大的数x，使得B中位置是1~x的字符与j-x+1~j的字符完全相同。
考虑P[|S|]的意义：也就是最大的前缀等于后缀的长度（不包括其本身）。
那P[P[|S|]]就是次大的。
因此所有P[P[…P[|S|]]]就是答案了。
（P即NXT）

或者用hash，不需要思考，直接跑就行啦

2 1 1 2 1 1 +