csp 复赛算法模板总结

EDG_AKUYTRE · 2024-09-30 19:05:23 · 算法·理论

算法总结

背好了理解了轻松省一

一.搜索

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。

搜索有很多优化方式，如减小状态空间，更改搜索顺序，剪枝等。

搜索是一些高级算法的基础。在 OI 中，纯粹的搜索往往也是得到部分分的手段，但可以通过纯粹的搜索拿到满分的题目非常少。

1.dfs 深度优先搜索

将要搜索的目标分成若干「层」，每层基于前几层的状态进行决策，直到达到目标状态。

P1706 全排列问题

dfs(int k){
    if(k==n+1){
        for(int i=1;i<=n;i++)printf("%5d",a[i]);
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==false)
        {
            vis[i]=true;
            a[k]=i;
            dfs(k+1);
            vis[i]=false;
        }
    }
}

2.bfs 广度优先搜索

每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层

P1141 01迷宫

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int dx[5]={-1,1,0,0};
const int dy[5]={0,0,-1,1};
struct Node{
    int x,y;
}q[1000100];
int n,m,head,tail,x,y,num;
int f[1010][1010];
int a[1010][1010];
int d[1000010];
int bfs(int x,int y,int cnt){
    head=0;
    tail=1;
    q[1]={x,y};
    while(head<tail){
        head++;
        int x0=q[head].x;
        int y0=q[head].y;
        for(int i=0;i<=3;i++){
            int tx=q[head].x+dx[i];
            int ty=q[head].y+dy[i];
            if(!f[tx][ty]&&a[tx][ty]!=a[x0][y0]&&tx>=1&&tx<=n&&ty>=1&&ty<=n){
                q[++tail]={tx,ty};
                f[tx][ty]=cnt;
            }
        }
    }
    return tail;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            char ch;
            cin>>ch;
            a[i][j]=ch-48;
        }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(!f[i][j]){
                ans++;
                f[i][j]=ans;
                num=bfs(i,j,ans);
                d[ans]=num;
            }
        }
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        cout<<d[f[x][y]]<<endl;
    }
    return 0;
}

3. bdfs 百度优先搜索算法

当你无法解决问题的时候可以使用bdfs以获得解法

二十一世纪最优解法

仅供娱乐

二.dp 动态规划

1.背包

(1)01背包

已知条件有第 i 个物品的重量 w_{i}，价值 v_{i}，以及背包的总容量 W。

设 DP 状态 f_{i,j} 为在只能放前 i 个物品的情况下，容量为j的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 i-1 个物品的所有状态，那么对于第 i 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 f_{i-1,j}；当其放入背包时，背包的剩余容量会减小 w_{i}，背包中物品的总价值会增大 v_{i}，故这种情况的最大价值为 f_{i1,j-w_{i}}+v_{i}。

由此可以得出状态转移方程：

f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})

这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优化。

由于对 f_i 有影响的只有 f_{i-1}，可以去掉第一维，直接用 f_{i} 来表示处理到当前物品时背包容量为 i 的最大价值，得出以下方程：

f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})

务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的。

注意枚举顺序

P1048 [NOIP2005 普及组] 采药

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=122200;
int f[MAXN],v[MAXN],w[MAXN];
int t,m;
int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=m;i++){
        for(int j=t;j>=w[i];j--){
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }

    }
    cout<<f[t];
    return 0;
}

（2）完全背包

解释

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

我们可以借鉴 0-1 背包的思路，进行状态定义：设 f_{i,j} 为只能选前 i 个物品时，容量为 j 的背包可以达到的最大价值。

需要注意的是，虽然定义与 0-1 背包类似，但是其状态转移方程与 0-1 背包并不相同。

过程可以考虑一个朴素的做法：对于第 i 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 O(n^3) 的。

状态转移方程如下：

f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k)

考虑做一个简单的优化。可以发现，对于 f_{i,j}，只要通过 f_{i,j-w_i} 转移就可以了。因此状态转移方程为：

f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)

理由是当我们这样转移时，f_{i,j-w_i} 已经由 f_{i,j-2\times w_i} 更新过，那么 f_{i,j-w_i} 就是充分考虑了第 i 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。

与 0-1 背包相同，我们可以将第一维去掉来优化空间复杂度。如果理解了 0-1 背包的优化方式，就不难明白压缩后的循环是正向的

P1616 疯狂的采药

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=122200;
long long f[2100][MAXN],v[MAXN],w[MAXN];
int t,m;
int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=m;i++){
        for(int j=w[i];j<=t;j++){
            f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
        }

    }
    cout<<f[m][t];
    return 0;
}

（3）多重背包

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 $$ 个，而非一个。

一个很朴素的想法就是：把「每种物品选 k_i 次」等价转换为「有k_i 个相同的物品，每个物品选一次」。这样就转换成了一个 0-1 背包模型，套用上文所述的方法就可已解决。状态转移方程如下：

f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k)

时间复杂度

O(W\sum_{i=1}^nk_i)。

2.

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么 f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}，cost 为将这两组元素合并起来的价值。

P1880 [NOI1995] 石子合并

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=300;
int n,a[MAXN],a1[MAXN][MAXN],a2[MAXN][MAXN],f[MAXN],ans1,ans2;
int main(){
    memset(a1,0x3f,sizeof(a1));
    memset(a2,0,sizeof(a2));
    cin>>n;
    f[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<2*n;i++){
        f[i]=f[i-1]+a[i];
        a1[i][i]=a2[i][i]=0;
    }
    for(int i=2;i<=n;i++)
        for(int j=1;i+j-1<2*n;j++){
            int r=i+j-1;
            for(int k=j;k<r;k++){
            a1[j][r]=min(a1[j][r],a1[j][k]+a1[k+1][r]+f[r]-f[j-1]);
            a2[j][r]=max(a2[j][r],a2[j][k]+a2[k+1][r]+f[r]-f[j-1]);
            }
        }
    ans1=1e8;
    ans2=-1;
    for(int i=1;i<=n;i++){
        ans1=min(ans1,a1[i][i+n-1]);
        ans2=max(ans2,a2[i][i+n-1]);
    }
    cout<<ans1<<endl<<ans2;
    return 0;
}

