ACM常用模板

最大值与次大值的科学求法

Cm = 0,说明不存在次大值;

    int a[]={,,,,};
    int Zm=,Cm=;
    for(int i=;i<;i++){
        if(a[i]>Cm){
            Cm=a[i];
        }
        if(Cm>Zm) Zm=Cm;
    }
    cout<<M1<<" "<<M2<<endl;

数位dp经典模板（不要62）

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define pb push_back
#define LL long long
LL dp[][];
int a[];
LL dfs(int pos,int pre,bool lead0,bool limit){
    if(pos==-) return ;
    if(!limit && !lead0 && dp[pos][pre]!=-) return dp[pos][pre];
    int up=limit ?a[pos] :;
    LL ans=;
    for(int i=;i<=up;i++){
        int nle=(i==&&lead0);
        int nli=(i==up&&limit);
        if(i==||(i==&&pre==)) continue;
        ans+=dfs(pos-,i,nle,nli);
    }
    if(!limit && !lead0) dp[pos][pre]=ans;
    return ans;
}
LL solve(LL x){
    int w=;
    while(x){
        a[w++]=x%;
        x/=;
    }
    return dfs(w-,-,true,true);
}
int main()
{
    memset(dp,-,sizeof(dp));
    LL l,r;
    while(~scanf("%lld %lld",&l,&r)){
        if(l+r==) break;
        printf("%lld\n",solve(r)-solve(l-));
    }
    return ;
}

结构体内部排序的方法（适用于set的自动排序）

struct Node {
    int id,s;
    Node(int _i,int _s):id(_i),s(_s) {}
    bool operator < (const Node& b) const {
        if(s!=b.s) return s<b.s;
        else return id<b.id;
    }
};

中国剩余定理（互质与非互质通用版）

