《[理学]acm模板_zhou.doc》由会员分享，可在线阅读，更多相关《[理学]acm模板_zhou.doc（61页珍藏版）》请在三一文库上搜索。
1、1. 高精度 22. kmp 算法 63. 后缀数组 84. 最大流 105. 最小费用最大流 146. RMQ167. 抽屉原理 188. km算法189. 匈牙利算法 （二分图最大匹配） 2110. 0/1 背包 2311. 多重背包 （二进制优化） 24 12. 单调队列优化多重背包 2513. 快速读入 2614. 差分约束 2715. 并查集 2916. 简单素数判定【1】 2917. 简单素数判定【2】 3018. 二超式素数判定 3019. dancing links 精确覆盖 3020. dancing links 重复覆盖 3421. 三维树状数组 3922. map函数 4
2、123. 二超式链表 4124. 字典树 4125. 矩阵链表 4326. 最小公倍数（辗转相除法） 4527. froyd算法 4528. dijkstra算法 4529. Spfa 算法 4630. prim 算法 4731. kruskal 算法 4832. 最优比例生成树 4833. pick 定理 5134. 拓扑排序 5135. 混合欧拉回路和通路 5236. Digit size 5637. 矩阵连乘 59+/高精度模版start/大整数加减乘除模版#include #includetypedef _int64 lld;const int And_Bit =1000000000;
3、 /进位数const int Num_Bit = 9; /数组一位表示整形数的位数const int Num_Len = 2001; /整形数的位数const int BigNum_Len = Num_Len/Num_Bit + 10; /数组的位数const char OutStr = %,0,0+Num_Bit,d,0; /标准化输出字符串void toBigInt(const char *s,int *a)/将输入的字符串转为整形数组的大整数int len=0,ret,ten;memset(a,0,sizeof(int)*BigNum_Len);for(int i=(int)strlen
4、(s)-1;i=0;i-=Num_Bit)ret = 0; ten = 1;for(int j=0;j=0;j+)ret += (si-j-0)*ten;ten *= 10;a+len=ret;a0=len;void outBigInt(const int *a)/输出大整数int tmp = a0;printf(%d,atmp);for(int i=tmp-1;i0;i-)printf(OutStr,ai);/printf(n);void leftShiftBigInt(int *a,int b)/大整数左移移位运算int l=a0;for(int i=l+1;i1;i-)ai = ai-1
5、;a1 = b;if(al+1!=0) a0+;int cmpBigInt(const int *a,const int *b)/大整数比较：若ab返回，若a=b返回，否则返回-1int la=a0,lb=b0;if(lalb) return 1;if(la=1;i-)if(aibi) return 1;if(aila&ilb) break;ci += ai + bi;if(ci=And_Bit)ci+1+;ci-=And_Bit;while(ci=0&i1) i-;c0=i;void subBigInt(const int *a,const int *b,int *c)/大整数减法：c=a-
6、bmemset(c,0,sizeof(int)*BigNum_Len);/初始化全为零int i=0,la=a0,lb=b0;for(i=1;i+)if(ila&ilb) break;ci += ai-bi;if(ci1) i-;c0=i;void mulBigInt(const int *a,const int *b,int *c)/大整数乘法：c=a*bmemset(c,0,sizeof(int)*BigNum_Len);int i,j,k;lld t;for(i=1;i=a0;i+)for(j=1;j= And_Bit)ci+j += t/And_Bit;t %= And_Bit;ci+
7、j-1 = t;k=i+j+1;while(ck=0&k1) k-;c0=k;void mulIntBigInt(const int *A,const int b,int *C)/大整数与Int数乘法：C=A*b;memset(C,0,sizeof(int)*BigNum_Len);int i=0;lld t;for(i=1;i=And_Bit)Ci+1+=t/And_Bit;t%=And_Bit;Ci = t;while(Ci=And_Bit)Ci+1+=Ci/And_Bit;Ci=Ci%And_Bit;i+;while(Ci=0&i1) i-;C0=i;void diviIntBigInt
8、(const int *a,int b,int *c,int d)/大数除小数 快多了int i,len;memset(c,0,sizeof(int)*BigNum_Len);len=a0;d=0;for(i=len;i=1;i-) d=d*10+ai; ci=d/b; d%=b; while(len1&clen=0) len-;c0=len;void divBigInt(const int *a,const int *b,int *c,int *d)/大整数除法：c=a/b,d=a%b/大数除大数int *td = new intBigNum_Len,*tb = new intBigNum_
9、Len;memset(c,0,sizeof(int)*BigNum_Len);memset(d,0,sizeof(int)*BigNum_Len);if(b0=1&b1=0) return ;int t_max,t_mid,t_min,la=a0,lb=b0,lc=la,ld=0;/二分辅助变量double b_min=blb,b_max=b_min+1,d_max=0,d_min=0;if(lb1)b_min = b_min*And_Bit + blb-1;b_max = b_min + 1;for(int i=la;i=1;i-)leftShiftBigInt(d,ai);if(cmpBi
10、gInt(b,d)=1) continue;ld = d0; d_min = dld;while(d_min=0)t_min = t_mid+1;continue;break;memcpy(d,td,sizeof(int)*BigNum_Len);ci = t_mid;delete td;delete tb;while(clc=0&lc1) lc-;c0=lc;int main()char str1Num_Len,str2Num_Len;int aBigNum_Len,bBigNum_Len,cBigNum_Len,dBigNum_Len;while(scanf(%s %s,str1,str2
11、)!=EOF)toBigInt(str1,a);toBigInt(str2,b);/divBigInt(a,b,c,d);diviIntBigInt(a,b,c,d)outBigInt(c);printf( );outBigInt(d);printf(n);+KMP算法 #include #includeint next10005;char p10005,str1000005;void get_next() next0=-1; int i=0,j=-1,len=strlen(p); while(i=len) if(j=-1 | pi=pj) +i; +j; nexti=j; else j=ne
12、xtj;int kmp() int i=0,j=0,num=0; int lenmain=strlen(str),lenp=strlen(p); while(i=lenp)/这里的j表示【1】紧接着要进行比较的字母【2】目前的匹配的长度 j=nextj; num+; return num;int main() int t; scanf(%d,&t); while(t-) scanf(%s%s,p,str); get_next();/短一点的 printf(%dn,kmp() ); return 0;/*3BAPCBAPCAZAAZAZAZA*/+/后缀数组#include#include#in
13、clude#includeusing namespace std;#define maxn 200010#define maxm 1000010int wamaxn,wbmaxn,wvmaxn,wzmaxm;/wz的大小和da（）传参的m，及n均有关，取最大值； int rmaxn,samaxn;int cmp(int *r,int a,int b,int j) return ra=rb&ra+j=rb+j;void da(int *r,int *sa,int n,int m) int i,j,*x=wa,*y=wb,*t,p; for(i=0;im;i+)wzi=0; for(i=0;in;
14、i+)wzxi=ri+; for(i=1;i=0;i-)sa-wzxi=i; for(j=1,p=1;pn;j*=2,m=p) for(p=0,i=n-j;in;i+)yp+=i; for(i=0;i=j) yp+=sai-j; for(i=0;in;i+)wvi=xyi; for(i=0;im;i+)wzi=0; for(i=0;in;i+)wzwvi+; for(i=1;i=0;i-)sa-wzwvi=yi; t=x;x=y;y=t;xsa0=0;p=1; for(i=1;in;i+) xsai=cmp(y,sai-1,sai,j)?p-1:p+; int rankmaxn,heightm
15、axn;void calh(int *r,int *sa,int n) int i,j,k=0; for(i=1;i=n;i+) ranksai=i; for(i=0;in;heightranki+=k) for(k?k-:0,j=saranki-1;ri+k=rj+k;k+); int bestmaxn20;void Init_RMQ(int n) int i,j; int a,b; int sl=(int)(log(double)n)/log(2.0); for(i=1;i=n;i+)besti0=i; for(i=1;i=sl;i+) for(j=1;j=n+1-(1(i);j+) a=
16、bestji-1; b=bestj+(1heightb) bestji=b; else bestji=a; int askRMQ(int x,int y) int tl=(int)(log(double)(y-x+1)/log(2.0); int a,b; a=bestxtl; b=besty-(1heightb) return b; else return a;int lcp(int x,int y) x=rankx,y=ranky; int t; if(xy) t=x; x=y; y=t; return heightaskRMQ(x+1,y);int main()rn=0; da(r,sa
17、,n+1,200); calh(r,sa,n); Init_RMQ(n);+/最大流 邻接表#include#includeconst int MAX=100005;const int INF=1000000000;structint v,c,next;edge1000000;int E,headMAX;int gapMAX,curMAX;int preMAX,disMAX;void add_edge(int s,int t,int c,int cc)/*加边的时候同时加两条，一条正的，一条反的，一般情况下反的容量是0 */edgeE.v=t; edgeE.c=c;edgeE.next=hea
18、ds;heads=E+;edgeE.v=s; edgeE.c=cc;edgeE.next=headt;headt=E+;int min(int a,int b)return (a=-1|ba)?b:a;int SAP(int s,int t,int n)memset(gap,0,sizeof(gap);gap0=n;memset(dis,0,sizeof(dis);int i;for(i=0;in;i+)curi=headi;int u=pres=s,max_flow=0,aug=-1,v;while(diss0&disu=disv+1)aug=min(aug,edgei.c);prev=u;
19、curu=i;u=v;if(u=t)for(u=preu;v!=s;v=u,u=preu)edgecuru.c-=aug;edgecuru1.c+=aug;max_flow+=aug;aug=-1;goto loop;int _min=n;for(i=headu;i!=-1;i=edgei.next)v=edgei.v;if(edgei.c0&disv_min)curu=i;_min=disv;if(-gapdisu)=0)break;gapdisu=_min+1+;u=preu;return max_flow;int main()memset(head,-1,sizeof(head);E=0
20、;/建图 如何建图SAP(0,9999,10000);return 0;+/矩阵#include#includeconst int INF=1000000000;const int MAX=1000;int mapMAXMAX;int disMAX,curMAX;int preMAX,gapMAX;int min(int a,int b)return (a=-1|ba)?b:a;int SAP(int s,int t,int n)memset(dis,0,sizeof(int)*n);memset(cur,0,sizeof(int)*n);memset(gap,0,sizeof(int)*n)
21、;int u=pres=s,max_flow=0,aug=-1,v;gap0=n;while(dissn)loop:for(v=curu;v0&disu=disv+1)aug=min(aug,mapuv);prev=u;curu=v;u=v;if(u=t)for(u=preu;v!=s;v=u,u=preu)mapuv-=aug;mapvu+=aug;max_flow+=aug;aug=-1;goto loop;int min_dis=n-1,v;for(v=0;v0&disvmin_dis)curu=v;min_dis=disv;if(-gapdisu)=0)break;gapdisu=mi
22、n_dis+1+;u=preu;return max_flow;int main()memset(map,0,sizeof(map);/建图 SAP(0,999,1000);return 0;+/*最小费用最大流：复杂度 （点在1000内是没有问题的）在保证流量最大的前提下,所需的费用最小题意：有很多的city 【点】和他们之间的单向路【具有价值】 找到一种可能使得他们组成多个欧拉回路使得他们所用到的价值最小 （最少有两个城市组成一个环）过程：先拆分点将每个点都拆分成两个点一个接受入度一个具有出度，应用欧拉回路的思想（入度等于出度时构成一个欧拉回路）【用最大流保证保证入度与出度】*/#incl
23、ude#includeconst int MAX=500; /顶点的个数const int INF=1000000000;const int MOD=1000000; /不要管它！struct EDGEint cap,cost,v,next;edgeMOD;int headMAX,E,qMOD;bool usedMAX;int preMAX,curMAX,disMAX;void add_edge(int s,int t,int cap,int cost)edgeE.cap=cap;/容量 edgeE.cost=cost;/费用 edgeE.next=heads;edgeE.v=t;heads=
24、E+;int min(int a,int b)return (a=-1|ba)?b:a;int SPFA(int s,int t,int n)int f=-1,r=0;int i,v;qr=s;for(i=0;i=MOD)f-=MOD;s=qf;useds=false;for(i=heads;i!=-1;i=edgei.next)v=edgei.v;if(edgei.cap0&diss+edgei.cost=MOD)r-=MOD;/为了防止数据太多溢出 qr=v;return dist;int MinCost(int s,int t,int n)int ans=0;int u,v,cap;in
25、t cost;while(1)cost=SPFA(s,t,n);if(cost=INF)break;u=v=t;cap=-1;for(u=preu;v!=s;v=u,u=preu)cap=min(cap,edgecurv.cap); ans+=cost*cap;u=v=t;for(u=preu;v!=s;v=u,u=preu)edgecurv.cap-=cap;edgecurv1.cap+=cap;return ans;int main()int T,i,j,n,m,s,t,a,b,c,ans;scanf(%d,&T);while(T-)scanf(%d%d,&n,&m);s=0;t=2*n+
26、1;E=0;memset(head,-1,sizeof(int)*(n*2+10);/费用流特别注意赋初值for(i=1;i=n;i+)/因为head是以首顶点拿来用的 add_edge(s,i,1,0);/cap costadd_edge(i,s,0,0);add_edge(i+n,t,1,0);add_edge(t,i+n,0,0);/注意往返路都要建立for(i=1;i=m;i+)scanf(%d%d%d,&a,&b,&c);add_edge(a,b+n,1,c);add_edge(b+n,a,0,-c);/注意这里的花费正反路的取值ans=MinCost(s,t,t+1);printf
27、(%dn,ans);return 0;+/RMQ模板#include#includeusing namespace std;int A100;int M100100;int n;int LOG100;void init() LOG0=-1; LOG1=0; int i,j; for(i=2;i=n;i+) if(i-1)&(i)=0) LOGi=LOGi-1+1; else LOGi=LOGi-1;/这里的LOG用于当在查询的时候得到长的二进制 printf(LOG%d=%dn,i,LOGi); for(i=0;in;i+) Mi0=i;/赋初值当长度为零时最小值就是它本身 for(j=1;(1j)=n;j+)/控制长(总长度)下面右移以为进行二分 for(i=0;i+(1j)-1n;i+)/控制那个位置开始的 if(AMij-1AMi+(11)j-1)/注意这里（起始位置）不需要加一 Mij=Mij-1; else Mij=Mi+(11)j-1; int RMQ(int i,int j) int k=LOGj-i+1;/这段区间的最大二分值 if(AMikAMj-(1k)+1k)/将起始位置改变