首页 > 代码库 > ACM常用模板整理
ACM常用模板整理
线段树单点修改区间查询
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int maxn=55555; struct segmentTree{ int sum; }tree[maxn<<2]; int per[maxn]; void PushUp(int rt){ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; } void build(int l,int r,int rt){ if(l==r){ tree[rt].sum=per[l]; return; } int mid=(l+r)/2; build(lson); build(rson); PushUp(rt); } void update(int x,int add,int l,int r,int rt){ if(l==r){ tree[rt].sum+=add; return; } int mid=(l+r)/2; if(x<=mid)update(x,add,lson); else update(x,add,rson); PushUp(rt); } int query(int a,int b,int l,int r,int rt){ if(a<=l&&b>=r){ return tree[rt].sum; } int ans=0; int mid=(l+r)/2; if(a<=mid) ans+=query(a,b,lson); if(b>mid) ans+=query(a,b,rson); return ans; } int main(){ int t,n,cas=1; scanf("%d",&t); while(t--){ scanf("%d",&n); printf("Case %d:\n",cas++); for(int i=1;i<=n;i++){ scanf("%d",&per[i]); } build(1,n,1); char op[11]; while(scanf("%s",op)!=EOF){ if(strcmp(op,"End")==0)break; if(strcmp(op,"Query")==0){ int a,b; scanf("%d%d",&a,&b); printf("%d\n",query(a,b,1,n,1)); } else if(strcmp(op,"Add")==0){ int a,b; scanf("%d%d",&a,&b); update(a,b,1,n,1); } else if(strcmp(op,"Sub")==0){ int a,b; scanf("%d%d",&a,&b); update(a,-b,1,n,1); } } } return 0; }
线段树同时维护和、最大值、最小值
#include <cstdio> #include <cstring> #define maxn 100000 + 10 #define Lson L, mid, rt<<1 #define Rson mid+1, R, rt<<1|1 int min(int a, int b) {return a<b ? a : b;} int max(int a, int b) {return a>b ? a : b;} struct Node { int sum, Min, Max, lazy; } T[maxn<<2]; void PushUp(int rt) { T[rt].sum = T[rt<<1].sum + T[rt<<1|1].sum; T[rt].Min = min(T[rt<<1].Min, T[rt<<1|1].Min); T[rt].Max = max(T[rt<<1].Max, T[rt<<1|1].Max); } void PushDown(int L, int R, int rt) { int mid = (L + R) >> 1; int t = T[rt].lazy; T[rt<<1].sum = t * (mid - L + 1); T[rt<<1|1].sum = t * (R - mid); T[rt<<1].Min = T[rt<<1|1].Min = t; T[rt<<1].Max = T[rt<<1|1].Max = t; T[rt<<1].lazy = T[rt<<1|1].lazy = t; T[rt].lazy = 0; } void Build(int L, int R, int rt) { if(L == R) { scanf("%d", &T[rt].sum); T[rt].Min = T[rt].Max = T[rt].sum; return ; } int mid = (L + R) >> 1; Build(Lson); Build(Rson); PushUp(rt); } void Update(int l, int r, int v, int L, int R, int rt) { if(l==L && r==R)//修改区间值 { T[rt].lazy = v; T[rt].sum = v * (R - L + 1); T[rt].Min = T[rt].Max = v; return ; } int mid = (L + R) >> 1; if(T[rt].lazy) PushDown(L, R, rt);//向下更新一级 if(r <= mid) Update(l, r, v, Lson); else if(l > mid) Update(l, r, v, Rson); else { Update(l, mid, v, Lson); Update(mid+1, r, v, Rson); } PushUp(rt); } int Query(int l, int r, int L, int R, int rt) { if(l==L && r== R) { printf("(%d, %d)---Min: %d Max: %d Sum: %d \n", L, R, T[rt].Min, T[rt].Max, T[rt].sum); return T[rt].sum; } int mid = (L + R) >> 1; if(T[rt].lazy) PushDown(L, R, rt); if(r <= mid) return Query(l, r, Lson); else if(l > mid) return Query(l, r, Rson); return Query(l, mid, Lson) + Query(mid + 1, r, Rson); } int main() { int n, q; scanf("%d", &n); Build(1, n, 1); scanf("%d", &q); int a, b, c, d; while(q--) { scanf("%d%d%d", &a, &b, &c); if(a) { scanf("%d", &d); Update(b, c, d, 1, n, 1); } else printf("%d\n", Query(b, c, 1, n, 1)); } return 0; }
线段树区间取模（平方）区间查询
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int maxn=500005; struct segmentTree{ int sum,maxnum,col; }tree[maxn<<2]; int per[maxn],n,m; inline void PushUp(int rt){ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; tree[rt].maxnum=max(tree[rt<<1].maxnum,tree[rt<<1|1].maxnum); } void build(int l,int r,int rt){ tree[rt].col=0; if(l==r){ tree[rt].sum=per[l]; tree[rt].maxnum=per[l]; return; } int mid=(l+r)>>1; build(lson); build(rson); PushUp(rt); } void update(int x,int add,int l,int r,int rt){ if(l==r){ tree[rt].sum=add; tree[rt].maxnum=add; return; } int mid=(l+r)>>1; if(x<=mid)update(x,add,lson); else update(x,add,rson); PushUp(rt); } void update2(int x,int mod,int l,int r,int rt){ if (tree[rt].maxnum<mod) return; if(l==r){ tree[rt].sum=tree[rt].sum%mod; tree[rt].maxnum=tree[rt].maxnum%mod; return; } int mid=(l+r)>>1; if(x<=mid)update2(x,mod,lson); else update2(x,mod,rson); PushUp(rt); } int query(int a,int b,int l,int r,int rt){ if(a<=l&&b>=r){ return tree[rt].sum; } int ans=0; int mid=(l+r)>>1; if(a<=mid) ans+=query(a,b,lson); if(b>mid) ans+=query(a,b,rson); return ans; } void mod(int l,int r,int rt,int a,int b,int m) {if (tree[rt].maxnum<m) return; if (a<=l&&r<=b) {if (l==r) {tree[rt].sum%=m; tree[rt].maxnum=tree[rt].sum; return; } int mid=(l+r)>>1; if (a<=mid) mod(lson,a,b,m); if (b>mid) mod(rson,a,b,m); PushUp(rt); return; } int mid=(l+r)>>1; if (a<=mid) mod(lson,a,b,m); if (b>mid) mod(rson,a,b,m); PushUp(rt); } int main() {while (scanf("%d%d",&n,&m)!=EOF) {int i; for (i=1;i<=n;i++) scanf("%d",&per[i]); build(1,n,1); for (i=1;i<=m;i++) {int op; scanf("%d",&op); if (op==1) {int l,r; scanf("%d%d",&l,&r); printf("%d\n",query(l,r,1,n,1)); } else if (op==2) {int l,r,x; scanf("%d%d%d",&l,&r,&x); mod(1,n,1,l,r,x); } else if (op==3) {int k,x; scanf("%d%d",&k,&x); update(k,x,1,n,1); } } } return 0; }
最短路spfa
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> using namespace std; const int maxn=1000001; const int inf =0x7ffffff; struct edge { int from,to,w,next; }e[1000001]; int head[maxn]; int vis[maxn]; int dist[maxn]; int n,m,t; void add(int i,int j,int w) { e[t].from=i; e[t].to=j; e[t].w=w; e[t].next=head[i]; head[i]=t++; } void spfa(int s) { queue <int> q; for(int i=1;i<=n;i++) dist[i]=inf; memset(vis,false,sizeof(vis)); q.push(s); dist[s]=0; //cout<<q.empty()<<endl; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];i!=-1;i=e[i].next) { //cout<<i<<endl; //system("pause"); int v=e[i].to; if(dist[v]>dist[u]+e[i].w) { dist[v]=dist[u]+e[i].w; if(!vis[v]) { vis[v]=true; q.push(v); } } } } } void doing() {scanf("%d%d",&n,&m); t=0; memset(head,-1,sizeof(head)); int i; for (i=1;i<=m;i++) {int x,y; scanf("%d%d",&x,&y); add(x,y,1); add(y,x,1); } for (i=1;i<=n;i++) {int x; scanf("%d",&x); if (x!=-1) add(i,x,0); } spfa(1); if (dist[n]==inf) printf("-1\n"); else printf("%d\n",dist[n]); } int main() {int T; scanf("%d",&T); int i; for (i=1;i<=T;i++) {printf("Case #%d: ",i); doing(); } return 0; }
2-SAT稳定党员
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #define eps 1e-5 using namespace std; const int MAXN = 20020; const int MAXM = 100010; struct Edge { int to; int next; } edge[MAXM]; int head[MAXN],tot; void init() { tot = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } bool vis[MAXN]; int S[MAXN], top; bool dfs(int u) { if(vis[u^1]) return false; if(vis[u]) return true; vis[u] = true; S[top++] = u; for(int i = head[u]; i != -1; i = edge[i].next) { if(!dfs(edge[i].to)) return false; } return true; } bool Twosat(int n) { memset(vis,false,sizeof(vis)); for(int i = 0; i < n; i += 2) { if(vis[i] || vis[i^1])continue; top = 0; if(!dfs(i)) { while(top) { vis[S[--top]] = false; } if(!dfs(i^1)) return false; } } return true; } int main() { int n, m; int u, v; while(~scanf("%d%d",&n,&m)) { init(); while(m--) { scanf("%d%d",&u,&v); u--; v--; addedge(u,v^1); addedge(v,u^1); } if(Twosat(2*n)) { for(int i = 0; i < 2*n; i++) { if(vis[i]) { printf("%d\n",i+1); } } } else printf("NIE\n"); } return 0; }
欧几里得与扩展欧几里得
long long GCD(long long a,long long b) { if(b == 0) return a; else return GCD(b,a%b); } void ExGCD(long long a,long long b,long long &d,long long &x,long long &y) { if( !b ) { x = 1; y = 0; d = a; } else { ExGCD(b,a%b,d,y,x); y -= x * (a/b); } }
中国剩余定理
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> using namespace std; int main() {int p,e,i,d,n; int num=1; int tot; scanf("%d",&tot); int t; for (t=1;t<=tot;t++) {while (true) {scanf("%d%d%d%d",&p,&e,&i,&d); if (p!=-1) {n=(5544*p+14421*e+1288*i-d)%21252; if (n<=0) n+=21252; printf("Case %d: the next triple peak occurs in %d days.\n",num++,n); } else break; } } return 0; }
字典树
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> using namespace std; char c[11]; int t=0; struct ss {int num; ss *a[27]; }; ss *root,memory[1000000]; string s; ss *create() {ss *p=&memory[t++]; int i; for (i=0;i<27;i++) p->a[i]=NULL; p->num=0; return p; } void insert() {int i,len=s.size(); ss *tt,*p=root; for (i=0;i<len;i++) {int pos=s[i]-‘a‘; if (p->a[pos]==NULL) {tt=create(); p->a[pos]=tt; } p=p->a[pos]; p->num++; } } void search() {int i,len=s.size(); ss *p=root; for (i=0;i<len;i++) {char pos=s[i]-‘a‘; if (p->a[pos]==NULL) {puts("0"); return; } p=p->a[pos]; } printf("%d\n",p->num); } int main() {gets(c); root=create(); while (strlen(c)!=0) {s.assign(c); insert(); gets(c); } while (scanf("%s\n",&c)!=EOF) {s.assign(c); search(); } return 0;
匈牙利算法
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<set> #include<queue> using namespace std; int map[102][102],visit[102],match[102]; int n,m,k; struct node { int x,y; }rc[102*102]; bool DFS(int k) { for(int i=1;i<=m;i++) { if(visit[i]||!map[k][i]) continue; visit[i]=1; if(!match[i]||DFS(match[i])) { match[i]=k; return true; } } return false; } int Match() { memset(match,0,sizeof(match)); int cnt=0; for(int i=1;i<=n;i++) { memset(visit,0,sizeof(visit)); if(DFS(i)) cnt++; } return cnt; } int main() { int i,t=1; while(scanf("%d %d %d",&n,&m,&k)!=EOF) { memset(map,0,sizeof(map)); for(i=1;i<=k;i++) { scanf("%d %d",&rc[i].x,&rc[i].y); map[rc[i].x][rc[i].y]=1; } int num=0,ans; ans=Match(); for(i=1;i<=k;i++) { map[rc[i].x][rc[i].y]=0; if(ans>Match()) num++; map[rc[i].x][rc[i].y]=1; } printf("Board %d have %d important blanks for %d chessmen.\n",t++,num,ans); } return 0; }
LCA Tarjan算法
#include <iostream> #include <vector> #include <cstdio> #include <cstring> using namespace std; #define MAXN 1001 int fa[MAXN]; int ques[MAXN][MAXN]; int ind[MAXN]; bool vis[MAXN]; int cnt[MAXN]; vector<int>edge[MAXN]; int n,m; int find_father(int k) { if(fa[k] == k)return k; else return fa[k] = find_father(fa[k]); } void tarjan(int x){ for (int i=1; i<=n; i++) { if (vis[i] && ques[x][i]) cnt[find_father(i)] += ques[x][i]; } fa[x] = x; vis[x] = true; for (int i=0; i<edge[x].size(); i++) { tarjan(edge[x][i]); fa[edge[x][i]] = x; } } int main() { while (~scanf("%d", &n)) { for (int i=1; i<=n; i++) { edge[i].clear(); } memset(ques, 0, sizeof(ques)); memset(vis, false, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); memset(ind, 0, sizeof(ind)); int a, b; for (int i=0; i<n; i++) { scanf("%d:(%d)", &a, &m); for (int j=0; j<m; j++) { scanf(" %d", &b); edge[a].push_back(b); ind[b]++; } } scanf("%d", &m); for (int i=0; i<m; i++) { scanf(" (%d %d)", &a, &b); ques[a][b]++; ques[b][a]++; } for (int i=1; i<=n; i++) if (!ind[i]) { tarjan(i); break; } for (int i=1; i<=n; i++) if (cnt[i]) printf("%d:%d\n", i, cnt[i]); } return 0; }
Tarjan强连通分量
#define M 5010//题目中可能的最大点数 int STACK[M],top=0;//Tarjan算法中的栈 bool InStack[M];//检查是否在栈中 int DFN[M];//深度优先搜索访问次序 int Low[M];//能追溯到的最早的次序 int ComponentNumber=0;//有向图强连通分量个数 int Index=0;//索引号 vector<int> Edge[M];//邻接表表示 vector<int> Component[M];//获得强连通分量结果 int InComponent[M];//记录每个点在第几号强连通分量里 int ComponentDegree[M];//记录每个强连通分量的度 void Tarjan(int i) { int j; DFN[i]=Low[i]=Index++; InStack[i]=true;STACK[++top]=i; for (int e=0;e<Edge[i].size();e++) { j=Edge[i][e]; if (DFN[j]==-1) { Tarjan(j); Low[i]=min(Low[i],Low[j]); } else if (InStack[j]) Low[i]=min(Low[i],Low[j]); } if (DFN[i]==Low[i]) { ComponentNumber++; do{ j=STACK[top--]; InStack[j]=false; Component[ComponentNumber]. push_back(j); InComponent[j]=ComponentNumber; } while (j!=i); } }
KMP算法
void kmp_pre(char x[], int m){ int i,j; j = Next[0] = -1; i = 0; while(i < m){ while(-1!=j && x[i] != x[j]) j = Next[j]; Next[++i] = ++j; } } int an[MAXN]; int tot; int KMP_Count(char x[], int m, char y[], int n){ int i,j; int ans = 0; kmp_pre(x,m); i=j=0; while(i<n){ while(-1!=j && y[i]!=x[j]) j = Next[j]; i++; j++; if(j >= m){ ans ++; an[tot++] = i; j = Next[j]; } } return ans; } void kmp_pre(int x[], int m){ int i,j; j = Next[0] = -1; i = 0; while(i < m){ while(-1!=j && x[i] != x[j]) j = Next[j]; Next[++i] = ++j; } } int an[1000001]; int tot; int KMP_Count(int x[], int m, int y[], int n){ int i,j; kmp_pre(x,m); i=0; j=0; while(i<n){ while(-1!=j && y[i]!=x[j]) j = Next[j]; i++; j++; if(j >= m){ return i-m+1; } } return -1; }
扩展KMP（最长公共前缀）
void GetNext(char *T) { int a=0; int Tlen=strlen(T); next[0]=Tlen; while(a<Tlen-1&&T[a]==T[a+1]) a++; next[1]=a; a=1; for(int k=2;k<Tlen;k++) { int p=a+next[a]-1,L=next[k-a]; if((k-1)+L>=p) { int j=(p-k+1)>0? p-k+1:0; while(k+j<Tlen&&T[k+j]==T[j]) j++; next[k]=j; a=k; } else next[k]=L; } } void GetExtend(char *S,char *T) { int a=0; GetNext(T); int Slen=strlen(S); int Tlen=strlen(T); int MinLen=Slen<Tlen? Slen:Tlen; while(a<MinLen&&S[a]==T[a]) a++; extend[0]=a; a=0; for(int k=1;k<Slen;k++) { int p=a+extend[a]-1,L=next[k-a]; if((k-1)+L>=p) { int j=(p-k+1)>0? p-k+1:0; while(k+j<Slen&&j<Tlen&&S[k+j]==T[j]) j++; extend[k]=j; a=k; } else extend[k]=L; } }
数位DP
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<iostream> using namespace std; const int N = 20; typedef long long LL; int dig[N]; LL dp[N][10][2]; LL dfs(int pos,int pre,int istrue,int limit) { if (pos < 0) return istrue; if (!limit && dp[pos][pre][istrue] != -1) return dp[pos][pre][istrue]; int last = limit ? dig[pos] : 9; LL ret = 0; for (int i = 0; i <= last; i++) { ret += dfs(pos-1,i,istrue || (pre == 4 && i == 9),limit && (i == last)); } if (!limit) { dp[pos][pre][istrue] = ret; } return ret; } LL solve(LL n) { int len = 0; while (n) { dig[len++] = n % 10; n /= 10; } return dfs(len-1,0,0,1); } int main(){ memset(dp,-1,sizeof(dp)); int T; scanf("%d",&T); while (T--) { LL n; cin>>n; cout<<solve(n)<<endl; } return 0; }
组合数取模lucas
typedef long long LL; using namespace std; LL exp_mod(LL a, LL b, LL p) { LL res = 1; while(b != 0) { if(b&1) res = (res * a) % p; a = (a*a) % p; b >>= 1; } return res; } LL Comb(LL a, LL b, LL p) { if(a < b) return 0; if(a == b) return 1; if(b > a - b) b = a - b; LL ans = 1, ca = 1, cb = 1; for(LL i = 0; i < b; ++i) { ca = (ca * (a - i))%p; cb = (cb * (b - i))%p; } ans = (ca*exp_mod(cb, p - 2, p)) % p; return ans; } LL Lucas(int n, int m, int p) { LL ans = 1; while(n&&m&&ans) { ans = (ans*Comb(n%p, m%p, p)) % p; n /= p; m /= p; } return ans; } int main() { Read(); int n, m, p; while(~scanf("%d%d%d", &n, &m, &p)) { printf("%lld\n", Lucas(n, m, p)); } return 0; }
block分块
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<set> #include<map> #include<queue> using namespace std; int n,k,a[30009],m,tot,sum[600009],ans[60009],pos[30009]; struct ss { int l,r,id,flag; }; ss q[120009]; void add(int l,int r,int id,int flag) { q[++tot].l=l; q[tot].r=r; q[tot].id=id; q[tot].flag=flag; } inline bool cmp(ss a,ss b) { if (pos[a.l]==pos[b.l]) return a.r<b.r; return a.l<b.l; } int main() { while (scanf("%d",&n)!=EOF) { scanf("%d",&k); int i; for (i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); tot=0; for (i=1;i<=m;i++) { int l,r,u,v; scanf("%d%d%d%d",&l,&r,&u,&v); add(l,v,i,1); add(l,u-1,i,-1); add(r+1,v,i,-1); add(r+1,u-1,i,1); } int block=(int)sqrt(n); for (i=1;i<=n;i++) pos[i]=(int)(i-1)/block+1; sort(q+1,q+tot+1,cmp); int l=1,r=0,tot2=0; memset(sum,0,sizeof(sum)); //cout<<tot<<endl; memset(ans,0,sizeof(ans)); for (i=1;i<=tot;i++) { while (l<q[i].l) { sum[a[l]]--; tot2-=sum[k-a[l]]; l++; } while (l>q[i].l) { l--; tot2+=sum[k-a[l]]; sum[a[l]]++; } while (r<q[i].r) { r++; tot2+=sum[k-a[r]]; sum[a[r]]++; } while (r>q[i].r) { sum[a[r]]--; tot2-=sum[k-a[r]]; r--; } //cout<<tot2<<endl; ans[q[i].id]+=q[i].flag*tot2; } for (i=1;i<=m;i++) printf("%d\n",ans[i]); } return 0; }
Heap
struct node { int64 id,x; }; struct cmp { bool operator()(const node &a,const node &b) { return a.x>b.x; } }; priority_queue<node,vector<node>,cmp> q;
Set
struct Node{ int id; int num; Node(int a, int b):id(a), num(b){} bool operator == (const Node& T) const{ return id==T.id && num == T.num; } bool operator <(const Node& T) const{ if(num != T.num) return num > T.num; else return id < T.id; } }; set<Node> st; set<Node> ::iterator it; st.insert(Node(i,po[i]));
离散化
void prepare(int *x) { fo(i,1,n) data[i]=x[i]; sort(data+1,data+n+1); int m=unique(data+1,data+n+1)-data-1; fo(i,1,n) x[i]=lower_bound(data+1,data+m+1,x[i])-data; }
最小费用最大流
const int MAXN = 10000; const int MAXM = 100000; const int INF = 0x3f3f3f3f; struct Edge { int to, next, cap, flow, cost; int x, y; } edge[MAXM],HH[MAXN],MM[MAXN]; int head[MAXN],tol; int pre[MAXN],dis[MAXN]; bool vis[MAXN]; int N, M,n,m; char map[MAXN][MAXN]; void init() { N = MAXN; tol = 0; memset(head, -1, sizeof(head)); } void add(int u, int v, int cap, int cost)//左端点，右端点，容量，花费 { edge[tol]. to = v; edge[tol]. cap = cap; edge[tol]. cost = cost; edge[tol]. flow = 0; edge[tol]. next = head[u]; head[u] = tol++; edge[tol]. to = u; edge[tol]. cap = 0; edge[tol]. cost = -cost; edge[tol]. flow = 0; edge[tol]. next = head[v]; head[v] = tol++; } bool spfa(int s, int t) { queue<int>q; for(int i = 0; i < N; i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[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) { int v = edge[i]. to; if(edge[i]. cap > edge[i]. flow && dis[v] > dis[u] + edge[i]. cost ) { dis[v] = dis[u] + edge[i]. cost; pre[v] = i; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(pre[t] == -1) return false; else return true; } //返回的是最大流， cost存的是最小费用 int minCostMaxflow(int s, int t, int &cost) { int flow = 0; cost = 0; while(spfa(s,t)) { int Min = INF; for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to]) { if(Min > edge[i]. cap - edge[i]. flow) Min = edge[i]. cap - edge[i]. 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; } return flow; }
最大流EK
#define MAXN 500 #define MAXE 1100000 #define INF 0x7fffffff int net[MAXN],size;//邻接表部分 struct EDGE{ int v,next; int cap;//容量 }edge[MAXE]; void init(){ size=0; memset(net,-1,sizeof(net)); } void add(int u,int v,int cap){//加边 edge[size].v=v; edge[size].cap=cap; edge[size].next=net[u]; net[u]=size++; edge[size].v=u; edge[size].cap=0; edge[size].next=net[v]; net[v]=size++; } int pe[MAXN];//记录当前点是由那条边转移过来的 int pre[MAXN];//记录前驱 queue<int> q;//BFS所用队列 int EK(int s,int t){ int max_flow=0; while(true){//不停的找增广路 并进行增广 直到找不到增广路为止 while(!q.empty()) q.pop(); memset(pre,-1,sizeof(pre)); q.push(s); while(!q.empty()){//BFS int u=q.front(); q.pop(); for(int i=net[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(pre[v]==-1&&edge[i].cap>0){ q.push(v); pre[v]=u; pe[v]=i; } } if(pre[t]!=-1) break;//到达汇点 找到一条增广路 跳出BFS } if(pre[t]==-1) break;//没有找到增广路 跳出大循环 int aug=INF; for(int v=t;v!=s;v=pre[v]){//找到最小的容量 aug aug=min(aug,edge[pe[v]].cap); } for(int v=t;v!=s;v=pre[v]){ edge[pe[v]].cap-=aug;//减去aug edge[pe[v]^1].cap+=aug;//反向边加上aug } max_flow+=aug; } return max_flow; }
最大流ISAP
#define MAXN 500 #define MAXE 1100000 #define INF 0x7fffffff int ne,nv,s,t; int size,net[MAXN]; struct EDGE{ int v,next; int cap; int flow; }edge[MAXE]; void init(){ size=0; memset(net,-1,sizeof(net)); } void add(int u,int v,int cap){ edge[size].v = v; edge[size].cap = cap; edge[size].flow = 0; edge[size].next = net[u]; net[u] = size; ++size; edge[size].v = u; edge[size].cap = 0; edge[size].flow = 0; edge[size].next = net[v]; net[v] = size; ++size; } int gap[MAXN];//gap优化 int dist[MAXN];//距离标号 int pre[MAXN];//前驱 int curedge[MAXN];//当前弧 int ISAP(){ int cur_flow,u,temp,neck,i; int max_flow; memset(gap,0,sizeof(gap)); memset(pre,-1,sizeof(pre)); memset(dist,0,sizeof(dist)); for(i=1;i<=nv;i++) curedge[i]=net[i];//将当前弧初始话成邻接表的第一条边 gap[nv]=nv; max_flow=0; u=s; while(dist[s]<nv){ if(u==t){//找到一条增广路 cur_flow=INF; for(i=s;i!=t;i=edge[curedge[i]].v){//沿着增广路找到最小增广流量 if(cur_flow>edge[curedge[i]].cap){ neck=i; cur_flow=edge[curedge[i]].cap; } } for(i=s;i!=t;i=edge[curedge[i]].v){//更新 temp=curedge[i]; edge[temp].cap-=cur_flow; edge[temp].flow+=cur_flow; temp^=1; edge[temp].cap+=cur_flow; edge[temp].flow-=cur_flow; } max_flow+=cur_flow; u=neck;//下次直接从关键边的u开始新一轮的增广 } for(i=curedge[u];i!=-1;i=edge[i].next)//找到一条允许弧 if(edge[i].cap>0&&dist[u]==dist[edge[i].v]+1) break; if(i!=-1){//如果找到 将u指向v curedge[u]=i; pre[edge[i].v]=u; u=edge[i].v; } else{//找不到 if(0==--gap[dist[u]]) break;//出现断层 curedge[u] = net[u];//把当前弧重新设为邻接表中满足要求的第一条弧 for(temp=nv,i=net[u];i!=-1;i=edge[i].next) if(edge[i].cap > 0) temp=temp<dist[edge[i].v]?temp:dist[edge[i].v]; dist[u]=temp+1;//将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加1 ++gap[dist[u]]; if(u!=s)u=pre[u]; } } return max_flow; }
最大流MCMF
#define INF 0x7fffffff #define MAXN 1100 #define MAXE 1100000 int net[MAXN],size; struct EDGE{ int v,next; int cap; int cost; }edge[MAXE]; void init(){ size=0; memset(net,-1,sizeof(net)); } void add(int u,int v,int cap,int cost){ edge[size].v=v; edge[size].cap=cap; edge[size].cost=cost; edge[size].next=net[u]; net[u]=size++; edge[size].v=u; edge[size].cap=0; edge[size].cost=-cost; edge[size].next=net[v]; net[v]=size++; } int nv;//点数 int dist[MAXN]; int pre[MAXN]; int pe[MAXN]; bool hash[MAXN]; queue<int>q; bool spfa(int s,int t){ while(!q.empty()) q.pop(); memset(hash,0,sizeof(hash)); memset(pre,-1,sizeof(pre)); for(int i=1;i<=nv;i++) dist[i]=INF; dist[s]=0; hash[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); hash[u]=0; for(int i=net[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(edge[i].cap&&dist[v]>dist[u]+edge[i].cost){ dist[v]=dist[u]+edge[i].cost; pre[v]=u; pe[v]=i; if(hash[v]==0){ hash[v]=1; q.push(v); } } } } if(pre[t]==-1) return false; return true; } int MCMF(int s,int t,int need=0){ int max_flow=0; int min_cost=0; while(spfa(s,t)){ int aug=INF; for(int v=t;v!=s;v=pre[v]){ aug=min(aug,edge[pe[v]].cap); } max_flow+=aug; min_cost+=dist[t]*aug; for(int v=t;v!=s;v=pre[v]){ edge[pe[v]].cap-=aug; edge[pe[v]^1].cap+=aug; } } if(max_flow<need) return -1; return min_cost; }
线段树区间合并
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #define maxn 100001 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; int sum[maxn<<1],lsum[maxn<<1],rsum[maxn<<1],n,m,lazy[maxn<<1]; void PushUp(int rt,int k) { lsum[rt]=lsum[rt<<1]; rsum[rt]=rsum[rt<<1|1]; if (lsum[rt]==k-(k>>1)) lsum[rt]+=lsum[rt<<1|1]; if (rsum[rt]==k>>1) rsum[rt]+=rsum[rt<<1]; sum[rt]=max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1])); } void PushDown(int rt,int k) { if (lazy[rt]!=-1) { lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; lsum[rt<<1]=rsum[rt<<1]=sum[rt<<1]=lazy[rt]?0:(k-(k>>1)); lsum[rt<<1|1]=rsum[rt<<1|1]=sum[rt<<1|1]=lazy[rt]?0:(k>>1); lazy[rt]=-1; } } void build(int l,int r,int rt) { lsum[rt]=rsum[rt]=sum[rt]=r-l+1; lazy[rt]=-1; if (l==r) return; int mid=(l+r)>>1; build(lson); build(rson); } int query(int w,int l,int r,int rt) { if (l==r) return l; PushDown(rt,r-l+1); int mid=(l+r)>>1; if (sum[rt<<1]>=w) return query(w,lson); else if (rsum[rt<<1]+lsum[rt<<1|1]>=w) return mid-rsum[rt<<1]+1; else return query(w,rson); } void upd(int L,int R,int c,int l,int r,int rt) { //cout<<l<<" "<<r<<" "<<rt<<endl; if (L<=l&&r<=R) { lsum[rt]=rsum[rt]=sum[rt]=c?0:r-l+1; lazy[rt]=c; return; } PushDown(rt,r-l+1); int mid=(l+r)>>1; if (L<=mid) upd(L,R,c,lson); if (R>mid) upd(L,R,c,rson); PushUp(rt,r-l+1); } int main() { while (~scanf("%d%d",&n,&m)) { build(1,n,1); while (m--) { int id; scanf("%d",&id); if (id==1) { int a; scanf("%d",&a); if (sum[1]<a) puts("0"); else { int pos=query(a,1,n,1); printf("%d\n",pos); upd(pos,pos+a-1,1,1,n,1); } } else { int a,b; scanf("%d%d",&a,&b); upd(a,a+b-1,0,1,n,1); } } } return 0; }
求反素数
void dfs(int kk,long long num,long long sum,long long limit) { if (sum>k) return ; if (sum==k) ans=min(ans,num); for (int i=1;i<=limit;i++) { if (ans/p[kk] <num || sum*(i+1)>k) break; num*=p[kk]; if (k%(sum*(i+1))==0) dfs(kk+1,num,sum*(i+1),i); } }
计算行列式
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 #define LL long long 7 using namespace std; 8 LL n,m,A[105][105],p[10000],pos,d[105],r[105],len,B[105][105]; 9 bool vd[10005]={0}; 10 void prime() 11 { 12 pos=0; 13 for(int i=2;i<10005;i++) 14 { 15 if(!vd[i]) 16 { 17 if(i>1000) p[pos++]=i; 18 for(int j=(i<<1);j<10005;j+=i) 19 vd[i]=1; 20 } 21 } 22 } 23 void deal(LL k) 24 { 25 len=0; 26 for(int i=0;i<pos&&k!=1;i++) 27 { 28 if(k%p[i]==0) 29 { 30 while(k%p[i]==0) 31 { 32 d[len++]=p[i]; 33 k/=p[i]; 34 } 35 } 36 } 37 } 38 LL exp(LL a,LL b,LL mod) 39 { 40 LL ans=1; 41 while(b) 42 { 43 if(b&1)ans=ans*a%mod; 44 a=a*a%mod;b>>=1; 45 } 46 return ans; 47 } 48 void ex_gcd(LL a,LL b,LL &dd,LL &x,LL &y) 49 { 50 if(b==0) 51 x=1,y=0,dd=a; 52 else 53 { 54 ex_gcd(b,a%b,dd,y,x); 55 y-=x*(a/b); 56 } 57 } 58 LL gauss(LL mod) 59 { 60 bool flag=0; 61 LL ans=1; 62 for(int i=0;i<n;i++) 63 for(int j=0;j<n;j++) 64 B[i][j]=A[i][j]; 65 for(int k=0;k<n-1;k++) 66 { 67 LL max_b=B[k][k];int bin=k; 68 for(int i=k+1;i<n;i++) 69 if(B[i][k]>max_b) 70 max_b=B[i][k],bin=i; 71 if(bin!=k) 72 { 73 for(int i=k;i<n;i++) 74 swap(B[bin][i],B[k][i]); 75 flag^=1; 76 } 77 if(B[k][k]<0)B[k][k]+=mod; 78 LL Ni,y,dd; 79 ex_gcd(B[k][k],mod,dd,Ni,y); 80 Ni%=mod; 81 if(Ni<0)Ni+=mod; 82 for(int j=k+1;j<n;j++) 83 { 84 B[k][j]=B[k][j]*Ni%mod; 85 if(B[k][j]<0)B[k][j]+=mod; 86 for(int i=k+1;i<n;i++) 87 { 88 B[i][j]=(B[i][j]-(B[k][j]*B[i][k])%mod)%mod; 89 if(B[i][j]<0)B[i][j]+=mod; 90 } 91 } 92 ans*=B[k][k]; 93 ans%=mod; 94 if(ans<0)ans+=mod; 95 } 96 ans*=B[n-1][n-1]; 97 ans%=mod; 98 if(flag)ans=-ans; 99 if(ans<0)ans+=mod; 100 return ans; 101 } 102 103 LL china_remain() 104 { 105 LL a,b,c,c1,c2,x,y,dd,N; 106 a=d[0],c1=r[0]; 107 if(c1==0)c1=d[0]; 108 for(int i=1;i<len;i++) 109 { 110 b=d[i],c2=r[i]; 111 ex_gcd(a,b,dd,x,y); 112 c=c2-c1; 113 LL b1=b/dd; 114 x=((c/dd*x)%b1+b1)%b1; 115 c1=a*x+c1; 116 a=a*b1; 117 } 118 return c1%m; 119 } 120 int main() 121 { 122 prime(); 123 while(cin>>n>>m) 124 { 125 deal(m); 126 for(int i=0;i<n;i++) 127 for(int j=0;j<n;j++) 128 cin>>A[i][j]; 129 if(m==1) 130 { 131 cout<<0<<endl; 132 continue; 133 } 134 for(int i=0;i<len;i++) 135 { 136 r[i]=gauss(d[i]); 137 } 138 cout<<china_remain()<<endl; 139 } 140 return 0;
读入挂
inline bool scan(int &num){ bool isN = false; char in = getchar(); if (in == EOF) return false; while (in != ‘-‘ && ((in < ‘0‘) || in > ‘9‘)) in = getchar(); if (in == ‘-‘) isN = true, num = 0; else num = in - ‘0‘; while (in = getchar(), in >= ‘0‘ && in <= ‘9‘) num *= 10, num += in - ‘0‘; if (isN) num = -num; return true; } inline bool scan_lf(double &num){ double Dec = 0.1; bool isN = false, isD = false; char in = getchar(); if (in == EOF) return false; while (in != ‘-‘ && in != ‘.‘ && (in < ‘0‘ || in > ‘9‘)) in = getchar(); if (in == ‘-‘) isN = true, num = 0; else if (in == ‘.‘) isD = true, num = 0; else num = in - ‘0‘; if (!isD) while (in = getchar(), in >= ‘0‘ && in <= ‘9‘) num *= 10, num += in - ‘0‘; if (in != ‘.‘){ if (isN) num = -num; return true;} else{ while (in = getchar(), in >= ‘0‘ && in <= ‘9‘) num += Dec * (in - ‘0‘), Dec *= 0.1;} if (isN) num = -num; return true; }
ACM常用模板整理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。