NOIp2016算法

程序大部分没经过编译和测评，欢迎在评论区指出本文中的错误
另：点开右下角像WIFI一样的标志进入RSS模式即可避免索引目录鬼畜的问题（可能需要向下翻一会才能找到本篇文章）

NOIp竞赛中还可能会用到的模板：Tarjan等，请大家注意一下

记得考前一定要练好DFS和记忆化DFS！！骗分必用！

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;
}

队列

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;
};

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

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

树状数组

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);

应用模型：

树状数组求逆序对：

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是离散化后的数组
}

单调队列

例题: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;
}

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个元素

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);

Stack

stack<int> opt;
opt.front();//返回
opt.size();
opt.empty();
opt.push();
opt.pop();//弹出

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相当于end
third.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();//清除

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);//看有没有关系

Algorithm里其他好用的函数

Next_permutation

int a[]={1,2,3,4};

next_permutation(a,a+3);//下一个全排列

//现在a数组变成了:1 2 4 3

Lower_bound与Upper_bound

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

Merge

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

sort

bool compare(int a,int b)
{
    return a<b;
};//compare函数的例子

sort(起始地址,结束地址,compare函数);

Reverse

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

Unique

bool myfunction (int i, int j)
{
  return (i==j);
}

unique(起始地址,结束地址,去重条件函数);//按照函数里面编写的规则去重，当然也可以没有第三个参数

Random_shuffle

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

数论

快速幂

普通快速幂

#define ull unsigned long long
ull 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;
}

矩阵快速幂

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;
}

筛法求素数

欧拉筛法

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;
        };
    };
};

应用举例：

模板题 : Luogu P3383

验证素数

普通方法

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

Miller-Rabin

时间复杂度：O(k∗log2n) k是次数(见下文)
难度：★★★

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

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

最大公约数和最小公倍数

gcd为最大公约数，lcm为最小公倍数
a∗b=gcd∗lcm;

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);
};

扩展欧几里德

解决ax+by=gcd(a,b)
当a,b互质：ax+by=1
解为：x+(b/gcd)∗t或y+(a/gcd)∗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；
} //不理解建议背过

应用举例：

模板题 : NOIp2012TG day2 T1 / Luogu P1082

逆元

所谓逆元就是ab≡1(modp)，a和b就在模p的意义下逆元。

利用同余的性质：
ab≡1(modp)⇒ab−1≡0(modp)⇒ab+pt=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;
}

Catalan数

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

括号化
矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(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;
}

应用举例：

模板题 : NOIp2003 PJ / Luogu P1044

高精

读入、储存与输出

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

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

读入与储存 :

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);//存长度
};

输出 :

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

高精度加法

高精加单精

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]);
};

高精加高精

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;
};

高精度乘法

高精乘单精

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]--;
    };
};

高精乘高精

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]--;
    };

高精度除法

高精度除以单精度

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

//divide
const 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;
}

压位

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];
        };
    };
}

注意⚠:使用压位的时候的读入不要读错
比如不要把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;
}

次短路

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

先用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];
    };
}

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

把所有边排序，记第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所在的连通分量
    }

在上面的伪代码中，最关键的地方在于”连通分量的查询与合并”:需要知道任意两个点是否在同一个连通分量中，还需要合并两个连通分量。
最容易想到的方法是”暴力”——每次”合并”时只在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;
};

其实此处还有一个优化，虽然不会节省很长时间，但是，优势都是一点点积累出来的！就是循环枚举边的时候不用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^9
for(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]);

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

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

只需将程序中的

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

改成

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

例题:

传递闭包：电话圈(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);

 }

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

树

建树

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

传递闭包

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

并查集

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

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

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 root
int 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;
}

动态规划

钟长者说：有几个未知量，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]);
    };

最大连续子序列和

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]);
}

最长公共自序列和

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]);

字符串转换问题

给定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;

最长不下降子序列

//据说可以用二分进行优化
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]);

背包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]即为最大权值

优化：

//条件和上面一样
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]);

例题：

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]);

混合背包

即有好几种背包的条件，分别写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]);

例题：

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];
}

二分

void binary(int l,int r)    //找最小
{
    while(r>l)
    {
        mid=(l+r)/2;
        if(check(mid))r=mid;
            else l=mid+1;
    };
    ans=l;
}

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;
};

Hash

哈希大法好

#define ull unsigned long long
ull 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;
};

感谢您的阅读

本文链接地址: NOIp2016算法http://www.hongyanliren.com/2017m02/37808.html

数据结构

栈

队列

树状数组

单调队列

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

相关文章