ACM模板 - 持续更新中

快速幂

typedef long long ll;

ll mod_pow(ll x,ll n,ll mod)
{
    ll res=1;
    while(n>0)
    {
        if(n&1)//if(n%2==1)
            res=res*x%mod;
        x=x*x%mod;//把x平方
        n>>=1;//n=n/2 舍去最后一位
    }
    return res;
}

如果用来取模的数本身很大，快速幂会爆掉的话，加上快速乘来优化时间，以达到大数相乘取模

typedef long long ll;
ll mod_pow(ll x,ll n,ll mod)
{
    ll res=1;
    while(n>0)
    {
        if(n&1)
            res = mod_mulit(res,x,mod);
        x = mod_multi(x,x,mod);
        n >>= 1;
    }
    return res;
}

树状数组

查询区间和，引申：查询区间最值差

int lowbit(int x)//lowbit(x)表示2^k
{
    return x&(-x);
}

void update(int x,int k)//在位置x增加k
{
    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}

int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

memset(c,0,sizeof(c));//输入记得清空

for(int i=1; i<=n; i++)//树状数组处理的是下标为1的数组
{
    scanf("%d",&a[i]);
    update(i,a[i]);//开始的时候每个元素初始值为0,对应位置加a[i]即可
}

最长公共子序列

char/int a[55],b[55];
int dp[55][55];//dp若是太大，就利用滚动数组取余处理
int lcs()
{
    //(char)
    int la=strlen(a);
    int lb=strlen(b);
    for(int i=0;i

欧几里得算法

（辗转相除法）

可以调用__gcd(a,b); v或者自己写函数，函数如下

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return(b,a%b);
}

扩展欧几里得

求\(ax+by=gcd(a,b)\)的整数解\(x\)、\(y\)，同时可以求出最大公因数。

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int yin=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
    //x1=y2,
    //y1=x2-(a/b)*y2;
    return yin;
}

int main()
{
    int a,b,x,y;
    scanf("%d %d",&a,&b);
    int maxx=exgcd(a,b,x,y);//最大公因数
    return 0;
}

扩展欧几里得求逆元

以上两种解法均要满足a、p互质。
逆元定义：ax ≡ 1 (mod p) 满足a乘以x对p取模等于1 ，此时称 x为a对p的逆元。
只有a与p互质才有逆元 ，互质即gcd(a,p)=1
问法：求 ：(a/b)%p；转化成 (ax)%p （即需要求b的逆元x），即bx≡1modp，设一个未知数y，则有bx+py=1（x即为所求逆元）（简介化成扩展欧几里得问题，因为b、p互质，所以gcd(b,p)=1 ）。

int inverse(int b,int p)//求b的逆元x
{
    int d=ex_gcd(b,p,x,y);//这里面的参数x就是所求逆元
    if(d==1)
        return (x%p+p)%p;
    //防止逆元为负，若需要负数作为逆元则return x即可
    return -1;//逆元不存在则返回-1
}

Dijkstra