3.树形dp

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

P1352 没有上司的舞会

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=106705;
int n,root,h[MAXN],a[MAXN],fa[MAXN],f[MAXN][3],cnt,u,v;
struct Node{
    int next,v;
}e[MAXN];
void add(int u,int v){
    e[++cnt].next=h[u];
    e[cnt].v=v;
    h[u]=cnt;
}
void dfs(int root){
    if(!root)return;
    f[root][1]=a[root];
    for(int i=h[root];i!=-1;i=e[i].next){
        int v=e[i].v;
        dfs(v);
        f[root][0]+=max(f[v][1],f[v][0]);
        f[root][1]+=f[v][0];
    }
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        cin>>u>>v;
        fa[u]=v;
        add(v,u);
    }
    for(int i=1;i<=n;i++)if(fa[i]==0){root=i;break;}
    dfs(root);
    cout<<max(f[root][0],f[root][1]);
    return 0;
}

4.状压dp

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

P1896 [SCOI2005] 互不侵犯

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,k,num=0,ans=0;
long long f[10][101][2010],sit[2000],tot[2000];
int main(){
    cin>>n>>k;
    for(int i=0;i<(1<<n);i++){
        int s=i,cnt=0;
        while(s){
            if(s&1)cnt++;
            s>>=1;
        }
        tot[i]=cnt;
        if((((i<<1)|(i>>1))&i)==0)sit[++num]=i;
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int u=1;u<=num;u++){
            int s1=sit[u];
            for(int l=1;l<=num;l++){
                int s2=sit[l];
                if(((s2|(s2<<1)|(s2>>1))&s1)==0){
                    for(int j=0;j<=k;j++)
                        if(j-tot[s1]>=0)
                            f[i][j][s1]+=f[i-1][j-tot[s1]][s2];
                }   
            } 
        }
    }
    for(int i=1;i<=num;i++)ans+=f[n][k][sit[i]];
    cout<<ans;
    return 0;
}

5.数位dp

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）；

这些条件经过转化后可以使用「数位」的思想去理解和判断；

输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；

上界很大（比如 10^{18}），暴力枚举验证会超时。

P2602 [ZJOI2010] 数字计数

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,k,num=0,ans=0;
long long f[10][101][2010],sit[2000],tot[2000];
int main(){
    cin>>n>>k;
    for(int i=0;i<(1<<n);i++){
        int s=i,cnt=0;
        while(s){
            if(s&1)cnt++;
            s>>=1;
        }
        tot[i]=cnt;
        if((((i<<1)|(i>>1))&i)==0)sit[++num]=i;
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int u=1;u<=num;u++){
            int s1=sit[u];
            for(int l=1;l<=num;l++){
                int s2=sit[l];
                if(((s2|(s2<<1)|(s2>>1))&s1)==0){
                    for(int j=0;j<=k;j++)
                        if(j-tot[s1]>=0)
                            f[i][j][s1]+=f[i-1][j-tot[s1]][s2];
                }   
            } 
        }
    }
    for(int i=1;i<=num;i++)ans+=f[n][k][sit[i]];
    cout<<ans;
    return 0;
}

三.快速幂与龟速乘

1.快速幂

P1226 【模板】快速幂

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long a,b,p,ans=1;
int main(){
    cin>>a>>b>>p;
    int y=b,x=a;
    while(b){
        if(b&1)ans=(ans*a)%p;
        a=(a*a)%p;
        b=b>>1;
    }
    cout<<x<<"^"<<y<<" mod "<<p<<"="<<ans;
    return 0;
}

延申：龟速乘求a*b mod p

while(b){
        if(b&1)ans=(ans+a)%p;
        a=(a+a)%p;
        b=b>>1;
    }

2.矩阵快速幂

