冲刺NOIp2016算法模板(C++)

Catalogue:

冲刺NOIp2016算法模板
数据结构
栈
队列
树状数组
单调队列
STL
Vector
Queue
Priority_queue
Stack
Deque
Bitset
Set
Multiset
Map
Algorithm里其他好用的函数
Next_permutation
Lower_bound与Upper_bound
Merge
sort
Reverse
Unique
Random_shuffle
数论
快速幂
普通快速幂
矩阵快速幂
筛法求素数
欧拉筛法
验证素数
普通方法
Miller-Rabin
分解质因数唯一分解定理
最大公约数和最小公倍数
扩展欧几里德
逆元
Catalan数
高精
读入储存与输出
高精度加法
高精加单精
高精加高精
高精度乘法
高精乘单精
高精乘高精
高精度除法
高精度除以单精度
压位
图论
最短路
SPFA
次短路
最小生成树MST
Kruskal
图的遍历
Floyed
二分图染色
树
建树
传递闭包
并查集
LCA
动态规划
线性DP
最大递增子序列和
最大连续子序列和
最长公共自序列和
字符串转换问题
最长不下降子序列
背包DP
01背包
完全背包
混合背包
分组背包
其他模板
归并排序
二分
Hash

数据结构

栈

int strack[maxn];int head;bool b[maxn];void push(int x){    strack[++head]=x;    b[x]=true;};int pop(){    int ret;    ret=strack[head--];    b[ret]=false;    return ret;};bool empty(){    return head>0;}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

队列

int queue[2*maxn];int tail,head;bool b[maxn];void push(int x){    queue[++tail]=x;    bool[x]=true;};int pop(){    int ret;    ret=queue[++head];    b[ret]=false;    return ret;};bool empty(){    return head>=tail;};  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

当然有的时候你手写的数据结构需要比较大的空间，这样队列就会造成很多损失，所以相应的就有两种解决方法：一：STL；二：循环队列，只需改两个地方（代码如下）；

head=(head+1)%n+1;//把head++改tail=(tail+1)%n+1;//把tail++改1
2

树状数组

int lowbit(int x){    return x&-x;};int getsum(int n) //求1～n见的和{    int ret=0;    while(n)    {        ret+=c[n];        n-=lowbit(n);    };    return ret;};void add(int n,int x) //给a[n]加上x{    a[n]+=x;    while(n<=maxn)    {        c[n]+=x;        n+=lowbit(n);1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

应用模型：

树状数组求逆序对：

void update(int n){    while(n<=maxn)    {        c[n]+=1;        n+=lowbit(n);    };};for(int i = 1; i <= n; ++i)  //主程序里面加上这个{      update(reflect[i]);      ans += i - getsum(reflect[i]);//reflect是离散化后的数组} 1
2
3
4
5
6
7
8
9
10
11
12
13
14

单调队列

例题:Luogu P1823 音乐会的等待（我写了一篇此题的解题报告）

以下单调队列的标程就用的音乐会的等待的。

#include <iostream>#include <cstdio>using namespace std;const int maxn=500005;int n,l,ans;long long q[maxn],bef[maxn];int main(){    cin>>n;    q[0]=-1;    long long a;    for(int i=1;i<=n;i++)    {        cin>>a;        while(l>0&&a>q[l])        {            l--;            ans++;        };        if(l!=0)        {            if(a!=q[l])ans++;else            {                ans+=bef[l];                if(bef[l]<l)ans++;            };        };        l++;q[l]=a;        if(q[l-1]==a)bef[l]=bef[l-1]+1;else bef[l]=1;       };    cout<<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

STL

关于每个STL我只会写一下是什么，怎么用（举例子的形式），不会说的太细

Vector

不定长度数组

#include <vector>vector<int> first;  //第一种定义方法int myints[]={16,2,77,29};vector<int> second(myints,myints+4);//第二种定义方法sort(second.begin(),second.end());//对vector排序a=second[i];//可以这么使用//以下是对vector的操作Vector<int> opt;opt.begin();    //返回起始地址opt.end();  //返回结束地址opt.size(); //返回大小opt.empty();    //返回是否vector为空opt.back(); //返回最后一个push进的数opt.pop_back(); //把最后一个数弹出（不返回）opt.push_back(int x);//把x从后面push进去opt.erase(opt.begin(),opt.begin()+3);//删掉前三个元素opt.erase(opt.begin()+5);//删掉第6个元素1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Queue