void  dijkstra()
{
    memset(book,0,sizeof(book));
    for(int i=1;i<=n;i++)
        dis[i]=e[1][i];
    book[1]=1;
    int u;
    for(int i=2;i<=n;i++)
    {
        int minn=inf;
        for(int j=1;j<=n;j++)
        {
            if(book[j]==0&&dis[j]

Kruskal

//kruskal
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
#define inff 0x3f3f3f3f3f3f3f3f
const int N=2200;
#define mod 998244353
typedef long long ll;

int f[N];
char a[N][10];

struct node
{
    int l,r,d;
} e[N*N];

int getf(int x)
{
    if(f[x]==x)
        return x;
    return f[x]=getf(f[x]);
}

int merge(int x,int y)
{
    int t1=getf(x);
    int t2=getf(y);
    if(t1!=t2)
    {
        f[t2]=t1;
        return 1;
    }
    return 0;
}

bool cmp1(node x,node y)
{
    return x.d>n)
    {
        if(n==0)
            break;
        memset(e,0,sizeof(e));
        /*for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    e[i][j]=0;
                else
                    e[i][j]=inf;
            }
        }*/
        for(int i=1; i<=n; i++)
        {
            scanf("%s",a[i]);
            f[i]=i;
        }
        int p=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                //for(int j=i+1; j<=n; j++)
            {
                int sum=0;
                for(int k=0; k<7; k++)
                {
                    if(a[i][k]!=a[j][k])
                        sum++;
                }
                //e[i][j]=e[j][i]=sum;
                e[p].l=i;
                e[p].r=j;
                e[p++].d=sum;
            }
        }
        int w,ans=0;
        sort(e,e+p,cmp1);
        for(int i=0; i

Prim

//prim
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
#define inff 0x3f3f3f3f3f3f3f3f
const int N=2200;
#define mod 998244353
typedef long long ll;

int e[N][N],dist[N];
int n,ans;
bool book[N];
char a[N][10];

void prim()
{
    int countt=1;//countt代表点数，而不是边数
    ans=0;//记录路径长度
    for(int i=1;i<=n;i++)
    {
        dist[i]=e[1][i];
        book[i]=0;
    }
    book[1]=1;
    while(countte[u][i])
            {
                dist[i]=e[u][i];
            }
        }
    }

}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        if(n==0)
            break;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    e[i][j]=0;
                else
                    e[i][j]=inf;
            }
        }
        for(int i=1; i<=n; i++)
            scanf("%s",a[i]);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                //for(int j=i+1; j<=n; j++)
            {
                int sum=0;
                for(int k=0; k<7; k++)
                {
                    if(a[i][k]!=a[j][k])
                        sum++;
                }
                e[i][j]=e[j][i]=sum;
            }
        }
        prim();
        cout<<"The highest possible quality is 1/"<

最短路和最小生成树区别

最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。
最短路径是从一点出发，到达目的地的路径最小。

网络流

#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
const int N=220;

int e[N][N],pre[N];
int n,m,s,t;
bool book[N];
int maxflow;


bool bfs()
{
    memset(book,false,sizeof(book));
    memset(pre,0,sizeof(pre));
    queueQ;
    Q.push(s);
    book[s]=true;

   while(!Q.empty())
    {
        int p=Q.front();
        Q.pop();
        if(p==t)
            return true;
        for(int i=1; i<=n; i++)
        {
            if(book[i]==false)
            {
                if(e[p][i]>0)
                {
                    book[i]=true;
                    pre[i]=p;
                    Q.push(i);
                }
            }
        }
    }
    return false;
}


int solve()
{
    maxflow=0;
    while(1)
    {
        if(bfs()==false)
            return maxflow;
        int minn=inf;
        for(int i=t; i!=s; i=pre[i])
            minn=min(minn,e[pre[i]][i]);
        for(int i=t; i!=s; i=pre[i])
        {
            e[pre[i]][i]-=minn;
            e[i][pre[i]]+=minn;
        }
        maxflow+=minn;
    }
}

int main()
{
    int u,v,w;
    int tt=1,ttt;
    {
        while(~scanf("%d %d",&m,&n))
        {
            memset(e,0,sizeof(e));
            s=1,t=n;
            for(int i=1; i<=m; i++)
            {
                scanf("%d %d %d",&u,&v,&w);
                e[u][v]+=w;
            }
            printf("%d\n",solve());
        }
    }
    return 0;
}

KMP

查找子串（模式串）在原串中出现了几次。

char s[10020],t[1000020];
int lens,lent;
int nextt[10020];
void getnext()
{
    int i=0,j=-1;
    nextt[0]=-1;
    while(i

01背包

//HDU-4508
#include
#include
#include
using namespace std;
int dp[2000000];
int main()
{
    int w[110],v[110];
    int n,i,m,j;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i

SPFA

注意：SPFA是求单源最短路径的，是BF的队列优化。因为Dijkstra无法处理负权边，BF算法的复杂度过高，所以可以用SPFA。SPFA的复杂度大约是O(kE),k是每个点的平均进队次数(一般的，k是一个常数，在稀疏图中小于2)，但是，SPFA算法稳定性较差，在稠密图中SPFA算法时间复杂度会退化。SPFA算法还可以判断图中是否有负权环，即一个点入队次数超过N。

队列的写法：（这个是判断负环的）

int n,tot,dis[N],head[N],cnt[N];
bool book[N];
//cnt记录每个点入队的次数,间接用来判断负环（cnt根据题意开）

struct node
{
    int v,w,nex;
} e[M<<2];

void add(int u,int v,int w)
{
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nex=head[u];
    head[u]=tot;
}

bool SPFA()
{
    for(int i=1; i<=n; i++)
        book[i]=0,cnt[i]=0,dis[i]=inf;
    queueQ;
// 注意：队列开在外面会造成内存超限，
//因为开在函数内部函数结束后就会释放内存，开在外面就相当于全局变量就不会释放内存
//如果只执行一次就没区别
//但是可以自己先手动清空队列再用
    Q.push(1);
    dis[1]=0,book[1]=1,cnt[1]++;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        book[u]=0;
        for(int i=head[u]; i!=-1; i=e[i].nex)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                if(!book[v])
                    Q.push(v),cnt[v]++,book[v]=1;
                if(cnt[v]==n)   // 如果不存在负环最多更新n-1次
                    return 0;
            }
        }
    }
    return 1;
}

