ACM比赛模板.docx

目录1.最小生成树22.最短路算法73.素数打表114.最大匹配125.线段树（敌兵布阵）146线段树（逆序树）167.树形dp188.树状数组（段跟新）209.Kmp模板2210.线段树（点跟新）2611.强连通2812.最小割3113.单源最短路（spfa）3414.三分查找3615.字典树（统计难题）3816.最大流入门题 12734017.状态压缩4318.匈牙利（HDU 2063）（最大匹配）4519.凸包 （HDU1348）4720.树状数组 (HDU1166)5021.强连通5222.前向星5523.矩阵5824.并查集6025. SORT6126. STL6327. LCA (HDU 2874)6728. 01背包7029. 状态压缩代码：7230. 快速幂7431.矩阵快速幂7532.GCD & LCM7733.ACM小技巧：7834. /* 大数（高精度）求幂 */8035. /* 大数除法与求余 */8236. /* 大数阶乘 */8437. /* 大数乘法 */8538. /* 大数累加 */861. 最小生成树要连通n个城市需要n1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。prim算法（矩阵形式）：#define inf 0x3f3f3f3fint prim(int n,int sta)/n表示有n个顶点，sta表从sta这个顶点出发生成最小生成树 int markM,disM; int i,sum = 0; /sum是总的最小生成树边权值 for (i = 0;i n;i +) /初始化disi 表从顶点sta到点i的权值 disi = matstai; marki = 0; marksta = 1;/sta 这个顶点加入最小生成树中 for (i = 1;i n;i +)/循环n-1次，每次找出一条最小权值的边 n个点的图 /只有n-1条边 int min = inf; /inf 表无穷大 for (j = 0;j n;j +)/找出当前未在最小生成树中边权最小的顶点 if (!markj & disj min) min = disj,flag = j; markflag = 1;/把该顶点加入最小生成树中 sum += disflag; /sum加上其边权值 for (j = 0;j matflagj) disj = matflagj; return sum; /返回边权总和prim算法（边表形式）：struct Edge/frm为起点,to为终点，w为边权，nxt指向下一个顶点 / int frm; int to,w,nxt;edgeM;int visM,headM,disM;void addedge (int cu,int cv,int cw)/生成边的函数 /edgee.frm = cu; edgee.to = cv; edgee.w = cw; edgee.nxt = headcu; headcu = e +; /edgee.frm = cv; edgee.to = cu; edgee.w = cw; edgee.nxt = headcv; headcv = e +;int prim(int n,int sta) /n为顶点数量，sta为起点 int sum = 0; memset(dis,0x3f,sizeof(dis); memset(vis,0,sizeof(vis); for (i = headsta;i != -1;i = edgei.nxt)/遍历与sta点相连的所有顶点 int v = edgei.to; disv = edgei.w; vissta = 1; /加入到最小生成树中 int m = n - 1; /只生成n-1条边，所以循环n-1次 while (m -) int min = inf; for (i = 0;i n;i +)/找出当前边权最小的边 if (!visi&disi min) flag = i,min = disi; sum += disflag; visflag = 1;/加入到最小生成树中 for (i = headflag;i != -1;i = edgei.nxt) /更新与flag顶点相连的点的dis int v = edgei.to; if (edgei.w disv) disv = edgei.w; return sum; /返回边权总和int main () e = 0; /记得初始化 memset (head,-1,sizeof(head); scanf (%d %d %d,&a,&b,&w); addedge(a,b,w); . . prim(n,sta); return 0;Kruskal算法：struct Edge int v1,v2,w;edgeM,treeM; /w为v1顶点到v2顶点的边权/ *int Find (int parent,int u)/第1种写法 int tmp = u; while (parentmp != -1) tmp = parenttmp; return tmp;*/int Find (int u) /第2种写法 if (u != parentu) parentu = Find(parenu); return parentu;bool cmp (Edge a,Edge b) return a.w b.w;int Kruskal()/parent表示集合 int parentM; int i,j,sum,vf1,vf2; sort(edge,edge+E,cmp); / memset (parent,-1,sizeof(parent);/对应第1种并查集的初始化 for (i = 0;i n;i +)/对应第2种并查集的初始化 parenti = i; sum = i = j = 0; while (i E & j N - 1)/生成的边数为N-1 vf1 = Find(parent,edgei.v1); /找这两个点的祖先 vf2 = Find(parent,edgei.v2); if (vf1 != vf2) /若两个点的祖先不同，说明不在同一集合 parentvf2 = vf1;/把vf2点加到vf1点的集合中 treej+ = edgei;/把边加到tree数组中，这句题目没要求可忽略之 sum += edgei.w; /sum 加上其边权 i +; return sum;最小生成树 - Kruskal算法：运用数组存点与边的权值#include #include #include #define N 150using namespace std;int m,n,uN,vN,wN,pN,rN;int cmp(const int i,const int j) return wiwj;int find(int x) return px=x?x:px=find(px);int kruskal() int cou=0,x,y,i,ans=0; for(i=0;in;i+) pi=i; for(i=0;im;i+) ri=i; sort(r,r+m,cmp); for(i=0;im;i+) int e=ri;x=find(ue);y=find(ve); if(x!=y) ans += we;px=y;cou+; if(coun-1) ans=0; return ans; int main() int i,ans; while(scanf(%d%d,&m,&n)!=EOF&m) for(i=0;im;i+) scanf(%d%d%d,&ui,&vi,&wi); ans=kruskal(); if(ans) printf(%dn,ans); else printf(?n,ans); return 0;2.最短路算法DIJKC+代码 1. #defineinf0x3fffffff2. #defineM1053. 4. intdistM,mapMM,n;5. boolmarkM;6. 7. voidinit()8. 9. inti,j;10. for(i=1;i=n;i+)/i=j的时候也可以初始化为0，只是有时候不合适11. for(j=1;j=n;j+)12. mapij=inf;13. 14. 15. voiddijk(intu)16. 17. inti,j,mins,v;18. for(i=1;i=n;i+)19. 20. disti=mapui;21. marki=false;22. 23. marku=true;24. distu=0;/既然上面的map当i=j时不是0，就要这句25. while(1)26. 27. mins=inf;28. for(j=1;j=n;j+)29. if(!markj&distjmins)30. mins=distj,v=j;31. if(mins=inf)32. break;33. markv=true;34. for(j=1;j=n;j+)35. if(!markj&distv+mapvjdistj)36. distj=distv+mapvj;37. 38. Floyd 1. #defineinf0x3fffffff/注意，太大会溢出2. #defineM/最大点数3. intn,distMM;/n：实际点数4. 5. voidinit()/有时候需要初始化6. 7. inti,j;8. for(i=1;i=n;i+)9. for(j=i+1;j=n;j+)10. distij=distji=inf;11. 12. 13. voidfloyd()14. 15. inti,j,k;16. for(k=1;k=n;k+)17. for(i=1;i=n;i+)18. for(j=1;j=n;j+)/有的题目会溢出就要自己变通了19. if(distik+distkjdistij)20. distij=distik+distkj;21. vector后插的SPFA C+代码 1. #defineinf0x3fffffff2. #defineM105/最大点数3. structson4. intv,w;5. ;6. vectorgM;7. boolinqM;/入队列标记8. intdistM,n;/n：实际点数9. 10. voidinit()11. 12. for(inti=1;i=n;i+)13. gi.clear();14. 15. 16. voidspfa(intu)17. 18. inti,v,w;19. for(i=1;i=n;i+)20. 21. disti=inf;22. inqi=false;23. 24. queueq;25. q.push(u);26. inqu=true;27. distu=0;28. while(!q.empty()29. 30. u=q.front();31. q.pop();32. inqu=false;33. for(i=0;igu.size();i+)34. 35. v=gui.v;36. w=gui.w;37. if(distu+wdistv)38. 39. distv=distu+w;40. if(!inqv)41. 42. q.push(v);43. inqv=true;44. 45. 46. 47. 48. 模拟前插的SPFA(多数情况下比快，数据较为复杂就会看出来) C+代码 1. #defineinf0x3fffffff2. #defineM1005/最大点数3. 4. structedge5. intv,w,next;6. e10005;/估计好有多少条边7. 8. intpreM,cnt,distM,n;9. boolinqM;10. /注意初始化11. voidinit()12. 13. cnt=0;14. memset(pre,-1,sizeof(pre);15. 16. /注意双向加边17. voidaddedge(intu,intv,intw)/加边函数，慢慢模拟就会明白的18. 19. ecnt.v=v;20. ecnt.w=w;21. ecnt.next=preu;/接替已有边22. preu=cnt+;/自己前插成为u派生的第一条边23. 24. 25. voidspfa(intu)26. 27. intv,w,i;28. for(i=1;i=n;i+)/对于从1到n的编号29. disti=inf,inqi=false;30. distu=0;31. queueq;32. q.push(u);33. inqu=true;34. while(!q.empty()35. 36. u=q.front();37. q.pop();38. inqu=false;39. for(i=preu;i!=-1;i=ei.next)40. 41. w=ei.w;42. v=ei.v;43. if(distu+wdistv)44. 45. distv=distu+w;46. if(!inqv)47. 48. q.push(v);49. inqv=true;50. 51. 52. 53. 54. 3.素数打表#include#include#include#define MAXN 5000using namespace std;int primeMAXN;void print_prime()int n = (int) sqrt(MAXN); for(int i = 2; i n; i+) if( !primei ) for(int j = i*i; j MAXN; j += i) primej = 1; prime+prime0 = i; for(int i = n; i MAXN; i+) if(!primei) prime+prime0 = i;int main()FILE *out; out = fopen(out.txt,w); print_prime(); for(int i = 1; i = prime0; i+) fprintf(out, %d, primei); return 0;4.最大匹配#include#include#define MAX 505 bool usedMAX;bool matchMAXMAX; int boysMAX,girlsMAX; int k, n; void init() memset(girls, -1, sizeof(girls); memset(boys, -1, sizeof(boys); memset(match, false, sizeof(match); bool can(int t) int i; for(i = 0; i n; i +) if(!usedi & matchti) usedi = true; if(girlsi = = -1 | can(girlsi) boyst = i; girlsi = t; return true; return false; int main()int tmpa, tmpb, i, res, t;while(scanf(%d, &n) != EOF)init();for(i = 0; i n; +i)scanf(%d: (%d), &tmpa, &k);while(k- -)scanf(%d, &tmpb);matchtmpatmpb = true;res = 0; for(i = 0; i n; i+) if(boysi = -1) memset(used, false, sizeof(used); if(can(i) res +; printf(%dn, n - res/2);return 0;5.线段树（敌兵布阵）#include#includeint a50005,n;void update(int x,int c)int i; for(i=x;i0;i-=(i&-i) sum+=ai;return sum; int main()int t,i,c,b=1;int z,y;char sh15;scanf(%d,&t);while(t-)memset(a,0,sizeof(a);scanf(%d,&n);for(i=1;i=n;i+) scanf(%d,&c); update(i,c); printf(Case %d:n,b+); while(scanf(%s,sh) if(sh0=E) break; scanf(%d%d,&z,&y); if(sh0=A) update(z,y); else if(sh0=S) update(z,-y); else printf(%dn,s(y)-s(z-1); return 0;6线段树（逆序树）#include#include#include using namespace std;int a500005,n;int b500005;int d500005;void update(int x,int c)int i; for(i=x;i0;i-=(i&-i) sum+=ai;return sum; int main()int i,j;int ans;while(scanf(%d,&n)!=EOF,n)memset(d,0,sizeof(d);for(i=1;i=n;i+)scanf(%d,&bi);bi=bi+1;di=bi;sort(b+1,b+n+1);memset(a,0,sizeof(a);ans=0;for(i=1;i=n;i+)update(di,1);printf(%d ,s(di);ans+=i-s(di);printf(%d ,ans);printf(%dn,ans);return 0;7.树形dp#include#includeusing namespace std;struct Treeint father,child,brother,with_max,without_max;int MAX()return with_max=without_max?with_max:without_max;void init()father=child=brother=without_max=0;tree6001;void dfs(int id)int child;child=treeid.child;while(child)dfs(child);treeid.with_max+=treechild.without_max;treeid.without_max+=treechild.MAX();child=treechild.brother;int main()int n,i;while(scanf(%d,&n)!=EOF)for(i=1;i=n;i+)scanf(%d,&treei.with_max);treei.init();int a,b;while(scanf(%d%d,&a,&b),a|b)treea.father=b;treea.brother=treeb.child;treeb.child=a;for(i=1;in;i+) if(!treei.father) dfs(i); printf(%dn,treei.MAX(); break; return 0;8.树状数组（段跟新）1. #include2. #include3. constintMAXN=110000;4. intn,cMAXN;5. intlowbit(intx)6. /计算2k7. 8. x=x&-x;9. returnx;10. 11. voidupdate(intnum,intval)12. /向下查询，num是要更新的子节点，val是要修改的值13. 14. while(num0)15. 16. cnum+=val;17. num-=lowbit(num);18. 19. 20. intgetSum(intnum)21. /向上统计每个区间被染色的次数22. 23. intsum=0;24. while(num=n)25. 26. sum+=cnum;27. num+=lowbit(num);28. 29. returnsum;30. 31. intmain()32. 33. inta,b;34. while(scanf(%d,&n),n)35. 36. memset(c,0,sizeof(c);37. for(inti=0;in;i+)38. 39. scanf(%d%d,&a,&b);40. /将b以下区间+141. update(b,1);42. /将a以下区间-143. update(a-1,-1);44. 45. for(intj=1;jn;j+)46. 47. printf(%d,getSum(j);48. 49. printf(%dn,getSum(n);50. 51. return0;52. 9.Kmp模板#include#include#includeusing namespace std;#define N 1000010int len,len1,nextN;int strN,str1N;void get_next()int i=0,j=-1;next0=-1;while(i=len1) return i-len1+1;return 0;int main()int i,t,flag;scanf(%d,&t);while(t-)memset(str,0,sizeof(str);memset(str1,0,sizeof(str1);memset(next,0,sizeof(next);scanf(%d%d,&len,&len1);for(i=0;ilen;i+) scanf(%d,&stri);for(i=0;ilen1;i+) scanf(%d,&str1i);get_next();flag=kmp();/printf(%dn,flag);if(flag=0) printf(-1n);else printf(%dn,flag); return 0;计算出字符串 str2 中含有的 str1 的个数#include#includeint next10005;char str110005, str21000005;int n, m, ans;void getNext(char *p, int *next) int j, k; next0 = -1; j = 0; k = -1; while(j m) if(k = -1 | pj = pk) /匹配的情况下,pj=pk j+; k+; nextj = k;/printf(%d *%d *%dn,j, k, nextj); else /pj!=pk k = nextk; int KMPMatch(char *s, char *p) int i = 0, j = 0; getNext(p, next); /*for(i = 1; i m; i+) printf(%d , nexti); i = 0; printf(n);*/ while(i n) if(j = -1 | si = pj) i+; j+; else j = nextj; /消除了指针i的回溯printf(i = %d, j = %dn, i, j), if(j = m ) ans+;/return i - m + 1; return ans;int main()int T;scanf(%d,&T);while(T-)memset(str1, 0, sizeof(str1);memset(str2, 0, sizeof(str2);memset(next, 0, sizeof(next);ans = 0;scanf(%s, str1);scanf(%s, str2);n = strlen(str2);m = strlen(str1);printf(%dn,KMPMatch(str2, str1);return 0;10.线段树（点跟新）#include#include#define N 200010struct Nodeint l,r,max;node3*N;int scoreN;int max(int a,int b)return ab?a:b;void Build(int left,int right,int index)nodeindex.l=left;nodeindex.r=right;if(left=right) nodeindex.max=scoreleft;elseint mid;mid=(left+right)/2;Build(left,mid,index*2);Build(mid+1,right,index*2+1);nodeindex.max=max(node2*index.max,node2*index+1.max);void Update(int stu,int c,int index)nodeindex.max=max(c,nodeindex.max);if(nodeindex.l=nodeindex.r)return ;if(stu=node2*index.r) Update(stu,c,index*2);else Update(stu,c,index*2+1); int query(int left,int right,int index)if(left=nodeindex.l&right=nodeindex.r) r