队列，操作与Stack一样。

Priority_queue

相当于堆

#include <queue>priority_queue<int> Bigheap;//定义一个大根堆priority_queue<int,vector<int>,greater<int> > Smallheap;//定义一个小根对（注意两个尖括号间有空格）//以下是操作priority_queue<int> opt;opt.top();//返回堆顶元素的值（不弹出）opt.pop();//弹出堆顶元素（无返回值）opt.push(x);1
2
3
4
5
6
7
8
9
10
11

Stack

stack<int> opt;opt.front();//返回opt.size();opt.empty();opt.push();opt.pop();//弹出1
2
3
4
5
6

Deque

双向队，操作与Stack一样

Bitset

压位神器，只普及一下，不会用。

Set

set<int> first;int myints[]= {10,20,30,40,50};set<int> second (myints,myints+5);set<int> third (second);set<int> fourth (second.begin(), second.end());third.rbegin(); third.rend();//rend相当于begin，rbegin相当于endthird.size();//返回大小third.insert(60);third.erase(it);third.erase(50);//删除元素'50'third.find(10);//找元素'10'third.lower_bound(30); third.upper_bound(30);//'30'出现的第一个位置/最后一个位置third.clear();//清除1
2
3
4
5
6
7
8
9
10
11
12
13

Multiset

与Set用法一样，只是允许重复元素。

Map

map<char,int> first;first[‘a’] = 10;first.insert(make_pair(‘b’,20));it++; ++it; it--; --it;first.erase(1);//删除元素firstt.count(1);//看有没有关系1
2
3
4
5
6

Algorithm里其他好用的函数

Next_permutation

int a[]={1,2,3,4};next_permutation(a,a+3);//下一个全排列//现在a数组变成了:1 2 4 31
2
3
4
5

Lower_bound与Upper_bound

lower_bound(first,last,val);//有返回值upper_bound(first,last,val);1
2

Merge

merge (first,first+5,second,second+5,v.begin(),compare);1

sort

bool compare(int a,int b){    return a<b;};//compare函数的例子sort(起始地址,结束地址,compare函数);1
2
3
4
5
6

Reverse

Reverse(myvector.begin(),myvector.end());1

Unique

bool myfunction (int i, int j){  return (i==j);}unique(起始地址,结束地址,去重条件函数);//按照函数里面编写的规则去重，当然也可以没有第三个参数1
2
3
4
5
6

Random_shuffle

留一个概念，不会用，生成数据的时候用。

数论

快速幂

普通快速幂

#define ull unsigned long longull qpow(ull x,ull y,ull p) // x^y mod p{    ull ret=1;    while(y)    {        if(y&1)ret = ret * x % p;        x=x*x%p;        y>>=1;    };    return ret;}1
2
3
4
5
6
7
8
9
10
11
12

矩阵快速幂

matrix operator *(matrix m1,matrix m2)//重载运算符{    assert(m1.m==m2.n);    matrix res;    res.n=m1.n; res.m=m2.m;    for(int i=0;i<m1.n;i++)        for(int j=0;j<m2.m;j++)            for(int k=0;k<m1.m;k++)                res.mat[i][j]+=m1.mat[i][k]*m2.mat[k][j];    return res;}matrix matrix_pow(matrix x,int y){    matrix res;    res.n=res.m=2;    res.mat[0][0]=res.mat[1][1]=1;    while(y)    {        if(y&1)res=res*x;        x=x*X;        y>>=1;    }    return res;}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

筛法求素数

欧拉筛法

int tot=0;void euler(int n){    memset(check,0,sizeof(check));    for(int i=1;i<=n;i++)    {        if(!check[i])prime[++tot]=i;        for(int k=1;k<=tot;k++)        {            if(i*prime[k]>n)break;            check[i*prime[k]]=1;            if(i%prime[k]==0)break;        };    };};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

应用举例：

模板题 : Luogu P3383

验证素数

普通方法

bool flag=true;for(int i=1;i<=trunc(sqrt(prime));i++)    if(prime%i==0)flag=false;//置不是素数标志1
2
3

Miller-Rabin

时间复杂度： $O (k * l o g_{2} n)$ k是次数(见下文)
难度：★★★

这里只说明一下原理，关于代码，自行百度吧。