int main()
{
    tot=-1,mem(head,-1);
    if(SPFA())
        cout<<"NO"<

栈的写法（该模板是POJ3159的）

void spfa()
{
    //mem(book,0); //清不清都AC
    for(int i=1;i<=n;i++)
        dis[i]=inf; // 两个都可 fill(dis,dis+N,inf);
    stack S;//用栈，队列超时
    while(!S.empty())
        S.pop();
    dis[0]=0,book[0]=1;
    S.push(0);
    while(!S.empty())
    {
        int p=S.top();
        S.pop();
        book[p]=0;
        for(int i=head[p];i!=-1;i=e[i].nex)
        {
            int v=e[i].v;
            int t=e[i].w;
            if(dis[v]>dis[p]+t)
            {
                dis[v]=dis[p]+t;
                if(!book[v])
                {
                    book[v]=1;
                    S.push(v);
                }
            }
        }
    }
}

线段树

区间修改（A->B）、查询

#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
#define mem(p,b) memset(p,b,sizeof(p))
#define inf 0x3f3f3f3f
typedef long long ll;

const int N=1e5+20;
ll a[N<<2],lazy[N<<2];//需要开到节点的四倍大小

void build(int L,int R,int i)
{
    if(L==R)//当左右结点相同的时候，说明该节点可以建树，输入即可。
    {
        scanf("%lld",&a[i]);//即为叶子结点
        return;//因为已经确定这个点可以输入了，也就类似叶结点，返回函数上次调用的地方即可。
    }

    //否则往下继续找
    int mid=(L+R)>>1;
    build(L,mid,i<<1);//递归建立左子树
    build(mid+1,R,i<<1|1);//递归建立右子树
    a[i]=a[i<<1]+a[i<<1|1];//统计该点(i)的左子树和右子树之和
    //a这个操作也可以另外写到一个函数pushup中(即pushup(i))，这个看自己怎么写代码
    //节点数据向上更新

    //根据题意写，这一题是求区间和，之前左区间和右区间相加即可
    //例如如果求区间内最大值，则写成：a[i]=max(a[i<<1],a[i<<1|1]);
}

void pushdown(int i,int len)//节点懒惰标记下推
{
    if(lazy[i])//如果懒惰标记为真，说明之前有过懒惰标记，现在需要进行更新
    {
//        lazy[i<<1]+=lazy[i];//懒惰标记往左结点传
//        lazy[i<<1|1]+=lazy[i];//懒惰标记往右结点传
//        //左右用 |1 区分
//        //因为求区间和，所以当区间内每个元素加上一个值时，区间的和也加上这个值
//        //对于区间求和, 原数组值需要加上lazy标记*子树所统计的区间长度
//        a[i<<1]+=lazy[i]*(len-(len>>1));//(len-(len>>1)是左区间的长度
//        a[i<<1|1]+=lazy[i]*(len>>1);//(len>>1)是右区间的长度
//        lazy[i]=0;//由于懒惰标记向下传递，所以当前节点的懒惰标记取消
        lazy[i<<1]=lazy[i];
        lazy[i<<1|1]=lazy[i];
        a[i<<1]=lazy[i]*(len-(len>>1));
        a[i<<1|1]=lazy[i]*(len>>1);
        lazy[i]=0;
    }
    //对于区间求最大值, 子树的值不需要乘以长度, 所以不需要传递参数区间长度len。
}

//注意：
// 1、单点更新, 不需要用到lazy标记
// 2、成段(区间)更新, 需要用到lazy标记来提高时间效率
void update(int x,int y,int L,int R,int i,int pluss)
{
    if(L>=x&&R<=y)//当前节点区间包含在查询区间内
        //范围缩小到left和right之间
    {
//        a[i]+=pluss*(R-L+1);
//        lazy[i]+=pluss;
        a[i]=pluss*(R-L+1);
        lazy[i]=pluss;
        return;
    }
    pushdown(i,R-L+1);
    int mid=(L+R)>>1;

    //更新区间
    if(x<=mid)//更新左区间
        update(x,y,L,mid,i<<1,pluss);
    if(y>mid)//更新右区间
        update(x,y,mid+1,R,i<<1|1,pluss);

    //更新结点值
    a[i]=a[i<<1]+a[i<<1|1];
}

ll query(int x,int y,int L,int R,int i)//查询操作
{
    if(L>=x&&R<=y)//当前节点区间包含在查询区间内
        return a[i];//返回当前值
    pushdown(i,R-L+1);
    int mid=(L+R)>>1;
    ll ans=0;
    if(x<=mid)//递归查询左子树内部的的区间值
        ans+=query(x,y,L,mid,i<<1);
    if(y>mid)//递归查询右子树内部的的区间值
        ans+=query(x,y,mid+1,R,i<<1|1);
    return ans;//返回题目所需的区间和（左+右）
}

int main()
{
    int n,q;
    scanf("%d",&n);
    build(1,n,1);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int t,x,y;
        scanf("%d %d %d",&t,&x,&y);
        if(t==0)
            printf("%lld\n",query(x,y,1,n,1));
        else
        {
            int c;
            scanf("%d",&c);
            update(x,y,1,n,1,c);//修改为c，不是加上
        }
    }
    return 0;
}