P3390 【模板】矩阵快速幂

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1000;
const int Mod=1e9+7;
long long n,k;
struct Node{
    long long mx[MAXN][MAXN];
}a,b,s; 
Node operator *(const Node &a,const Node &b){
    Node c;
    memset(c.mx,0,sizeof(c.mx));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int p=1;p<=n;p++)
                c.mx[i][j]=(c.mx[i][j]+(b.mx[i][p]*a.mx[p][j])%Mod)%Mod;
    return c;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)s.mx[i][i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a.mx[i][j];
    while(k){
        if(k&1)s=s*a;
        a=a*a;
        k>>=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<s.mx[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

四.图论

1.最短路

（1）SPFA

P3371 【模板】单源最短路径（弱化版）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=500010;
int n,m,s,cnt=0;
struct Node{
    int to,nxt,w;
}e[MAXN];
int vis[MAXN],h[MAXN],dis[MAXN];
queue<int>q;
void add(int u,int v,int w){
    cnt++;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=h[u];
    h[u]=cnt;
}
void SPFA(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt){
            int x=e[i].to;
            if(dis[x]>dis[u]+e[i].w){
                dis[x]=dis[u]+e[i].w;
                if(vis[x]==0){
                    vis[x]=1;
                    q.push(x);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int xx,yy,zz;
        cin>>xx>>yy>>zz;
        add(xx,yy,zz);
    }
    SPFA();
    for(int i=1;i<=n;i++){
        if(dis[i]==0x3f3f3f3f)cout<<"2147483647 ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}

(2)堆优化dij

P4779 【模板】单源最短路径（标准版）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=200000;
const int MAXn=500010;
const int INF=(long long)(1<<31)-1;
int h[MAXN],vis[MAXN],d[MAXN],xx,yy,zz;
int n,m,s,cnt=0;
struct Heapnode{
    int w,u;
    bool operator <(const Heapnode &x)const{
        return w>x.w;
    }
};
priority_queue<Heapnode>q;
struct Node{
    int to,nxt,w;
}e[MAXn]; 
void Add(int xx,int yy,int zz){
    cnt++;
    e[cnt].to=yy;
    e[cnt].w=zz;
    e[cnt].nxt=h[xx];
    h[xx]=cnt;
}
void dij(int s){
    memset(d,0x3f,sizeof(d));
    d[s]=0; 
    q.push((Heapnode){0,s});
    while(!q.empty()){
        Heapnode x=q.top();
        q.pop();
        int t=x.u;
        if(vis[t]==1)continue;
        vis[t]=1;
        for(int i=h[t];i!=-1;i=e[i].nxt){
            int v=e[i].to;
            if(vis[v]==0&&d[v]>d[t]+e[i].w){
                d[v]=d[t]+e[i].w;
                q.push((Heapnode){d[v],v});
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>xx>>yy>>zz;
        Add(xx,yy,zz);
    }
    dij(s);
    for(int i=1;i<=n;i++){
        if(d[i]==0x3f3f3f3f)cout<<INF<<" ";
        else cout<<d[i]<<" ";
    }
    return 0;
}

(3)全源最短路

P5905 【模板】全源最短路（Johnson）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int MAXN=200000;
const int MAXn=500010;
const int INF=1000000000;
long long h[MAXN],vis[MAXN],d[MAXN],xx,yy,zz,ct[MAXN];
int n,m,s,cnt=0;
struct Heapnode{
    int w,u;
    bool operator <(const Heapnode &x)const{
        return w>x.w;
    }
};
priority_queue<Heapnode>q;
queue<long long>qw;
struct Node{
    int to,next,w;
}e[MAXn]; 
void Add(int xx,int yy,int zz){
    cnt++;
    e[cnt].to=yy;
    e[cnt].w=zz;
    e[cnt].next=h[xx];
    h[xx]=cnt;
}
long long dd[100005];
void dij(int s){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)dd[i]=INF;
    dd[s]=0;                                                                                                                
    q.push((Heapnode){0,s});
    while(!q.empty()){
        Heapnode x=q.top();
        q.pop();
        int t=x.u;
        if(vis[t]==1)continue;
        vis[t]=1;
        for(int i=h[t];i;i=e[i].next){
            int v=e[i].to;
            if(dd[v]>dd[t]+e[i].w){
                dd[v]=dd[t]+e[i].w;
                if(vis[v]==0)q.push((Heapnode){dd[v],v});
            }
        }
    }
    return ;
}
bool SPFA(int s){
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(ct,0,sizeof(ct));
    ct[s]=1;
    d[s]=0;
    qw.push(s);
    vis[s]=1;
    while(!qw.empty()){
        int u=qw.front();qw.pop();
        vis[u]=0;
        for(int i=h[u];i>0;i=e[i].next){
            int x=e[i].to;
            if(d[x]>d[u]+e[i].w){
                d[x]=d[u]+e[i].w;
                if(vis[x]==0){
                    ct[x]=ct[x]+1;
                    if(ct[x]>n)return 1;
                    vis[x]=1;
                    qw.push(x);
                }
            }
        }       
    }
    return 0;
}
signed main(){

    memset(h,0,sizeof(h));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>xx>>yy>>zz;
        Add(xx,yy,zz);
    }
    for(int i=1;i<=n;i++)Add(0,i,0);
    bool f=SPFA(0);
    if(f==1){
        cout<<-1;
        return 0;
    }

    for(int j=1;j<=n;j++)
        for(int i=h[j];i;i=e[i].next)
            e[i].w+=d[j]-d[e[i].to];

    for(int i=1;i<=n;i++){
        dij(i);
        long long ans=0;

        for(int j=1;j<=n;j++){
            if(dd[j]==INF)ans+=j*INF;
            else ans+=(dd[j]+d[j]-d[i])*j;
        }
        cout<<ans<<endl;
    }
    return 0;
}

2.最小生成树

P3366 【模板】最小生成树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5010;
long long n,m,f[MAXN],ans=0,z=0;
long long cnt=0;
struct Node{
    int u,v,w;  
}e[200000];
bool cmp(Node x,Node y){
    return x.w<y.w;
}
int Find(int x){
    if(f[x]==x)return x;
    else return f[x]=Find(f[x]);
}
void kru(){

    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int x=Find(e[i].u);
        int y=Find(e[i].v);
        if(x!=y){
            f[y]=x;
            ans+=e[i].w;
            if(++cnt==n-1)break;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);        
    kru();
    if(cnt==n-1)cout<<ans;
    else cout<<"orz";
    return 0;
}

3.tarjan

P3387 【模板】缩点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int MAXN=1e4+10;
const int MAXn=1e5+10;
int n,m,num,xx,yy;
int head[MAXN],to[MAXn],nxt[MAXn],pred[MAXN],d[MAXN],dfn[MAXN],low[MAXN],co[MAXN],col;
int head2[MAXN], to2[MAXn], nxt2[MAXn];
void add(int xx,int yy){
    to[++num]=yy;
    nxt[num]=head[xx];
    head[xx]=num;
}
void add2(int xx,int yy){
    to2[++num]=yy;
    nxt2[num]=head2[xx];
    head2[xx]=num;
}
stack<int>s;
void tarjan(int u){
    dfn[u]=low[u]=++num;
    s.push(u);
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        } 
        else if(!co[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        co[u]=++col;
        while(s.top()!=u){
            co[s.top()]=col;
            s.pop();
        }
        s.pop();
    }
}
int ans,f[MAXN];
void dp(int u){
    if(f[u])return;
    int ss=0;
    f[u]=d[u];
    for(int i=head2[u];i;i=nxt2[i]){
        int v=to2[i];
        dp(v);
        ss=max(ss, f[v]);
    }
    f[u]+=ss;
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>pred[i];
    for(int i=1;i<=m;i++){
        cin>>xx>>yy;
        add(xx,yy);
    }
    num=col=0;
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)d[co[i]] += pred[i];
    num=0;
    for(int i=1;i<=n;i++) {
        for(int j=head[i];j;j=nxt[j]){
            int v=to[j];
            if(co[v]!=co[i])add2(co[i],co[v]);
        }
    }
    n=col;
    for(int i=1;i<=n;i++) 
        if(!f[i]){
            dp(i);
            ans=max(ans, f[i]);
        }
    cout<<ans<<endl;
    return 0;
}

P3388 【模板】割点（割顶）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=5e5+10;
const int INF=1e9;
struct Node{
    int nxt,to;
}e[MAXN];
int n,m,cnt=0,tot=0,root;
int dfn[MAXN],low[MAXN],vis[MAXN],head[MAXN];
void add(int a,int b){
    e[++tot].nxt=head[a];
    e[tot].to=b;
    head[a]=tot;
}
void tarjan(int x){
    int fc=0;
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
            if(x==root)fc++;
            if(dfn[x]<=low[v]&&x!=root)
            vis[x]=1;
        }
        else low[x]=min(low[x],dfn[v]);
    }
    if(x==root&&fc>=2)vis[x]=1;

}
int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])root=i,tarjan(i);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(vis[i]) ans++;
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
        if(vis[i])cout<<i<<" ";
    return 0;
}