根据费马小定理，随机选一个数 $a \in (1, p)$ ，若 $a^{p - 1} \equiv 1$ (mod p)则很有可能是素数。多次尝试（尝试k次）若都成立若都成立则判定为素数。
但是合数也有可能能通过这一测试：Carmichael数
Carmichael概念：
　　卡迈克尔数是一种合数，使得对于所有跟n互质的整数a： $a^{n - 1} \equiv 1$ (mod n)
这种数用此方法测试时，除非random出其因子，不然都无法判断为合数。例如：6。
二次探测定理：若n为素数，方程 $x^{2} \equiv 1$ (mod n)小于n的正整数解只有 $x = 1$ 和 $x = n - 1$ 。
先计算出m、j，使得 $n - 1 = m * 2^{j}$ 且j尽可能大。
随机选一个数 $a \in (1, n)$
计算x= $a^{m}$ mod n
然后将x不断平方j次，重复如下步骤：
　　1. 计算y= $x^{2}$ mod n
　　2. 如果y=1并且 $x \neq 1, n - 1$ ，此时一定不是素数，退出测试
　　3. x=y；
　　4. 如果y=1，暂时认为是素数，回到2.继续下一轮
若上述计算中没有满足2.和4.而正常退出，即不满足 $a^{n - 1} \equiv 1$ (mod n)，一定不是质数
其次：这个博客写的很好（点击进入）；

分解质因数——唯一分解定理

void divide_prime(int n){    int p=2;    int t(trunc(sqrt(n)));    while(n!=1&&p<=t)    {        int i=0;        if(n%p==0)        {            while(n%p==0){n/=p;i++;};            cout<<p<<'^'<<i<<' ';        };        p++;    };    if(n!=1)cout<<n<<'^'<<1;}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最大公约数和最小公倍数

gcd为最大公约数，lcm为最小公倍数
$a * b = g c d * l c m$ ;

int gcd(int a,int b)//注意此处a要大于b{    return b==0?a:gcd(b,a%b);};int lcm(int a,int b){    return a*b/gcd(a,b);};1
2
3
4
5
6
7
8

扩展欧几里德

解决 $a x + b y = g c d (a, b)$
当a,b互质： $a x + b y = 1$
解为： $x + (b / g c d) * t$ 或 $y + (a / g c d) * t$

int x,y;int gcd(int a,int b){    int ret,t;    if(b==0)    {        x=1;        y=0;        return a;    };    ret=gcd(b,a%b);    t=y; y=x-(a%b)*y; x=t;    return ret；} //不理解建议背过1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

应用举例：

模板题 : NOIp2012TG day2 T1 / Luogu P1082

逆元

所谓逆元就是 $a b \equiv 1 (\mod p)$ ，a和b就在模p的意义下逆元。

利用同余的性质：
$a b \equiv 1 (\mod p) \Rightarrow a b - 1 \equiv 0 (\mod p) \Rightarrow a b + p t = 1$
故可以用扩展欧几里德求解

//其实就是NOIp2012TG D2T1/Luogu P1082#include <iostream>#include <cstdio>using namespace std;long long x,y,a,b,ans;long long gcd(long long a,long long b){    long long t,ret;    if(b==0)    {        x=1;        y=0;        return a;    }    ret=gcd(b,a%b);    t=y;    y=x-(a/b)*y;    x=t;    return ret;}int main(){    cin>>a>>b;    ans=gcd(a,b);    while(x>b)x-=b;    while(x<0)x+=b;    cout<<x<<endl;    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

Catalan数

原理理解：(两个应用模板)

括号化
矩阵连乘： $P = a_{1} \times a_{2} \times a_{3} \times \dots \dots \times a_{n}$ ，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n-1)种)

出栈次序
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

详情请参照百度百科

int main() // 求第n个卡特兰数{    cin>>n;    h[0]=1;h[1]=1;    for(int i=2;i<=n;i++)        for(int j=0;j<=i-1;j++)            h[i]=h[i]+h[j]*h[i-j-1];    cout<<h[n];    return 0;}1
2
3
4
5
6
7
8
9
10

应用举例：

模板题 : NOIp2003 PJ / Luogu P1044

高精

读入、储存与输出

以下代码块均包含以下语句 :

int s[255];//255位的数1

读入与储存 :

