最大值与次大值的科学求法
Cm = 0,说明不存在次大值;
int a[10]={1,2,3,4,45}; int Zm=0,Cm=0; for(int i=0;i<5;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[20][10]; int a[20]; LL dfs(int pos,int pre,bool lead0,bool limit){ if(pos==-1) return 1; if(!limit && !lead0 && dp[pos][pre]!=-1) return dp[pos][pre]; int up=limit ?a[pos] :9; LL ans=0; for(int i=0;i<=up;i++){ int nle=(i==0&&lead0); int nli=(i==up&&limit); if(i==4||(i==2&&pre==6)) continue; ans+=dfs(pos-1,i,nle,nli); } if(!limit && !lead0) dp[pos][pre]=ans; return ans; } LL solve(LL x){ int w=0; while(x){ a[w++]=x%10; x/=10; } return dfs(w-1,-1,true,true); } int main() { memset(dp,-1,sizeof(dp)); LL l,r; while(~scanf("%lld %lld",&l,&r)){ if(l+r==0) break; printf("%lld ",solve(r)-solve(l-1)); } return 0; }
结构体内部排序的方法（适用于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[3],r[3]; int e_gcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; 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[0],R = r[0]; for(int i = 1; i < 3; i++) { int c = r[i]-R,x,y; int gcd = e_gcd(M,m[i],x,y); if(c%gcd != 0) return -1; 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+5; #define lc 2*node #define rc 2*node+1 #define MAX 1e9 int seg[N*4+10],dp[N]; void Build(int node,int l,int r){ if(l == r) seg[node] = MAX; else { int mid = (l+r)>>1; Build(lc,l,mid); Build(rc,mid+1,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)>>1; if(k <= mid) Update(lc,l,mid,k,num); else Update(rc,mid+1,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)>>1; p1 = query(lc,l,mid,ql,qr); p2 = query(rc,mid+1,r,ql,qr); return min(p1,p2); }
求逆元（含扩展欧几里得）
ll ex_gcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; 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 = 2005; const int M = 56666; const int INF = 1e9; const double eps = 1e-4; 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, -1, sizeof(head)); e = 0; ans = cost = 0; } 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,0,-cost,head[v]); head[v] = e++; } int aug(int u, int f) { if(u == des) { ans += cost * f; return f; } vis[u] = 1; int tmp = f; for(int i = head[u]; i != -1; 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^1].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] = 0; 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 != -1; i = edge[i].next) { tmp = d[u]-edge[i].cost; if(edge[i^1].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 != -1; 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, 0, sizeof(vis)); } while(aug(src, INF)); } }
zkw费用流修正版
const int N = 2005; const int M = 56666; const int INF = 1e9; const double eps = 1e-7; 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, -1, sizeof(head)); e = 0; ans = cost = 0; } 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,0,-cost,head[v]); head[v] = e++; } int aug(int u, int f) { if(u == des) { ans += cost * f; return f; } vis[u] = 1; int tmp = f; for(int i = head[u]; i != -1; 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^1].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] = 0; 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 != -1; i = edge[i].next) { a = d[u]-edge[i].cost; if(edge[i^1].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 != -1; 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, 0, sizeof(vis)); } while(aug(src, INF)); } }
spfa最小费用最大流
const int N = 105; 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 = 0; memset(head, -1, sizeof(head)); } void addEdge(int u, int v, int w, int c) { Edge E1 = {u, v, w, 0, c, head[u]}; edge[edgenum] = E1; head[u] = edgenum++; Edge E2 = {v, u, 0, 0, -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=0;i<N;i++) dist[i]=INF; memset(vis, false, sizeof(vis)); memset(pre, -1, sizeof(pre)); dist[s] = 0; vis[s] = true; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = false; for(int i = head[u]; i != -1; 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] != -1; } void MCMF(int s, int t, int &cost, int &flow) { flow = 0; cost = 0; while(SPFA(s, t)) { int Min = INF; for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { Edge E = edge[i]; Min = min(Min, E.cap - E.flow); } for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].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=0,int b=0,int c=0) :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=0; 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,0,G[from].size()-1)); } void bfs(int s) { memset(level,-1,sizeof(level)); queue<int> que; level[s]=0; que.push(s); while(!que.empty()) { int v=que.front(); que.pop(); for(int i=0; i<G[v].size(); i++) { edge &e=G[v][i]; if(e.cap>0&&level[e.to]<0) { level[e.to]=level[v]+1; 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>0&&level[v]<level[e.to]) { int d=dfs(e.to,t,min(f,e.cap)); if(d>0) { e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t) { int flow=0; while(true) { bfs(s); if(level[t]<0) return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(s,t,INF))>0) flow+=f; } }
Dinic算法链式前向星版本（可以有序储存反向弧）
const int INF=0x3f3f3f3f; const int N=60; const int M=60*60*2; int n,p; int s,t,e_max,fir[N],dis[N],q[N]; struct Node { int c; int in[15],ou[15]; } a[N]; struct edge { int u,v,w,nex; } e[M]; void add_edge(int u,int v,int w,int x) { if(x==2) 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,0,x+1); } int bfs() { int i,x,v,tail=0,head=0; memset(dis,0,sizeof(dis)); dis[s]=1; q[tail++]=s; while(head<tail) { x=q[head++]; for(i=fir[x]; i!=-1; i=e[i].nex) if(e[i].w&&dis[v=e[i].v]==0) { dis[v]=dis[x]+1; if(v==t) return 1; q[tail++]=v; } } return 0; } int dfs(int s,int limit) { if(s==t) return limit; int i,v,tmp,cost=0; for(i=fir[s]; i!=-1; i=e[i].nex) if(e[i].w&&dis[s]==dis[v=e[i].v]-1) { tmp=dfs(v,min(limit-cost,e[i].w)); if(tmp>0) { e[i].w-=tmp; e[i^1].w+=tmp; cost+=tmp; if(limit==cost) break; } else dis[v]=-1; } return cost; } int Dinic() { int ans=0; while(bfs()) ans+=dfs(s,INF); return ans; } void init() { s=0; t=n+1; memset(fir,-1,sizeof(fir)); e_max=0; }
Dinic算法（修正版）
const int N = 105; 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,-1,sizeof(fir)); e_max=0; } void add_edge(int u,int v,int w,int x) { if(x==2) 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,0,x+1); } int bfs() { int i,x,v,tail=0,head=0; memset(dis,0,sizeof(dis)); dis[s]=1; q[tail++]=s; while(head<tail) { x=q[head++]; for(i=fir[x]; i!=-1; i=e[i].nex) if(e[i].w&&dis[v=e[i].v]==0) { dis[v]=dis[x]+1; if(v==t) return 1; q[tail++]=v; } } return 0; } int dfs(int s,int limit) { if(s==t) return limit; int i,v,tmp,cost=0; for(i=fir[s]; i!=-1; i=e[i].nex) if(e[i].w&&dis[s]==dis[v=e[i].v]-1) { tmp=dfs(v,min(limit-cost,e[i].w)); if(tmp>0) { e[i].w-=tmp; e[i^1].w+=tmp; cost+=tmp; if(limit==cost) break; } else dis[v]=-1; } return cost; } int Dinic() { int ans=0; while(bfs()) ans+=dfs(s,INF); return ans; }
普通母函数解决整数拆分组合数（完全背包也可以解决）
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; int c1[1100],c2[1100]; int A[1100]; int main() { int T,N,K; cin >> T; while(T--) { cin >> N >> K; memset(A,0,sizeof(A)); for(int i = 1; i <= K; ++i) { int a,b; cin >> a >> b; A[a] = b; } for(int i = 0; i <= N; ++i) c1[i] = c2[i] = 0; c1[0] = 1; for(int i = 1; i <= K; ++i) //第i项表达式(1+x^2+...) { for(int j = 0; 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 = 0; j+i*k <= N && k <= A[i]; ++k) c2[j+i*k] += c1[j];//c2[]保存结果 }// k表示的是将要计算的表达式的每项。(因为第i个表达式的增量是i，所以k每次增i)。 for(int j = 0; j <= N; ++j) { c1[j] = c2[j];//迭代 c2[j] = 0; } } cout << c1[N] << endl; } return 0; }
指数型母函数问题：
假设有8个元素，其中a1重复3次，a2重复2次，a3重复3次。从中取r个组合，求其排列数。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; double f[] = {1,1,2,6,24,120,720,5040,40320,362880,3628800}; double num[11],c1[11],c2[11]; int main() { int N,M; while(cin >> N >> M) { memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); for(int i = 0; i < N; ++i) cin >> num[i]; for(int i = 0; i <= num[0]; ++i) c1[i] = 1.0/f[i]; for(int i = 1; i < N; ++i) { for(int j = 0; j <= M; ++j) for(int k = 0; k <= num[i] && (k+j)<=M; ++k) c2[k+j] += (c1[j]/f[k]); for(int j = 0; j <= M; ++j) { c1[j] = c2[j]; c2[j] = 0; } } double s = 1.0*c1[M]*f[M]; printf("%.0lf ",s); } return 0; }
树状数组区间更新，单点查询与区间更新
单点查询值
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int N = 1e5+5; 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=0; 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,0,sizeof(c)); for(int i=1;i<=m;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ scanf("%d%d%d",&l,&r,&x); update(l,x); update(r+1,-x); } // for(int i=1;i<=m;i++){ // cout<<":: "<<getsum(i)<<endl; // } for(int i=1;i<=q;i++){ scanf("%d%d",&l,&r); int ans=0; for(int j=l;j<=r;j++){ if(a[j]-getsum(j) < 0){ ans++; } } printf("%d ",ans); } } return 0; }
区间查询值
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int N = 1e5+5; #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=0; while(i>0) { sum+=a[i]; i-=lowbit(i); } return sum; } void Gupdate(int l,int r,LL tmp) { update(c1,l,tmp); update(c1,r+1,-tmp); update(c2,l,tmp*l); update(c2,r+1,-tmp*(r+1)); } LL getAns(int l,int r) { LL ans=s[r]-s[l-1]; ans += (r+1)*getsum(c1,r)-l*getsum(c1,l-1); ans -= getsum(c2,r)-getsum(c2,l-1); return ans; } int main() { LL tmp; char c[2]; while(~scanf("%d%d",&n,&q)) { memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); s[0]=0; for(int i=1; i<=n; i++) { scanf("%lld",&tmp); s[i]=s[i-1]+tmp; } while(q--) { scanf("%s%d%d",c,&l,&r); if(c[0]=='Q') { printf("%lld ",getAns(l,r)); } else { scanf("%lld",&tmp); Gupdate(l,r,tmp); } } } return 0; }