4.负环

P3385 【模板】负环

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=10010;
const int MAXn=500010;
int n,m,s,xx,yy,zz,minx=2147483647,cnt=0;
int dis[MAXN],vis[MAXN],h[MAXN],ct[MAXN];
queue<int>q;
struct Node{
    int to,next,w;
}e[MAXn]; 
bool SPFA(int s){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(ct,0,sizeof(ct));
    ct[s]=1;
    dis[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=h[u];i>0;i=e[i].next){
            int x=e[i].to;
            if(dis[x]>dis[u]+e[i].w){
                ct[x]=ct[u]+1;
                dis[x]=dis[u]+e[i].w;

                if(vis[x]==0){
                    if(ct[x]>n)return 1;
                    vis[x]=1;
                    q.push(x);
                }
            }
        }       
    }
    return 0;
}
void Add(int xx,int yy,int zz){
    cnt++;
    e[cnt].to=yy;
    e[cnt].w=zz;
    e[cnt].next=h[xx];
    h[xx]=cnt;
}
int main(){
//freopen("qunqun.txt","r",stdin);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        cnt=0;
        memset(h,0,sizeof(h));
        for(int i=1;i<=m;i++){
            cin>>xx>>yy>>zz;
            Add(xx,yy,zz);
            if(zz>=0)Add(yy,xx,zz); 
        }
        int f=SPFA(1);
        if(f==1)cout<<"YES"<<endl;
        else cout<<"NO\n";
    //  while(!q.empty())q.pop();   
    }
    return 0;
}

5.拓扑排序

P4017 最大食物链计数

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int Mod=80112002;
int h[500005],cu[500005],ru[500005],q[500005],u,v,tail=0,ansq,ans[500005];
int cnt=0;
struct Node{
    int to,next,w;
}e[500005];
void Add(int x,int y){
    cnt++;
    e[cnt].to=y;
    e[cnt].next=h[x];
    h[x]=cnt;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        Add(u,v);
        ru[v]++;
        cu[u]++;
    }
    for(int i=1;i<=n;i++)
        if(ru[i]==0){
            ans[i]=1; 
            q[++tail]=i;
        } 
    int head=0;
    while(head<tail){
        int a=q[++head];
        for(int i=h[a];i;i=e[i].next){
            int b=e[i].to;
            ans[b]=(ans[a]+ans[b])%Mod;
            ru[b]--;
            if(ru[b]==0&&cu[b]==0){
                ansq+=ans[b];
                ansq%=Mod;
            }
            else if(ru[b]==0)q[++tail]=b;
        }
    }
    cout<<ansq;
    return 0;
}

6.最短路计数

P1144 最短路计数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=2000010;
const int MAXn=2000010;
const int Mod=100003;
const int INF=(long long)(1<<31)-1;
int h[MAXN],vis[MAXN],d[MAXN],xx,yy,zz,ans[MAXN];
int n,m,s,cnt=0;
struct Heapnode{
    int w,u;
    bool operator <(const Heapnode &x)const{
        return w>x.w;
    }
};
priority_queue<Heapnode>q;
struct Node{
    int to,nxt,w;
}e[2*MAXn]; 
void Add(int xx,int yy){
    cnt++;
    e[cnt].to=yy;
    e[cnt].nxt=h[xx];
    h[xx]=cnt;
}
void dij(int s){
    memset(d,0x3f,sizeof(d));
    d[s]=0; 
//  vis[s]=1;
    ans[1]=1;
    q.push((Heapnode){0,s});
    while(!q.empty()){
        Heapnode x=q.top();
        q.pop();
        int t=x.u;
        if(vis[t]==1)continue;
        vis[t]=1;
        for(int i=h[t];i!=-1;i=e[i].nxt){
            int v=e[i].to;
            if(vis[v]==0){
                if(d[v]>d[t]+1){
                    d[v]=d[t]+1;
                    q.push((Heapnode){d[v],v});
                    ans[v]=ans[t];
                }
                else if(d[v]==d[t]+1){
                    ans[v]+=ans[t];
                    ans[v]%=Mod;
                }
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&xx,&yy);
        Add(xx,yy);
        Add(yy,xx);
    }
    dij(1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}

7.二分图

P3386 【模板】二分图最大匹配

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=5e5+10;
struct Node{
    int to,nxt;
}e[MAXN*2];
int n,m,ee,h[MAXN],cnt=0,ans=0,vis[MAXN],p[MAXN];
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=h[u];
    h[u]=cnt;
}
bool dfs(int u){
    if(vis[u]++)return 0;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!p[v]||dfs(p[v])){
            p[v]=u;
            return 1;
        }
    }
    return 0;
}
int main(){
    cin>>n>>m>>ee;
    for(int i=1;i<=ee;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;i++){
        if(dfs(i))ans++;
        memset(vis,0,sizeof(vis));
    }
    cout<<ans;
    return 0;
}