void read(){    char ss[255];    scanf("%s",ss);    for(int i=1;i<=strlen(ss);i++)        s[i]=ss[strlen(ss)-i+1]-'0';    s[0]=strlen(ss);//存长度};1
2
3
4
5
6
7
8
9

输出 :

void print(){    for(int i=s[0];i>=1;i－－)        cout<<s[i];};1
2
3
4
5

高精度加法

高精加单精

void add(int *s,int x)//s存高精度数，x是要加的单精度{    int k=1;    s[k]+=x;    while(s[k]>=10)    {        s[k+1]+=s[k]/10;        s[k++]%=10;    };    s[0]=max(k,s[0]);};1
2
3
4
5
6
7
8
9
10
11

高精加高精

void add(int *s1,int *s2,int *ans){    int len;    len=max(s1[0],s2[0]);    for(int i=1;i<=len;i++)    {        ans[i]+=s1[i]+s2[i];        if(ans[i]>=10)        {            ans[i+1]+=ans[i]/10;            ans[i]%=10;        };    };    if(ans[len+1]!=0)len++;    ans[0]=len;};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

高精度乘法

高精乘单精

void multiply(int *s,int x){    for(int i=1;i<=n;i++)    {        c[i]+=s[i]*x;        c[i+1]+=(s[i]*x)/10;        c[i]%=10;    };    c[0]=s[0]+1;    while(c[c[0]]>=10)    {        c[c[0]+1]+=c[c[0]]/10;        c[c[0]]%=10;        c[0]++;    };    while(c[0]>1&&c[c[0]]==0)    {        c[0]--;    };};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

高精乘高精

void multiply(int *s1,int *s2,int *ans){    for(int i=1;i<=s1[0];i++)        for(int j=1;j<=s2[0];j++)        {            ans[i+j-1]+=s1[i]*s2[j];            ans[i+j]+=ans[i+j-1]/10;            ans[i+j-1]%=10;        };    ans[0]=s1[0]+s2[0]+1;    while(ans[0]>1&&ans[ans[0]]==0)    {        ans[0]--;    };  1
2
3
4
5
6
7
8
9
10
11
12
13
14

高精度除法

高精度除以单精度

此处略微借鉴了一下铭哥的标程

//divideconst int opt=10000;struct node{    int a[1005];    int len;}node divide(node a;int p){    node c;    int i,d;    d=0;    c.len=a.len;    for(int i=a.len;i>=1;i--)    {        d=d*opt+a.a[i];        c.a[i]=d/p;        d=d%p;    };    while(c.len>1&&c.a[c.len]==0)    {        c.len--;    };    return c;}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

压位

const int opt=100000000;void multiply(int *num,int x){    for(int i=1;i<=num[0];i++)num[i]*=x;    for(int i=1;i<=num[0];i++)    {        if(num[i]>=opt)        {            num[i+1]+=num[i]/opt;            num[i]%=opt;        };        while(num[num[0]]!=0)        {            num[0]++;        };    }}void print(int *a){    for(int i=a[0];i>=1;i--)    {        if(i==a[0])        {            cout<<a[i];        }else        {            if(a[i]<10000000)cout<<0;            if(a[i]<1000000)cout<<0;            if(a[i]<100000)cout<<0;            if(a[i]<10000)cout<<0;            if(a[i]<1000)cout<<0;            if(a[i]<100)cout<<0;            if(a[i]<10)cout<<0;            cout<<a[i];        };    };}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

注意⚠:使用压位的时候的读入不要读错
比如不要把99存到数组的两个位置里面，而应该是一个；

图论

最短路

SPFA

以下代码中包括邻接表(前向星)存图

#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn=5005,maxm=100005;const int INF=0xffffff;int n,m; //n个点，m条边int queue[2*maxn],head,tail;int dist[maxn];int firstEdge[maxn],weight[maxm],nextEdge[maxm],endPoint[maxm];int p;bool b[maxn];void add(int x,int y,int z)//前向星{    weight[++p]=z;    endPoint[p]=y;    nextEdge[p]=firstEdge[x];    firstEdge[x]=p;};void push(int x)  //队列的操作，详见上面{    b[x]=true;    queue[++tail]=x;}int pop() //队列的操作，详见上面{    int ret;    ret=queue[++head];    b[ret]=false;    return ret;}void SPFA(){    int u;    int nowP;    for(int i=2;i<=n;i++)dist[i]=INF;    push(1);    while(tail>head)    {        u=pop();        nowP=firstEdge[u];        while(nowP)        {            if(dist[endPoint[nowP]]>dist[u]+weight[nowP])            {                dist[endPoint[nowP]]=dist[u]+weight[nowP];                if(b[endPoint[nowP]])push(endPoint[nowP]);            }；            nowP=nextEdge[nowP];        }    }}int main(){    cin>>n>>m;    for(int i=1;i<=m;i++)    {        int x,y,z;        cin>>x>>y>>z;        add(x,y,z);        add(y,x,z); //无向图加上这句，有向图不用加（具体看题描述）    };    SPFA();    cout<<dist[n]<<endl;    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

次短路

代码比较麻烦，不写了，说一下思路吧。

先用SPFA跑一遍，找出来最短路。把最短路记下来。
接下来，每次删掉最短路上的一条边，再跑一边SPFA。
运行一遍以后，路径长度最小的即次短路。

最小生成树(MST)

最小生成树即一个无向连通不含圈图中，连接G中所有点，且边集是E的子集，且边权和最小的生成树。（我解释的有点拗口）

最小生成树算法一共有两个：Prim和Kruskal算法，由于经并查集优化的Kruskal算法比Prim算法优秀得多，且Prim算法较容易理解，这里只给出Kruscal算法的模板。

Kruskal

下面展现两种做法，一种是普通的暴力枚举做法，另一种是并查集优化过的。并查集优化过的算法比较快，但是要忽略生成树的形状。就是说如果你需要用到新生成树的形状，那么不能使用此种方法。

普通方法：//类似Prim算法

struct node{int u,v,w;}e[maxe];//u是起点,v是终点,w是权node MST[maxe];bool com(node a,node b){return a.w<b.w;};void Kruskal(){    sort(e+1,e+m+1,com);//按边权从小到大排序    for(int i=1;i<=m;i++)    {        if(!b[e[i].u]&&!b[e[i].v])//b判断是否已经在集合里            MST[++tot]=e[i];    };}1
2
3
4
5
6
7
8
9
10
11
12
13

以上版本是自己写的，感觉不对，于是抄下来了粉书上的伪代码和讲解：

把所有边排序，记第i小的边为e[i](1<=i<m)初始化MST为空初始化连通分量，让每个点自成一个独立的连通分量for(int i=1;i<=m;i++)    if(e[i].u和e[i].v不在同一个连通分量)    {        把边e[i]加入MST        合并e[i].u和e[i].v所在的连通分量    }   1
2
3
4
5
6
7
8
9

在上面的伪代码中，最关键的地方在于”连通分量的查询与合并”:需要知道任意两个点是否在同一个连通分量中，还需要合并两个连通分量。
最容易想到的方法是”暴力”——每次”合并”时只在MST中加入一条边（如果使用邻接矩阵，只需G[e[i].u][e[i].v]=1），而”查询”时直接在MST中进行图遍历(DFS和BFS都可以判断连通性)。

并查集优化

int find(int x){return p[x]==x?x:p[x]=find(p[x]);}//并查集的find和路径压缩int Kruskal()//返回的最小生成树的边权和{    int ans=0;    for(int i=1;i<=n;i++)p[i]=i;//初始化并查集    sort(edge+1,edge+m+1,com);//给边从小到大排序    for(int i=1;i<=m;i++)    {        int x=find(edge[i].u);        int y=find(edge[i].v);        if(x!=y)        {            ans+=edge[i].w;//求和            p[x]=y;        };//如果在不同的集合，合并    }    return ans;};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

其实此处还有一个优化，虽然不会节省很长时间，但是，优势都是一点点积累出来的！就是循环枚举边的时候不用for而用while，当当前得到的最小生成树一共有n-1条边时，最小生成树就已经生成完了，剩下的边就不用再枚举了。

训练参考:

最小生成树: Slim Span(UVa1395)
最小生成树: Buy or Build(UVa1151)

图的遍历

Floyed

for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++)        d[i][j]=INF;//INF是比最大权和大一点的数，不能超2*10^9for(int i=1;i<=n;i++)    d[i][i]=0;      //以上为使用前的初始化for(int k=1;k<=n;k++)    for(int i=1;i<=n;i++)        for(itn j=1;j<=n;i++)            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);1
2
3
4
5
6
7
8
9
10

还有一点相关的东西就是传递闭包（Transitive Closure）

即在有向图中，有时不必关心路径长度，而只关心每两点间是否有通路，则可以用1和0分别表示”连通”和”不连通”。得到的结果称为有向图的传递闭包。

只需将程序中的

d[i][j]=min(d[i][j],d[i][k]+d[k][j]);1

改成

d[i][j]=d[i][j]||(d[i][k]&&d[k][j]));1