线段树区间修改（A->A+B）、查询

//题意：
//C：对区间[l,r]每一个数+c；
// Q:查询区间[l,r]的所有元素的总和。

//线段树修改和查找的时间复杂度都是O(logn)。
//线段树基本思想：分治。
//线段树基本操作:建树、区间查询(最值;和)、区间修改(更新)、单点修改、单点查询。

#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
#define inf 0x3f3f3f3f;
#define pi acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
typedef long long ll;

const int N=1e5+20;
ll a[N<<2],lazy[N<<2];//需要开到节点的四倍大小

void build(int L,int R,int i)
{
    if(L==R)//当左右结点相同的时候，说明该节点可以建树，输入即可。
    {
        scanf("%lld",&a[i]);//即为叶子结点
        return;//因为已经确定这个点可以输入了，也就类似叶结点，返回函数上次调用的地方即可。
    }

    //否则往下继续找
    int mid=(L+R)>>1;
    build(L,mid,i<<1);//递归建立左子树
    build(mid+1,R,i<<1|1);//递归建立右子树
    a[i]=a[i<<1]+a[i<<1|1];//统计该点(i)的左子树和右子树之和
    //a这个操作也可以另外写到一个函数pushup中(即pushup(i))，这个看自己怎么写代码
    //节点数据向上更新

    //根据题意写，这一题是求区间和，之前左区间和右区间相加即可
    //例如如果求区间内最大值，则写成：a[i]=max(a[i<<1],a[i<<1|1]);
}

void pushdown(int i,int len)//节点懒惰标记下推
{
    if(lazy[i])//如果懒惰标记为真，说明之前有过懒惰标记，现在需要进行更新
    {
        lazy[i<<1]+=lazy[i];//懒惰标记往左结点传
        lazy[i<<1|1]+=lazy[i];//懒惰标记往右结点传
        //左右用 |1 区分
        //因为求区间和，所以当区间内每个元素加上一个值时，区间的和也加上这个值
        //对于区间求和, 原数组值需要加上lazy标记*子树所统计的区间长度
        a[i<<1]+=lazy[i]*(len-(len>>1));//(len-(len>>1)是左区间的长度
        a[i<<1|1]+=lazy[i]*(len>>1);//(len>>1)是右区间的长度
        lazy[i]=0;//由于懒惰标记向下传递，所以当前节点的懒惰标记取消
    }
    //对于区间求最大值, 子树的值不需要乘以长度, 所以不需要传递参数区间长度len。
}