五.数据结构

1.树与二叉树

P5076 【深基16.例7】普通二叉树（简化版）

/*求 x 的前驱（前驱定义为小于 x，且最大的数）误区1：右孩子的父亲是满足要求的数吗？未必，更有可能是右孩子的左孩子，或者在左孩子分支上的数 
误区2：左孩子的左孩子是满足要求的数吗？ 未必，有可能是左孩子数上的某个点。
误区3：x的前驱，在树上未必是x的父亲或者孩子，有可能是其祖先或者孙子，意味着他们未必紧邻 
求后继一样 
*/ 
#include<cstdio>
#include<iostream>
const int INF=0x7fffffff;
using namespace std;
struct Node{
    int da,l,r,f;
    int lnum,rnum,dnum;//记录左右孩子的数量 ,和根节点数字出现的次数 
}tr[10010];
int n,tot,p;
void btree(int x,int root){//如果有0值出现，要特别注意 
    if(x==tr[root].da) {
        tr[root].dnum++;
        return ;
    }
    if(x<tr[root].da){//左子树 
        tr[root].lnum++;//左子树的结点数加1 
        if(tr[root].l==0) {//如果左子树不存在 
            tr[++tot].da=x;//树的节点数tot+1 
            tr[root].l=tot;
            tr[tot].dnum=1;
            tr[tot].f=root;
        }
        else btree(x,tr[root].l);//如果左子树存在 
    } 
    else {
        tr[root].rnum++;
        if(tr[root].r==0) {
            ++tot;
            tr[tot].da=x;
            tr[root].r=tot;
            tr[tot].dnum=1;
            tr[tot].f=root;
        }
        else btree(x,tr[root].r);
    }
}
int Find(int x,int root){
    if(root==0) return 0;//找不到 ，没有排名 ,不要忘了找不到的处理，否则死循环，这是循环的截止条件 
    if(tr[root].da==x) return tr[root].lnum;//不要忘了左子树上节点的个数 
    if(x<tr[root].da)return Find(x,tr[root].l);//去左子树查找 
    else return Find(x,tr[root].r)+tr[root].lnum+tr[root].dnum;//不要忘了前面已经有的节点数num 
}
int pm(int x,int root){
    if(root==0) return INF;//找不到排名为无限大 
    if(x>tr[root].lnum&&x<=tr[root].lnum+tr[root].dnum) return tr[root].da;
    if(x<=tr[root].lnum){
        return pm(x,tr[root].l);
    }
    if(x>tr[root].lnum+tr[root].dnum) return pm(x-tr[root].lnum-tr[root].dnum,tr[root].r);
}
int cx(int x,int root,int ansq){//root是当前节点的下标。
//  if(root==0)return ansq;//如果当前节点为空说明没有前驱 
    if(tr[root].da>=x){//如果相等看左孩子树或者ansq 
        //第一个比他小的数是其父亲 ? 如果root在左子树上，则其前驱只能在root的左子树上 
        int u=tr[root].l;//左孩子的下标。如果root在右子树上，若root的左子树存在，则其前驱只能在root的左子树上，否则前驱可能是其祖先 
        if(u==0) return ansq;
        return cx(x,u,ansq);    
    }
    else{
        if(tr[root].r==0) return tr[root].da; 
        cx(x,tr[root].r,tr[root].da);//前驱在右子树上，或者就是当前的根节点（右子树没有左孩子的时候） 
    }
}
int hz(int x,int root,int ansh){ //后继定义为大于 x，且最小的数
//  if(root==0)return ansh;
    if(x<tr[root].da){//去左子树找 
        if(tr[root].l==0) return tr[root].da;//如果左子树不存在，则当前值为后继 
         return hz(x,tr[root].l,tr[root].da);//当前root有可能成为后继 
    }
    else{
        if(tr[root].r==0) return ansh;
        return hz(x,tr[root].r,ansh);
    } 
}
int main(){
    scanf("%d",&n);
    tr[0].da=-2147483647 ;//根1的前驱 
    for(int i=1;i<=n;i++){
        int x,y;
        int ansq=-2147483647;
        int ansh=2147483647;
        scanf("%d%d",&y,&x);
        if(y==1){// 查询 x 数的排名
            cout<<Find(x,1)+1<<endl;//+1为什么要最后加？ 
        }
        if(y==2) cout<< pm(x,1)<<endl;//查询排名为 x的数
        if(y==3) cout<<cx(x,1,ansq)<<endl;//求 x 的前驱
        if(y==4) cout<<hz(x,1,ansh)<<endl;//求 x 的后继 
        if(y==5) {//插入一个数 x
            if(p==0) {
                tr[1].da=x;
                tr[1].dnum=1;
                tot=1;
                p=1;
            }
            else btree(x,1);
        }
    }
    return 0;
}