例题:

传递闭包：电话圈(Calling Circles,ACM/ICPC World Finals 1996,UVa247)(Floyd，连通分量)
Floyd：噪音恐惧症(Audiophobia,UVa10048)(Floyd，最大值最小路)

二分图染色

基本思路就是用DFS，对于每个点，将与其连接的下一个点染上不同的颜色。

下面的程序是“双栈排序“里二分图染色的子程序：

void dfs(int p,int colour) {     if(!color[p])color[p]=colour;     else if(color[p]!=colour)      {          printf("0");          exit(0);      }          else return;    for(int i=last[p];i>0;i=next[i])dfs(goal[i],3-colour); }1
2
3
4
5
6
7
8
9
10
11
12
13

附上几篇不错的博客：（感谢喵头鹰、暗金色、LOI_summer）
喵头鹰的博客
 暗金色的博客
 LOI_summer的博客

树

建树

具体思路：对于一个节点来说，其他的任意一个节点，不是他的父节点，就是他的子节点。

传递闭包

详见上面图论部分Floyd算法。

并查集

int find(int x)//非路径压缩{    return p[x]==x?x:find(p[x]);};1
2
3
4

int find(int x)//并查集+路径压缩{    return p[x]==x?x:p[x]=find(p[x]);}；1
2
3
4