int m[],r[];
int e_gcd(int a,int b,int &x,int &y) {
    if(b==) {
        x=;
        y=;
        return a;
    }
    int ans=e_gcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
int Zhong() {
    int M = m[],R = r[];
    for(int i = ; i < ; i++) {
        int c = r[i]-R,x,y;
        int gcd = e_gcd(M,m[i],x,y);
        if(c%gcd != ) return -;
        x = c*x;
        x = (x+m[i]) % m[i];
        int X = x*M + R;
        M = m[i]/gcd*M;
        R = X % M;
    }
    return (R%M+M)%M;
}

线段树(求区间最大值)：

const int N = 1e6+;
#define lc 2*node
#define rc 2*node+1
#define MAX 1e9
int seg[N*+],dp[N];
void Build(int node,int l,int r){
    if(l == r) seg[node] = MAX;
    else {
        int mid = (l+r)>>;
        Build(lc,l,mid);
        Build(rc,mid+,r);
        seg[node] = min(seg[lc],seg[rc]);
    }
}
void Update(int node,int l,int r,int k,int num){
    if(l==r) {
       seg[node] = num;
       return;
    }
    int mid = (l+r)>>;
    if(k <= mid) Update(lc,l,mid,k,num);
    else Update(rc,mid+,r,k,num);
    seg[node] = min(seg[lc],seg[rc]);
}
int query(int node,int l,int r,int ql,int qr){
    int p1,p2;
    if(ql > r || qr < l) return MAX;
    if(l >= ql && r <= qr) return seg[node];
    int mid = (l+r)>>;
    p1 = query(lc,l,mid,ql,qr);
    p2 = query(rc,mid+,r,ql,qr);
    return min(p1,p2);
}

 求逆元（含扩展欧几里得）

ll ex_gcd(ll a,ll b,ll &x,ll &y) {
    if(b==) {
        x=;
        y=;
        return a;
    }
    ll ans=ex_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ans;
}

要求 a和b的最大公约数是1，然后x = (x+b)%b 将x转到正确的区间，x就是a的逆元。

zkw费用流

const int N = ;
const int M = ;
const int INF = 1e9;
const double eps = 1e-;
struct Edge {
    int next,cap,v;
    double cost;
    Edge() {}
    Edge(int vv,int ca,double co,int ne) {
        v=vv;
        cap = ca;
        cost=co;
        next=ne;
    }
} edge[M];
int head[N],e,vis[N];
double d[N],cost,ans;
int src,des;
void init() {
    memset(head, -, sizeof(head));
    e = ;
    ans = cost = ;
}
void addEdge(int u, int v, int cap, double cost) {
    edge[e] = Edge(v,cap,cost,head[u]);
    head[u] = e++;
    edge[e] = Edge(u,,-cost,head[v]);
    head[v] = e++;
}
int aug(int u, int f) {
    if(u == des) {
        ans += cost * f;
        return f;
    }
    vis[u] = ;
    int tmp = f;
    for(int i = head[u]; i != -; i = edge[i].next)
        if(edge[i].cap && fabs(edge[i].cost)<eps && !vis[edge[i].v]) {
            int delta = aug(edge[i].v, tmp < edge[i].cap ? tmp : edge[i].cap);
            edge[i].cap -= delta;
            edge[i^].cap += delta;
            tmp -= delta;
            if(!tmp) return f;
        }
    return f - tmp;
}
bool modlabel() {
    for(int i = src; i <= des; i++) d[i] = INF;
    d[des] = ;
    deque<int>Q;
    Q.push_back(des);
    while(!Q.empty()) {
        int u = Q.front();
        double tmp;
        Q.pop_front();
        for(int i = head[u]; i != -; i = edge[i].next) {
            tmp =  d[u]-edge[i].cost;
            if(edge[i^].cap && d[edge[i].v]>tmp+eps){
                d[edge[i].v] = tmp;
                double a = tmp;
                double b = d[Q.empty() ?src :Q.front()];
                (b>a+eps||(fabs(a-b)<eps)) ?Q.push_front(edge[i].v) :Q.push_back(edge[i].v);
            }
        }

    }
    for(int u = src; u <= des; u++)
        for(int i = head[u]; i != -; i = edge[i].next)
            edge[i].cost += d[edge[i].v] - d[u];
    cost += d[src];
    return d[src] < INF;
}
void costflow() {
    while(modlabel()) {
        do {
            memset(vis, , sizeof(vis));
        } while(aug(src, INF));
    }
}

zkw费用流修正版

const int N = ;
const int M = ;
const int INF = 1e9;
const double eps = 1e-;
struct Edge {
    int next,cap,v;
    double cost;
    Edge() {}
    Edge(int vv,int ca,double co,int ne) {
        v=vv;
        cap = ca;
        cost=co;
        next=ne;
    }
} edge[M];
int head[N],e,vis[N];
double d[N],cost,ans;
int src,des;
void init() {
    memset(head, -, sizeof(head));
    e = ;
    ans = cost = ;
}
void addEdge(int u, int v, int cap, double cost) {
    edge[e] = Edge(v,cap,cost,head[u]);
    head[u] = e++;
    edge[e] = Edge(u,,-cost,head[v]);
    head[v] = e++;
}
int aug(int u, int f) {
    if(u == des) {
        ans += cost * f;
        return f;
    }
    vis[u] = ;
    int tmp = f;
    for(int i = head[u]; i != -; i = edge[i].next)
        if(edge[i].cap && fabs(edge[i].cost)<eps && !vis[edge[i].v]) {
            int nxtf = min(tmp,edge[i].cap);
            int delta = aug(edge[i].v,nxtf);
            edge[i].cap -= delta;
            edge[i^].cap += delta;
            tmp -= delta;
            if(!tmp) return f;
        }
    return f - tmp;
}
bool modlabel() {
    for(int i = src; i <= des; i++) d[i] = INF;
    d[des] = ;
    deque<int>Q;
    Q.push_back(des);
    while(!Q.empty()) {
        int u = Q.front();
        double a,b;
        Q.pop_front();
        for(int i = head[u]; i != -; i = edge[i].next) {
            a =  d[u]-edge[i].cost;
            if(edge[i^].cap && d[edge[i].v]>a+eps) {
                d[edge[i].v] = a;
                b = d[Q.empty() ?src :Q.front()];
                if(b>a+eps||(fabs(a-b)<eps)) {
                    Q.push_front(edge[i].v);
                } else Q.push_back(edge[i].v);
            }
        }
    }
    for(int u = src; u <= des; u++)
        for(int i = head[u]; i != -; i = edge[i].next)
            edge[i].cost += d[edge[i].v] - d[u];
    cost += d[src];
    return d[src] < INF;
}
void costflow() {
    while(modlabel()) {
        do {
            memset(vis, , sizeof(vis));
        } while(aug(src, INF));
    }
}

spfa最小费用最大流

const int N = ;
const int M = N*N;
const int INF = 1e9;
struct Edge {
    int from, to, cap, flow, cost, next;
};
Edge edge[M];
int head[N],pre[N],dist[N],edgenum;
bool vis[N];
int source, sink;
void init() {
    edgenum = ;
    memset(head, -, sizeof(head));
}
void addEdge(int u, int v, int w, int c) {
    Edge E1 = {u, v, w, , c, head[u]};
    edge[edgenum] = E1;
    head[u] = edgenum++;
    Edge E2 = {v, u, , , -c, head[v]};
    edge[edgenum] = E2;
    head[v] = edgenum++;
}
bool SPFA(int s, int t) {
    queue<int> Q;
    while(!Q.empty()) Q.pop();
    for(int i=;i<N;i++) dist[i]=INF;
    memset(vis, false, sizeof(vis));
    memset(pre, -, sizeof(pre));
    dist[s] = ;
    vis[s] = true;
    Q.push(s);
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -; i = edge[i].next) {
            Edge E = edge[i];
            if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow) {
                dist[E.to] = dist[u] + E.cost;
                pre[E.to] = i;
                if(!vis[E.to]) {
                    vis[E.to] = true;
                    Q.push(E.to);
                }
            }
        }
    }
    return pre[t] != -;
}
void MCMF(int s, int t, int &cost, int &flow) {
    flow = ;
    cost = ;
    while(SPFA(s, t)) {
        int Min = INF;
        for(int i = pre[t]; i != -; i = pre[edge[i^].to]) {
            Edge E = edge[i];
            Min = min(Min, E.cap - E.flow);
        }
        for(int i = pre[t]; i != -; i = pre[edge[i^].to]) {
            edge[i].flow += Min;
            edge[i^].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
}

Dinic算法求最大流（邻接表版本）

#define INF 0x3f3f3f3f
#define MAX_V 20
#define MAX_E 2000
struct edge {
    int to,cap,rev;
    edge(int a=,int b=,int c=) :to(a),cap(b),rev(c) {}
};
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
void init(int v) {
    for(int i=; i<=v; i++) G[i].clear();
}
void addedge(int from,int to,int cap) {
    G[from].push_back( edge(to,cap,G[to].size()));
    G[to].push_back( edge(from,,G[from].size()-));
}
void bfs(int s) {
    memset(level,-,sizeof(level));
    queue<int> que;
    level[s]=;
    que.push(s);
    while(!que.empty()) {
        int v=que.front();
        que.pop();
        for(int i=; i<G[v].size(); i++) {
            edge &e=G[v][i];
            if(e.cap>&&level[e.to]<) {
                level[e.to]=level[v]+;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f) {
    if(v==t) return f;
    for(int &i=iter[v]; i<G[v].size(); i++) {
        edge &e=G[v][i];
        if(e.cap>&&level[v]<level[e.to]) {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>) {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return ;
}
int max_flow(int s,int t) {
    int flow=;
    while(true) {
        bfs(s);
        if(level[t]<) return flow;
        memset(iter,,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>) flow+=f;
    }
}

Dinic算法链式前向星版本（可以有序储存反向弧）

const int INF=0x3f3f3f3f;
const int N=;
const int M=**;
int n,p;
int s,t,e_max,fir[N],dis[N],q[N];
struct Node {
    int c;
    int in[],ou[];
} a[N];
struct edge {
    int u,v,w,nex;
} e[M];
void add_edge(int u,int v,int w,int x) {
    if(x==) return;
    e[e_max].u=u;
    e[e_max].v=v;
    e[e_max].w=w;
    e[e_max].nex=fir[u];
    fir[u]=e_max++;
    add_edge(v,u,,x+);
}
int bfs() {
    int i,x,v,tail=,head=;
    memset(dis,,sizeof(dis));
    dis[s]=;
    q[tail++]=s;
    while(head<tail) {
        x=q[head++];
        for(i=fir[x]; i!=-; i=e[i].nex)
            if(e[i].w&&dis[v=e[i].v]==) {
                dis[v]=dis[x]+;
                if(v==t)
                    return ;
                q[tail++]=v;
            }
    }
    return ;
}
int dfs(int s,int limit) {
    if(s==t)
        return limit;
    int i,v,tmp,cost=;
    for(i=fir[s]; i!=-; i=e[i].nex)
        if(e[i].w&&dis[s]==dis[v=e[i].v]-) {
            tmp=dfs(v,min(limit-cost,e[i].w));
            if(tmp>) {
                e[i].w-=tmp;
                e[i^].w+=tmp;
                cost+=tmp;
                if(limit==cost)
                    break;
            } else dis[v]=-;
        }
    return cost;
}
int Dinic() {
    int ans=;
    while(bfs())
        ans+=dfs(s,INF);
    return ans;
}
void init() {
    s=;
    t=n+;
    memset(fir,-,sizeof(fir));
    e_max=;
}

Dinic算法（修正版）

const int N = ;
const int INF = 1e9;
const int M = N*N;
struct edge {
    int u,v,w,nex;
} e[M];
int s,t,e_max,fir[N],dis[N],q[N];
void init() {
    memset(fir,-,sizeof(fir));
    e_max=;
}
void add_edge(int u,int v,int w,int x) {
    if(x==) return;
    e[e_max].u=u;
    e[e_max].v=v;
    e[e_max].w=w;
    e[e_max].nex=fir[u];
    fir[u]=e_max++;
    add_edge(v,u,,x+);
}
int bfs() {
    int i,x,v,tail=,head=;
    memset(dis,,sizeof(dis));
    dis[s]=;
    q[tail++]=s;
    while(head<tail) {
        x=q[head++];
        for(i=fir[x]; i!=-; i=e[i].nex)
            if(e[i].w&&dis[v=e[i].v]==) {
                dis[v]=dis[x]+;
                if(v==t)
                    return ;
                q[tail++]=v;
            }
    }
    return ;
}
int dfs(int s,int limit) {
    if(s==t)
        return limit;
    int i,v,tmp,cost=;
    for(i=fir[s]; i!=-; i=e[i].nex)
        if(e[i].w&&dis[s]==dis[v=e[i].v]-) {
            tmp=dfs(v,min(limit-cost,e[i].w));
            if(tmp>) {
                e[i].w-=tmp;
                e[i^].w+=tmp;
                cost+=tmp;
                if(limit==cost)
                    break;
            } else dis[v]=-;
        }
    return cost;
}
int Dinic() {
    int ans=;
    while(bfs())
        ans+=dfs(s,INF);
    return ans;
}

普通母函数解决整数拆分组合数（完全背包也可以解决）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int c1[],c2[];
int A[];

int main()
{
    int T,N,K;
    cin >> T;
    while(T--)
    {
        cin >> N >> K;
        memset(A,,sizeof(A));
        for(int i = ; i <= K; ++i)
        {
            int a,b;
            cin >> a >> b;
            A[a] = b;
        }
        for(int i = ; i <= N; ++i)
            c1[i] = c2[i] = ;
        c1[] = ;
        for(int i = ; i <= K; ++i) //第i项表达式(1+x^2+...)
        {
            for(int j = ; j <= N; ++j)
            //前面i个表达式累乘的表达式(前一表达式)里第j个变量
            {
            /*如(1+x)(1+x^2)(1+x^3)，j先指示的是1和x的系数，i=2执行完之后变为（1+x+x^2+x^3）(1+x^3)，这时候j应该指示的是合并后的第一个括号的四个变量的系数。*/
                for(int k = ; j+i*k <= N && k <= A[i]; ++k)
                    c2[j+i*k] += c1[j];//c2[]保存结果
            }// k表示的是将要计算的表达式的每项。(因为第i个表达式的增量是i，所以k每次增i)。
            for(int j = ; j <= N; ++j)
            {
                c1[j] = c2[j];//迭代
                c2[j] = ;
            }
        }
        cout << c1[N] << endl;
    }
    return ;
}

 指数型母函数问题：
 假设有8个元素，其中a1重复3次，a2重复2次，a3重复3次。从中取r个组合，求其排列数。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

double f[] = {,,,,,,,,,,};
double num[],c1[],c2[];
int main()
{
    int N,M;
    while(cin >> N >> M)
    {
        memset(c1,,sizeof(c1));
        memset(c2,,sizeof(c2));
        for(int i = ; i < N; ++i)
            cin >> num[i];
        for(int i = ; i <= num[]; ++i)
            c1[i] = 1.0/f[i];
        for(int i = ; i < N; ++i)
        {
            for(int j = ; j <= M; ++j)
                for(int k = ; k <= num[i] && (k+j)<=M; ++k)
                    c2[k+j] += (c1[j]/f[k]);
            for(int j = ; j <= M; ++j)
            {
                c1[j] = c2[j];
                c2[j] = ;
            }
        }
        double s = 1.0*c1[M]*f[M];
        printf("%.0lf\n",s);
    }

    return ;
}

 树状数组区间更新，单点查询与区间更新

单点查询值

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1e5+;
int c[N],n,m,a[N];
int lowbit(int x){
    return x&(-x);
}
void update(int k,int x){
    for(int i=k;i<=m;i+=lowbit(i)){
        c[i]+=x;
    }
}
int getsum(int k){
    int sum=;
    while(k){
        sum+=c[k];
        k-=lowbit(k);
    }
    return sum;
}
int main()
{
    int l,r,x,q;
    while(~scanf("%d%d%d",&m,&n,&q)){
        memset(c,,sizeof(c));
        for(int i=;i<=m;i++) {
            scanf("%d",&a[i]);
        }
        for(int i=;i<=n;i++){
            scanf("%d%d%d",&l,&r,&x);
            update(l,x);
            update(r+,-x);
        }
//        for(int i=1;i<=m;i++){
//            cout<<"::  "<<getsum(i)<<endl;
//        }
        for(int i=;i<=q;i++){
            scanf("%d%d",&l,&r);
            int ans=;
            for(int j=l;j<=r;j++){
                if(a[j]-getsum(j) < ){
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
    }
    return ;
}

区间查询值

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1e5+;
#define LL long long
LL c1[N],c2[N],s[N];
int n,q,l,r;
int lowbit(int x) {
    return x&(-x);
}
void update(LL *a,int i,LL d) {
    while(i<=n) {
        a[i] += d;
        i+=lowbit(i);
    }
}
LL getsum(LL* a,int i) {
    LL sum=;
    while(i>) {
        sum+=a[i];
        i-=lowbit(i);
    }
    return sum;
}
void Gupdate(int l,int r,LL tmp) {
    update(c1,l,tmp);
    update(c1,r+,-tmp);
    update(c2,l,tmp*l);
    update(c2,r+,-tmp*(r+));
}
LL getAns(int l,int r) {
    LL ans=s[r]-s[l-];
    ans += (r+)*getsum(c1,r)-l*getsum(c1,l-);
    ans -= getsum(c2,r)-getsum(c2,l-);
    return ans;
}
int main() {
    LL tmp;
    char c[];
    while(~scanf("%d%d",&n,&q)) {
        memset(c1,,sizeof(c1));
        memset(c2,,sizeof(c2));
        s[]=;
        for(int i=; i<=n; i++) {
            scanf("%lld",&tmp);
            s[i]=s[i-]+tmp;
        }
        while(q--) {
            scanf("%s%d%d",c,&l,&r);
            if(c[]=='Q') {
                printf("%lld\n",getAns(l,r));
            } else {
                scanf("%lld",&tmp);
                Gupdate(l,r,tmp);
            }
        }
    }
    return ;
}