P4913 【深基16.例3】二叉树深度

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=1e6+10;
int n,ans,x,y;
struct Node{
    int l,r;
}a[MAXN];
int f[MAXN];
void Dfs(int son,int dep){
    if(f[son]==0){
        if(dep>ans)ans=dep;
        return;
    }
    Dfs(f[son],dep+1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        f[x]=f[y]=i;
        a[i].l=x;
        a[i].r=y;
    }
    for(int i=1;i<=n;i++)
        if(a[i].l==0&&a[i].r==0)
            Dfs(i,1);
    cout<<ans<<endl;
    return 0;
}

P1030 [NOIP2001 普及组] 求先序排列

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
string ldr,lrd;
void dfs(int zs,int zt,int hs,int ht){
    char ch=lrd[ht-1];
    cout<<ch;
    int x=ldr.find(ch);
    if(x>zs)dfs(zs,x,hs,hs+(x-zs));
    if(x+1<zt)dfs(x+1,zt,hs+(x-zs),ht-1);
}                     
int main(){  
    cin>>ldr;
    cin>>lrd;
    int len=ldr.size();
    dfs(0,len,0,len);
    return 0;
}

延申并查集（重要）

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

合并（Union）：合并两个元素所属集合（合并对应的树）查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

P1551 亲戚

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,q,f[10010],c,d,a,b;
int fd(int x){
    if(f[x]==x)return x;
    else return  f[x]=fd(f[x]);
}
void hb(int x,int y){
    f[fd(y)]=fd(x);
    return;
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>c>>d;
        hb(c,d);  
    }
    for(int i=1;i<=q;i++){
        cin>>a>>b;
        if(fd(a)==fd(b))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

延申 LCA 重要

P3379 【模板】最近公共祖先（LCA）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=500010;
int n,m,s,h[MAXN],d[MAXN],fa[MAXN][20],cnt;
inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while((ch>'9'||ch<'0')&&ch!='-')
        ch=getchar();
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
    char F[200];
    int tmp=x>0?x:-x ;
    if(x<0)putchar('-') ;
    int cnt=0 ;
    while(tmp>0){
        F[cnt++]=tmp%10+'0';
        tmp/=10;
    }
    while(cnt>0)putchar(F[--cnt]) ;
}
struct Node{
    int u,v,nxt;
}e[MAXN*2];
inline void add(int xx,int yy){
    e[++cnt].v=yy;
    e[cnt].nxt=h[xx];
    h[xx]=cnt;
}
inline int LCA(int x,int y){
    int k=log(n)/log(2);
    if(d[x]<d[y])swap(x,y);
    for(int i=k;i>=0;i--)
        if(d[fa[x][i]]>=d[y])x=fa[x][i];
    if(x==y)return y;
    for(int i=k;i>=0;i--)
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i]; 
            y=fa[y][i];
        }
    return fa[x][0];
}
inline void init(){
    int k=log(n)/log(2);
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
}
inline void dfs(int u,int f,int dep){
    for(int i=h[u];i!=-1;i=e[i].nxt){
        int v=e[i].v;
        if(v!=f){
            d[v]=dep+1;
            fa[v][0]=u;
            dfs(v,u,dep+1);
        }   
    }
}
signed main(){
    n=read();m=read();s=read();
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++){
        int xx,yy;
        xx=read();
        yy=read();
        add(xx,yy);
        add(yy,xx);
    }
    d[s]=1;
    dfs(s,0,1);
    init();
    while(m--){
        int x,y;
        x=read();
        y=read();//cin>>x>>y;
        write(LCA(x,y));
        printf("\n");
    }
    return 0;
}

2.树状数组与线段树

P3372 【模板】线段树 1

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1002010;
long long n,w,a[MAXN];
struct Node{
    int l,r;
    long long dat,laz;
}tr[MAXN*4];
void build(int p,int l,int r){//建树 
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);//左子树 
    build(2*p+1,mid+1,r);//右子树 
    tr[p].dat=tr[2*p].dat+tr[2*p+1].dat;
}
void spread(int p){
    if(tr[p].laz){
        tr[2*p].dat+=(tr[2*p].r-tr[2*p].l+1)*tr[p].laz;
        tr[2*p+1].dat+=(tr[2*p+1].r-tr[2*p+1].l+1)*tr[p].laz;
        tr[2*p].laz+=tr[p].laz;
        tr[2*p+1].laz+=tr[p].laz;
        tr[p].laz=0;
    }
}
void Change(int p,int l,int r,long long k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].dat+=(tr[p].r-tr[p].l+1)*k;
        tr[p].laz+=k;
        return;
    }
    spread(p);//传递 
    int mid=(tr[p].l+tr[p].r)/2;
    if(l<=mid)Change(2*p,l,r,k);
    if(r>mid) Change(2*p+1,l,r,k);
    tr[p].dat=tr[p*2].dat+tr[2*p+1].dat;
}
long long ask(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)return tr[p].dat;
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    long long val=0;
    if(l<=mid)val+=ask(2*p,l,r);
    if(r>mid) val+=ask(2*p+1,l,r);
    return val;
}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);//根节点 区间 
    for(int i=1;i<=w;i++){
        char ch;
        int u;
        cin>>ch>>u;
        if(ch=='1'){
            int v;
            long long k;
            cin>>v>>k;
            Change(1,u,v,k);
        }
        else{
            long long v;
            cin>>v;
            long long ans=ask(1,u,v);
            cout<<ans<<endl;     
        } 
    } 
    return 0;
}