LCA

倍增版LCA

思路如下

// 把树存起来（前向星，无向边）// 把每个点的深度求出来（dfs）// 把i向上2^j个深度的祖宗求出来（倍增）(先搜j在搜i)// 读入两个点// 把较深的一个点向上移动至与另一个点相同// 如果祖宗一样就返回这个祖宗// 两个点一起向上移（从远到近）（条件里不要忘了＝）#include <iostream>#include <cstdio>using namespace std;int n,m,s;//n is node,m is qustion,s is rootint anc[500005][50];int fa[500005];int deep[500005];int h[500005],v[1000010],nt[1000010];void dfs(int u)//u代表起点{    int p=h[u];    while(p)    {        if(deep[v[p]]==-1)//如果没处理过        {            deep[v[p]]=deep[u]+1;            anc[v[p]][0]=u;//v[i]上面2^0个深度的祖先是u            dfs(v[p]);//接下来处理一下v[i]        }        p=nt[p];    }}void init(){    for(int j=1;(1<<j)<=n;j++)        for(int i=1;i<=n;i++)            anc[i][j]=anc[anc[i][j-1]][j-1];}int LCA(int a,int b){    if(deep[a]<deep[b])swap(a,b);    int i;for(i=0;(1<<i)<=deep[a];i++);i--;    if(deep[a]!=deep[b])        for(int j=i;j>=0;j--)            if(deep[a]-(1<<j)>=deep[b])                a=anc[a][j];    if(a==b)return a;    for(int j=i;j>=0;j--)    {        if(anc[a][j]&&(anc[a][j]!=anc[b][j]))        {            a=anc[a][j];            b=anc[b][j];        };    };    return anc[a][0];}int main(){    scanf("%d%d%d",&n,&m,&s);    for(int i=1;i<=n;i++)deep[i]=-1;//表示deep还没有处理过    for(int i=1;i<2*n-1;i+=2)//i个点的树有2*(n-1)条边    {        int a;        scanf("%d%d",&a,&v[i]);        nt[i]=h[a]; h[a]=i;        v[i+1]=a; nt[i+1]=h[v[i]]; h[v[i]]=i+1;    }//前向星村边    deep[s]=0;//根的深度是0    dfs(s);//深搜求每个点的深度    init();    for(int i=1;i<=m;i++)    {        int a,b;        scanf("%d%d",&a,&b);        printf("%d",LCA(a,b));    }    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
76
77
78
79
80
81
82
83
84
85
86
87
88
89

动态规划

钟长者说：有几个未知量，DP数组就有几维，若求个数能再省掉最后一维。
然而这只是一般情况，例如有个例外：HAOI2012 音量调节/Luogu P1877，这道题就不能省掉最后一维。

铭哥说：重推所有的DP方程是复习DP的最佳方法

线性DP

最大递增子序列和

int ans=0,f[maxn]={-1};for(int i=1;i<=n;i++)    for(int j=0;j<=i-1;j++)    {        f[i]=max(f[i],f[j]+a[i]);        ans=max(ans,f[i]);    };1
2
3
4
5
6
7