//注意：
// 1、单点更新, 不需要用到lazy标记
// 2、成段(区间)更新, 需要用到lazy标记来提高时间效率
void update(int x,int y,int L,int R,int i,int pluss)
{
    if(L>=x&&R<=y)//当前节点区间包含在查询区间内
        //范围缩小到left和right之间
    {
        a[i]+=pluss*(R-L+1);
        lazy[i]+=pluss;
        return;
    }
    pushdown(i,R-L+1);
    int mid=(L+R)>>1;

    //更新区间
    if(x<=mid)//更新左区间
        update(x,y,L,mid,i<<1,pluss);
    if(y>mid)//更新右区间
        update(x,y,mid+1,R,i<<1|1,pluss);

    //更新结点值
    a[i]=a[i<<1]+a[i<<1|1];
}

ll query(int x,int y,int L,int R,int i)//查询操作
{
    if(L>=x&&R<=y)//当前节点区间包含在查询区间内
        return a[i];//返回当前值
    pushdown(i,R-L+1);
    int mid=(L+R)>>1;
    ll ans=0;
    if(x<=mid)//递归查询左子树内部的的区间值
        ans+=query(x,y,L,mid,i<<1);
    if(y>mid)//递归查询右子树内部的的区间值
        ans+=query(x,y,mid+1,R,i<<1|1);
    return ans;//返回题目所需的区间和（左+右）
}

int main()
{
    int n,q;
    while(~scanf("%d %d",&n,&q))
    {
        mem(lazy,0);//如果多组数据lazy数组需要进行清空
        mem(a,0);
        build(1,n,1);//开始建树，传入树的总区间(传入最左端点，最右端点)和树的根节点
        //建树的过程中输入每一个节点
        for(int i=1;i<=q;i++)
        {
            char ch;
            getchar();//吸收每次读入的空格
            scanf("%c",&ch);
            if(ch=='Q')//询问区间内的和
            {
                int x,y;
                scanf("%d %d",&x,&y);
                ll ans=query(x,y,1,n,1);
                printf("%lld\n",ans);
            }else if(ch=='C')//往区间内每一个数上都插入pluss
            {
                int x,y,z;
                scanf("%d %d %d",&x,&y,&z);
                update(x,y,1,n,1,z);
            }
        }
    }
    return 0;
}

邻接表

int tot,head[N];

struct node
{
    int v,w,nex; //w权值
    // 根据题意加 花费 cost
}e[M];

void add(int u,int v,int w)
{
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nex=head[u];
    head[u]=tot;
   // e[tot].cost=cost;  根据题意加
}

int main()
{
    tot=-1;
    return 0;
}

三分

    double L=0,R=1e9;
    while(L+1e-3<=R) // while(R-L>=1e-3)
    {
        double m1=L+(R-L)/3,m2=R-(R-L)/3;
        if(f(m1)

并查集

int f[N];

int getf(int x)
{
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}

bool merge(int x,int y)
{
    int t1=getf(x);
    int t2=getf(y);
    if(t1==t2)
        return 1;
    f[t2]=t1;
    return 0;
}

int main()
{
    int n;
    for(int i=1;i<=n;i++)
        f[i]=i;
    return 0;
}

带权并查集

见：

二分

二分查找时间复杂度：O(log n)。

手写二分：

int binary_search(int a[],int len)
{
    int l=0,r=len-1,mid;  // 三个变量都表示下标
    int x; // 目标值
    while(l<=r)
    {
        int mid=(l+r)>>1;  // 最好 mid=mi+((ma-mi)>>1); 防止溢出
        if(a[mid]>x) r=mid-1;
        else if(a[mid]

二分函数：

#include 
using namespace std;

//upper_bound查找第一个大于某个元素的位置
//lower_bound查找第一个大于或等于某个元素的位置
// 返回下标位置

int a[10] = {0, 1, 3, 5, 7, 6, 2, 4, 8, 9};

int main()
{
    sort(a,a+10); // 需要排序！

    int w=upper_bound(a,a+9,4)-a; // 找数字4
    cout<
C++

相关

年功序列c++游戏

C++ ：string 用法详解

C++11 并发指南五(std::condition_variable 详解)

顺序存储的循环队列（c++实现）

C++中的各种定义

解析一下C++的异常处理

C++typename的由来和用法

C++多元组tuple使用方法？你熟悉吗？快来看看吧

使用vs2019用c++创建dll库

c++primer

C++ 天坑收集

077.C++中的引用-引用的注意事项

标签

一品网 冀ICP备14022925号-6