P3373 【模板】线段树 2

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1002010;
long long n,w,a[MAXN];
struct Node{
    int l,r;
    long long dat,laz;
}tr[MAXN*4];
void build(int p,int l,int r){//建树 
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);//左子树 
    build(2*p+1,mid+1,r);//右子树 
    tr[p].dat=tr[2*p].dat+tr[2*p+1].dat;
}
void spread(int p){
    if(tr[p].laz){
        tr[2*p].dat+=(tr[2*p].r-tr[2*p].l+1)*tr[p].laz;
        tr[2*p+1].dat+=(tr[2*p+1].r-tr[2*p+1].l+1)*tr[p].laz;
        tr[2*p].laz+=tr[p].laz;
        tr[2*p+1].laz+=tr[p].laz;
        tr[p].laz=0;
    }
}
void Change(int p,int l,int r,long long k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].dat+=(tr[p].r-tr[p].l+1)*k;
        tr[p].laz+=k;
        return;
    }
    spread(p);//传递 
    int mid=(tr[p].l+tr[p].r)/2;
    if(l<=mid)Change(2*p,l,r,k);
    if(r>mid) Change(2*p+1,l,r,k);
    tr[p].dat=tr[p*2].dat+tr[2*p+1].dat;
}
long long ask(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)return tr[p].dat;
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    long long val=0;
    if(l<=mid)val+=ask(2*p,l,r);
    if(r>mid) val+=ask(2*p+1,l,r);
    return val;
}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);//根节点 区间 
    for(int i=1;i<=w;i++){
        char ch;
        int u;
        cin>>ch>>u;
        if(ch=='1'){
            int v;
            long long k;
            cin>>v>>k;
            Change(1,u,v,k);
        }
        else{
            long long v;
            cin>>v;
            long long ans=ask(1,u,v);
            cout<<ans<<endl;     
        } 
    } 
    return 0;
}

P3374 【模板】树状数组 1

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1002010;
long long n,w,a[MAXN];
struct Node{
    int l,r;
    long long dat,laz;
}tr[MAXN*4];
void build(int p,int l,int r){//建树 
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);//左子树 
    build(2*p+1,mid+1,r);//右子树 
    tr[p].dat=tr[2*p].dat+tr[2*p+1].dat;
}
void spread(int p){
    if(tr[p].laz){
        tr[2*p].dat+=(tr[2*p].r-tr[2*p].l+1)*tr[p].laz;
        tr[2*p+1].dat+=(tr[2*p+1].r-tr[2*p+1].l+1)*tr[p].laz;
        tr[2*p].laz+=tr[p].laz;
        tr[2*p+1].laz+=tr[p].laz;
        tr[p].laz=0;
    }
}
void Change(int p,int l,int r,long long k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].dat+=(tr[p].r-tr[p].l+1)*k;
        tr[p].laz+=k;
        return;
    }
    spread(p);//传递 
    int mid=(tr[p].l+tr[p].r)/2;
    if(l<=mid)Change(2*p,l,r,k);
    if(r>mid) Change(2*p+1,l,r,k);
    tr[p].dat=tr[p*2].dat+tr[2*p+1].dat;
}
long long ask(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)return tr[p].dat;
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    long long val=0;
    if(l<=mid)val+=ask(2*p,l,r);
    if(r>mid) val+=ask(2*p+1,l,r);
    return val;
}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);//根节点 区间 
    for(int i=1;i<=w;i++){
        char ch;
        int u;
        cin>>ch>>u;
        if(ch=='1'){
            int v;
            long long k;
            cin>>v>>k;
            Change(1,u,v,k);
        }
        else{
            long long v;
            cin>>v;
            long long ans=ask(1,u,v);
            cout<<ans<<endl;     
        } 
    } 
    return 0;
}

P3368 【模板】树状数组 2

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1002010;
long long n,w,a[MAXN];
struct Node{
    int l,r;
    long long dat,laz;
}tr[MAXN*4];
void build(int p,int l,int r){//建树 
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);//左子树 
    build(2*p+1,mid+1,r);//右子树 
    tr[p].dat=tr[2*p].dat+tr[2*p+1].dat;
}
void spread(int p){
    if(tr[p].laz){
        tr[2*p].dat+=(tr[2*p].r-tr[2*p].l+1)*tr[p].laz;
        tr[2*p+1].dat+=(tr[2*p+1].r-tr[2*p+1].l+1)*tr[p].laz;
        tr[2*p].laz+=tr[p].laz;
        tr[2*p+1].laz+=tr[p].laz;
        tr[p].laz=0;
    }
}
void Change(int p,int l,int r,long long k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].dat+=(tr[p].r-tr[p].l+1)*k;
        tr[p].laz+=k;
        return;
    }
    spread(p);//传递 
    int mid=(tr[p].l+tr[p].r)/2;
    if(l<=mid)Change(2*p,l,r,k);
    if(r>mid) Change(2*p+1,l,r,k);
    tr[p].dat=tr[p*2].dat+tr[2*p+1].dat;
}
long long ask(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)return tr[p].dat;
    spread(p);
    int mid=(tr[p].l+tr[p].r)/2;
    long long val=0;
    if(l<=mid)val+=ask(2*p,l,r);
    if(r>mid) val+=ask(2*p+1,l,r);
    return val;
}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);//根节点 区间 
    for(int i=1;i<=w;i++){
        char ch;
        int u;
        cin>>ch>>u;
        if(ch=='1'){
            int v;
            long long k;
            cin>>v>>k;
            Change(1,u,v,k);
        }
        else{
            long long v;
            cin>>v;
            long long ans=ask(1,u,v);
            cout<<ans<<endl;     
        } 
    } 
    return 0;
}

3.st表

P3865 【模板】ST 表 && RMQ 问题

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const int MAXN=2000010;
int m,n,f[MAXN][20],l,r,ans;
void st(){
    int k=log(n)/log(2);
    for(int j=1;j<=k;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int qq(int l,int r){
    int kk;
    kk=log(r-l+1)/log(2);
    ans=max(f[l][kk],f[r-(1<<kk)+1][kk]);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)cin>>f[i][0];
    st();
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        printf("%d\n",qq(l,r));
    }
    return 0;
}

六.字符串

1.KMP