最大连续子序列和

f[1]=a[1];for(int i=2;i<=n;i++){    f[i]=max(f[i-1]+a[i],a[i]);    ans=max(ans,f[i]);}1
2
3
4
5
6

最长公共自序列和

for(int i=1;i<=strlen(s1);i++)    for(int j=1;j<=strlen(s2);j++)        if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1;            else f[i][j]=max(f[i-1][j],f[i][j-1]);1
2
3
4

字符串转换问题

给定A串和B串，有删除一个字符、插入一个字符、改变一个字符三种操作，求A变到B的最少操作次数。
f[i][j]表示A的前i个字符变成B的前j个字符所用的最少步数。

for(int i=0;i<=strlen(A);i++)f[i][0]=i;for(int i=0;i<=strlen(B);i++)f[0][i]=i;for(int i=1;i<=strlen(A);i++)    for(int j=1;j<=strlen(B);j++)        if(A[i]==B[j])f[i][j]=f[i-1][j-1];            else f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1,j-1])+1;1
2
3
4
5
6

最长不下降子序列

//据说可以用二分进行优化for(int i=2;i<=n;i++)    for(int j=1;j<=i-1;j++)        if(a[j]<=a[i])f[i]=max(f[i],f[j]+1);for(int i=1;i<=n;i++)ans=max(ans,f[i]);1
2
3
4
5

背包DP

01背包

for(int i=1;i<=m;i++)//m个物品    for(int j=1;j<=w;j++)//背包容量为w        if(a[i]<=j)        {            dp[i][j]=max(dp[i-1,j-a[i]]+val[i],dp[i-1,j]);//a数组是占用的容量，val是价值        }else        {            dp[i][j]=dp[i-1][j];        };//此时dp[m][w]即为最大权值1
2
3
4
5
6
7
8
9
10
11

优化：

//条件和上面一样for(int i=1;i<=n;i++)    for(int j=w;i>=a[i];j--)        dp[j]=(dp[j],dp[j-a[i]]+val[i]);1
2
3
4

例题：

Luogu1048 菜药

完全背包

//条件和上面一样,只是每个物品可以取无数次for(int i=1;i<=n;i++)    for(int j=a[i];i<=w;j++)//注意这里的改动        dp[j]=(dp[j],dp[j-a[i]]+val[i]);1
2
3
4

混合背包

即有好几种背包的条件，分别写dp满足条件就可以了（比如NOIp2014TG的飞扬的小鸟）

for(int k=1;k<=组数;k++)    for(int j=c;j>=0;j++)        for(int i=1;i<=n;i++)            if(j>=v[i])f[j]=maxn(f[j],f[j-v[i]]+w[i]);1
2
3
4

例题：

NOIp2014TG 飞扬的小鸟

分组背包

这里有一篇分组背包博客写的不错，参考这篇博客吧。感谢博客的作者nywsp。

练习题:luogu P1757

其他模板

归并排序

void mergesort(int l,int r){    if(l==r)return;    int ret[maxn];    int mid;    mid=(l+r)/2;    mergesort(l,mid); mergesort(mid+1,r);    int i=l,j=mid+1,k=l;    while(i<=mid&&j<=r)    {        if(a[i]<a[j])        {            ret[k++]=a[i++];        }else        {            ret[k++]=a[j++];            ans+=mid-i+1;//求逆序对时加上这一句        };    };    while(i<=mid)ret[k++]=a[i++];    while(j<=r)ret[k++]=a[j++];    for(int i=l;i<=r;i++)a[i]=ret[i];}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

二分

void binary(int l,int r)    //找最小{    while(r>l)    {        mid=(l+r)/2;        if(check(mid))r=mid;            else l=mid+1;    };    ans=l;}1
2
3
4
5
6
7
8
9
10

void binary(int l,int r)    //找最大{    while(r>l)    {        mid=(r+l)/2+1;  //特别注意        if(check(mid))l=mid+1;            else r=mid;    };    ans=l;};1
2
3
4
5
6
7
8
9
10

Hash

哈希大法好

#define ull unsigned long longull hash(char *s){    int l=strlen(S);    ull ans=0;    int seed=27;    for(int a=0;a<l;a++)        ans=ans*seed+a[i]-'a'+1;    return ans;};1
2
3
4
5
6
7
8
9
10

感谢您的阅读

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。