P3375 【模板】KMP

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1e6+10;
int nxt[MAXN];
char s[MAXN],p[MAXN];
int main(){
    scanf("%s",s+1);
    scanf("%s",p+1);
    int n=strlen(s+1);
    int m=strlen(p+1);
    int j=0;
    for(int i=2;i<=m;i++){
        while(j&&p[i]!=p[j+1])j=nxt[j];
        if(p[i]==p[j+1])j++;
        nxt[i]=j;
    }
    j=0;
    for(int i=1;i<=n;i++){
        while(j&&s[i]!=p[j+1])j=nxt[j];
        if(s[i]==p[j+1])j++;
        if(j==m)cout<<i-m+1<<endl;
    }
    for(int i=1;i<=m;i++)
        cout<<nxt[i]<<" ";
    return 0;
}

2.hash

我们定义一个把字符串映射到整数的函数 f，这个 f 称为是 Hash 函数。

我们希望这个函数 f 可以方便地帮我们判断两个字符串是否相等。

P3370 【模板】字符串哈希

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define int unsigned long long
using namespace std;
const int MAXN=10010;
const int mod=121312313221;
const int jz=21133;
char s[MAXN];
int n,a[MAXN];
int h(char c[]){
    int len=strlen(c);
    int ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*jz+(int)s[i])%mod;
    return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        a[i]=h(s);
    }
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=2;i<=n;i++)
        if(a[i]!=a[i-1])ans++;
    cout<<ans+1;
    return 0;
}

七.数论

1.中国剩余定理

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN=100;
int n,a[MAXN],b[MAXN],ans,c;
int gbs(int a,int b){
    return a*b/ __gcd(a,b);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    c=a[1];
    ans=b[1];
    for(int i=2;i<=n;i++){
        while(ans%a[i]!=b[i])ans+=c;
        c=gbs(c,a[i]);
    }
    cout<<ans;
    return 0;
}

2.线性筛

P3383 【模板】线性筛素数

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1e8+20;
bool vis[MAXN];
int p[MAXN];
int n,q,cnt,d;
void io(){
    std::ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL); 
}
void pri(int k){
    vis[1]=1;
    for(int i=2;i<=k;i++){
        if(!vis[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<k;j++){
            vis[i*p[j]]=1;
            if(!(i%p[j]))break;
        }
    }
}
int main(){
    io();
    cin>>n>>q;
    pri(n);
    for(int i=1;i<=q;i++){
        cin>>d;
        cout<<p[d]<<endl;
    }
    return 0;
}

八.二分三分

1.二分

(1)整数二分

P1314 [NOIP2011 提高组] 聪明的质监员

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=200010;
long long sum[MAXN],cnt[MAXN],w[MAXN],l[MAXN],r[MAXN],v[MAXN];
long long n,m,s;
long long check(int W) {
    for(long long i=1;i<=n;i++){
        if(w[i]>=W){
            sum[i]=sum[i-1]+v[i];
            cnt[i]=cnt[i-1]+1;
        }
        else{
            sum[i]=sum[i-1];
            cnt[i]=cnt[i-1];
        }
    }
    long long y=0;
    for(long long i=1;i<=m;i++)
        y+=(sum[r[i]]-sum[l[i]-1])*(cnt[r[i]]-cnt[l[i]-1]);
    return y;
}
long long ef(){
    long long l=0,r=1104514;
    long long mid;
    while(l<r){
        mid=(r+l+1)/2;
        if(check(mid)>=s)l=mid;
        else r=mid-1;
    }
    long long ans=min(abs(check(l)-s),abs(check(l+1)-s));
    return ans;
}
int main(){
    cin>>n>>m>>s;
    for(long long i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(long long i=1;i<=m;i++){
        cin>>l[i]>>r[i];
    }
    cout<<ef();
    return 0;
}

(2)实数二分

P1024 [NOIP2001 提高组] 一元三次方程求解

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const double eps=1e-10;
const double INF=1e9;
double n,a,b,c,d;
double f(double x){
    return (a*pow(x,3))+(b*pow(x,2))+c*x+d;
}
double solve(){
    double l,r,mid;
    for(int i=-100;i<=100;i++){
        double l=i,r=i+1-eps,mid;
            if(f(l)*f(r)<=0){
                while(r-l>=eps){
                    mid=(l+r)/2;
                    if(f(l)*f(mid)<=0)r=mid;
                    else l=mid;
                }
                printf("%.2lf ",l);
            }
    }
}
int main(){
    cin>>a>>b>>c>>d;
    solve();
    return 0;
}

2.三分

P1883 【模板】三分 | 函数

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=100010;
double a[MAXN],b[MAXN],c[MAXN];
int t,n;
double f(double x,int i){
    return x*x*a[i]+x*b[i]+c[i];
} 
double check(double x){
    double ans=f(x,1);
    for(int i=1;i<=n;i++)ans=max(ans,f(x,i));
    return ans;
}
void awa(){
    double eps=1e-11;
    double l=0,r=1000,mid1,mid2;
    while(fabs(r-l)>eps){
        mid1=(l+r)/2;
        mid2=(mid1+r)/2;
        if(check(mid1)>check(mid2))l=mid1;
        else r=mid2;
    }
    printf("%.4lf\n",check(l));
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
        awa();
    }
    return 0;
}

九.差分

P2367 语文成绩

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int MAXN=5000010;
int n,p,x,y,z,a[MAXN],d[MAXN];
int ans=1e9;
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)d[i]=a[i]-a[i-1];
    for(int i=1;i<=p;i++){
        cin>>x>>y>>z;
        d[x]+=z;
        d[y+1]-=z;
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+d[i];
        if(ans>a[i])ans=a[i];
    }
    cout<<ans;
    return 0;
}

若有不尽人意或缺失之处请私信我补充谢谢

update 2024.10.5

zjt_AKUYTRE

csp 复赛 算法模板总结