中国地质大学复试ACM测试题库

1、PAGE- 42 -地大ACM题库2017.5目录TOC o 1-5 h z u HYPERLINK l _Toc388040768 1.环境设置 PAGEREF _Toc388040768 h - 2 - HYPERLINK l _Toc388040769 1.1.头文件 PAGEREF _Toc388040769 h - 2 - HYPERLINK l _Toc388040770 1.2.Ubuntu相关设置 PAGEREF _Toc388040770 h - 2 - HYPERLINK l _Toc388040771 2.基本算法 PAGEREF _Toc388040771 h - 2

2、- HYPERLINK l _Toc388040772 2.1.三分（极小值） PAGEREF _Toc388040772 h - 2 - HYPERLINK l _Toc388040773 3.数论 PAGEREF _Toc388040773 h - 2 - HYPERLINK l _Toc388040774 3.1.判断质数 PAGEREF _Toc388040774 h - 2 - HYPERLINK l _Toc388040775 3.2.筛法打质数表 PAGEREF _Toc388040775 h - 2 - HYPERLINK l _Toc388040776 3.3.分解质因数（打

3、一个表） PAGEREF _Toc388040776 h - 2 - HYPERLINK l _Toc388040777 3.4.快速幂取模 PAGEREF _Toc388040777 h - 2 - HYPERLINK l _Toc388040778 3.5.费马小定理求逆元（M必须是质数） PAGEREF _Toc388040778 h - 2 - HYPERLINK l _Toc388040779 3.6.lucas定理 PAGEREF _Toc388040779 h - 2 - HYPERLINK l _Toc388040780 3.7.扩展欧几里得 PAGEREF _Toc38804

4、0780 h - 2 - HYPERLINK l _Toc388040781 3.8.扩展欧几里得求逆元（只需gcd(a,M)=1） PAGEREF _Toc388040781 h - 2 - HYPERLINK l _Toc388040782 3.9.欧拉函数 PAGEREF _Toc388040782 h - 2 - HYPERLINK l _Toc388040783 3.10.欧拉函数打表 PAGEREF _Toc388040783 h - 2 - HYPERLINK l _Toc388040784 3.11.中国剩余定理不互质 PAGEREF _Toc388040784 h - 2 -

5、 HYPERLINK l _Toc388040785 3.12.高斯消元 PAGEREF _Toc388040785 h - 2 - HYPERLINK l _Toc388040786 3.13.二进制下的高斯消元 PAGEREF _Toc388040786 h - 2 - HYPERLINK l _Toc388040787 3.14.组合数打表 PAGEREF _Toc388040787 h - 2 - HYPERLINK l _Toc388040788 4.图论 PAGEREF _Toc388040788 h - 2 - HYPERLINK l _Toc388040789 4.1.邻接表

6、PAGEREF _Toc388040789 h - 2 - HYPERLINK l _Toc388040790 4.2.spfa PAGEREF _Toc388040790 h - 2 - HYPERLINK l _Toc388040791 4.3.dijkstra+heap PAGEREF _Toc388040791 h - 2 - HYPERLINK l _Toc388040792 4.4.kruskal PAGEREF _Toc388040792 h - 2 - HYPERLINK l _Toc388040793 4.5.prim+heap PAGEREF _Toc388040793 h

7、 - 2 - HYPERLINK l _Toc388040794 4.6.最小树形图朱刘算法 PAGEREF _Toc388040794 h - 2 - HYPERLINK l _Toc388040795 4.7.树的直径 PAGEREF _Toc388040795 h - 2 - HYPERLINK l _Toc388040796 4.8.LCA的tarjan离线算法 PAGEREF _Toc388040796 h - 2 - HYPERLINK l _Toc388040797 4.9.二分图最大匹配匈牙利算法 PAGEREF _Toc388040797 h - 2 - HYPERLINK

8、l _Toc388040798 5.数据结构 PAGEREF _Toc388040798 h - 2 - HYPERLINK l _Toc388040799 5.1.离散化 PAGEREF _Toc388040799 h - 2 - HYPERLINK l _Toc388040800 5.2.一维树状数组 PAGEREF _Toc388040800 h - 2 - HYPERLINK l _Toc388040801 5.3.RMQ PAGEREF _Toc388040801 h - 2 - HYPERLINK l _Toc388040802 5.4.线段树 PAGEREF _Toc388040

9、802 h - 2 - HYPERLINK l _Toc388040803 5.5.对一棵树进行线段树操作 PAGEREF _Toc388040803 h - 2 - HYPERLINK l _Toc388040804 5.6.KMP PAGEREF _Toc388040804 h - 2 - HYPERLINK l _Toc388040805 6.数学 PAGEREF _Toc388040805 h - 2 - HYPERLINK l _Toc388040806 6.1.De Bruijn序列（格雷码） PAGEREF _Toc388040806 h - 2 - HYPERLINK l _T

10、oc388040807 6.2.矩阵类 PAGEREF _Toc388040807 h - 2 - HYPERLINK l _Toc388040808 6.3.巴什博弈（取石子游戏，1堆，一次取m个） PAGEREF _Toc388040808 h - 2 - HYPERLINK l _Toc388040809 6.4.尼姆博弈（取m堆石子游戏，一次只能在一堆里取） PAGEREF _Toc388040809 h - 2 - HYPERLINK l _Toc388040810 6.5.威佐夫博弈（取(2堆)石子游戏，一次取一堆的任意或两堆的相同） PAGEREF _Toc388040810 h

11、 - 2 - HYPERLINK l _Toc388040811 7.动态规划 PAGEREF _Toc388040811 h - 2 - HYPERLINK l _Toc388040812 7.1.二维最大子段和 PAGEREF _Toc388040812 h - 2 - HYPERLINK l _Toc388040813 8.计算几何 PAGEREF _Toc388040813 h - 2 - HYPERLINK l _Toc388040814 9.其他 PAGEREF _Toc388040814 h - 2 - HYPERLINK l _Toc388040815 9.1.旋转的坐标变换

12、PAGEREF _Toc388040815 h - 2 - HYPERLINK l _Toc388040816 9.2.蔡勒公式 PAGEREF _Toc388040816 h - 2 - HYPERLINK l _Toc388040817 9.3.归并排序求逆序数 PAGEREF _Toc388040817 h - 2 - HYPERLINK l _Toc388040818 9.4.卡特兰数 PAGEREF _Toc388040818 h - 2 - HYPERLINK l _Toc388040819 10.黑科技 PAGEREF _Toc388040819 h - 2 - HYPERLIN

13、K l _Toc388040820 10.1.输入输出优化 PAGEREF _Toc388040820 h - 2 - HYPERLINK l _Toc388040821 10.2.强制O2优化 PAGEREF _Toc388040821 h - 2 - HYPERLINK l _Toc388040822 10.3.其他 PAGEREF _Toc388040822 h - 2 -环境设置头文件1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include10 #

14、include11 #include12 #include13 #include14 #include15 #include16 #include17 #include18 #include19 #include20 #include21 #define debug puts()22 #define pi (acos(-1.0)23 #define eps (1e-8)24 #define inf (1eps) 5 6 mid1=(left+right)/2; 7 mid2=(mid1+right)/2; 8 if (f(mid1)f(mid2) 9 right=mid2;10 else11

15、left=mid1;12 数论判断质数1 intisprime(long long n) 2 3 if (n=1) 4 return0; 5 long long x=sqrt(n); 6 for (int i=2; i=x; i+) 7 if (n%i=0) 8 return0; 9 return1;10 筛法打质数表1 const int NP=1000005; 2 int ispriNP=,primeNP=,pcnt=0; 3 voidgetprime() 4 5 ispri0=ispri1=1; 6 for (long long i=2;iNP;i+) 7 if (isprii=0) 8

16、 9 prime+pcnt=i;10 for (long long j=i*i;jNP;j+=i)11 isprij=1;12 13 分解质因数（打一个表）1 int a1000000= ,pcnt=0; 2 voidpdec(int n) 3 4 int x=sqrt(n); 5 for (int i=1; primei=x; i+) 6 if (n%primei=0) 7 8 a+pcnt=primei; 9 n/=primei;10 i-;11 12 if (n!=1)13 a+pcnt=n;14 快速幂取模1 const long longM=1000000007; 2 long lo

17、ngquickpow(long longa,long longb) 3 4 if(b=1,a= (a*a) %M) 8 if(b&1) 9 ret= (ret*a) %M;10 returnret;11 费马小定理求逆元（M必须是质数）1 long longinv(long longa) 2 3 returnquickpow(a,M-2); 4 lucas定理1 const intfcnt=M; 2 long longfacfcnt; 3 voidgetfac() 4 5 fac0=fac1=1; 6 for(inti=2;ifcnt;i+) 7 faci=faci-1*i%M; 8 9 lo

18、ng longC(long longn,long longm,long longM)10 11 if(nm)12 return0;13 returnfacn*inv(facm,M)%M*inv(facn-m,M)%M;14 15 long longlucas(long longn,long longm,long longM)16 17 if(m=0)18 return1;19 return(lucas(n/M,m/M,M)*C(n%M,m%M,M)%M;20 扩展欧几里得1 long longexgcd(long longa,long longb,long long&x,long long&y

19、) 2 3 if(b=0) 4 5 x=1; 6 y=0; 7 returna; 8 9 long longans=exgcd(b,a%b,x,y);10 long longtemp=x;11 x=y;12 y=temp-(a/b)*y;13 returnans;14 扩展欧几里得求逆元（只需gcd(a,M)=1）1 long longinv(long longa,long longM) 2 3 long longx,y; 4 long longt=exgcd(a,M,x,y); 5 if(t!=1) 6 return-1; 7 return(x%M+M)%M; 8 欧拉函数1 long lo

20、ngphi(long longn) 2 3 long longans=n; 4 long longx=sqrt(n); 5 for(long longi=2;i1)15 ans=ans/n*(n-1);16 returnans;17 欧拉函数打表1 const intMAXN=10005; 2 long longphiMAXN; 3 voidgetphi() 4 5 for(inti=1;iMAXN;i+) 6 phii=i; 7 for(inti=2;iMAXN;i+) 8 if(phii=i) 9 for(intj=i;jt) 5 6 intflag=1; 7 long longn1,a1

21、; 8 if(t) 9 scanf(%lld%lld,&n1,&a1),t-;10 while(t-)11 12 long longn2,a2,k1,k2;13 scanf(%lld%lld,&n2,&a2);14 if(flag=0)15 continue;16 long longd=exgcd(n1,n2,k1,k2);17 if(a2-a1)%d!=0)18 flag=0;19 if(flag)20 21 k1=(k1*(a2-a1)/d%(n2/d)+n2/d)%(n2/d);22 long longa=n1*k1+a1;23 long longn=n1/d*n2;24 n1=n;25

22、 a1=a;26 27 28 if(flag)29 returna1;30 else31 return-1;32 33 高斯消元1 const int MAXN=105; 2 double aMAXNMAXN,bMAXN; /要注意-0.000的情况 +eps 3 intgauss_elimination(int n,double aMAXN,double b) 4 5 int i,j,k,row; 6 double mx,t; 7 for(k=1; k=n; k+) 8 9 for(mx=0,i=k; ifabs(mx)11 mx=arow=ik;12 if(fabs(mx)eps)13 r

23、eturn0;14 if(row!=k)15 16 for(j=k; j=n; j+)17 swap(akj,arowj);18 swap(bk,brow);19 20 for(j=k+1; j=n; j+)21 for(akj/=mx,i=k+1; i=n; i+)22 aij-=aik*akj;23 for(bk/=mx,i=k+1; i=1; i-)27 for(j=i+1; j=n; j+)28 bi-=aij*bj;29 return1;30 二进制下的高斯消元1 const intMAXN=105; 2 intaMAXNMAXN,bMAXN; 3 voidgauss(intn,in

24、taMAXN,intb) 4 5 for(inti=1;i=n;i+) 6 7 intk; 8 for(intj=i;j=n;j+) 9 if(aji)10 11 k=j;12 break;13 14 for(intj=1;j=n;j+)15 swap(aij,akj);16 swap(bi,bk);17 for(intj=1;j=n;j+)18 if(i!=j&aji)19 20 for(k=1;k=n;k+)21 ajk=aik;22 bj=bi;23 24 25 组合数打表1 const intCN=20; 2 long longcCNCN= ; 3 voidcinit() 4 5 fo

25、r(inti=0;iCN;i+) 6 7 ci0=cii=1; 8 for(intj=1;ji;j+) 9 cij=ci-1j+ci-1j-1;10 11 图论邻接表1 typedefint mytype; 2 const int NV=105; 3 const int NE=10005*2; 4 int heNV,ecnt; 5 struct edge 6 7 int v,next; 8 mytype l; 9 ENE;10 voidadde(int u,int v,mytype l)11 12 E+ecnt.v=v;13 Eecnt.l=l;14 Eecnt.next=heu;15 heu

26、=ecnt;16 17 初始化：18 ecnt=0;19 memset(he,-1,sizeof(he);20 调用：21 for (int i=heu; i!=-1; i=Ei.next)spfa1 typedefintmytype; 2 const intNV=105; 3 const intNE=10005*2; 4 mytype disNV; 5 intpreNV,visNV,vcntNV,heNV,ecnt; 6 structedge 7 8 intv,next; 9 mytype l;10 ENE;11 voidadde(intu,intv,mytype l)12 13 E+ecn

27、t.v=v;14 Eecnt.l=l;15 Eecnt.next=heu;16 heu=ecnt;17 18 voidinit(intn,intm,ints)19 20 ecnt=0;21 memset(pre,0,sizeof(pre);22 memset(vis,0,sizeof(vis);23 memset(vcnt,0,sizeof(vcnt);24 memset(he,-1,sizeof(he);25 for(inti=0;i=n;i+)26 disi=inf;27 diss=0;28 for(inti=1;i=m;i+)29 30 intu,v;31 mytype l;32 sca

28、nf(%d%d%d,&u,&v,&l);33 adde(u,v,l);34 adde(v,u,l);35 36 37 voidspfa(intn,intm,ints)38 39 queueq;40 viss=1;41 q.push(s);42 while(!q.empty()43 44 intu=q.front();45 q.pop();46 visu=0;47 for(inti=heu;i!=-1;i=Ei.next)48 if(disu+Ei.ldisEi.v)49 50 disEi.v=disu+Ei.l;51 preEi.v=u;52 if(!visEi.v)53 54 visEi.v

29、=1;55 q.push(Ei.v);56 vcntEi.v+;57 58 59 60 dijkstra+heap1 typedefintmytype; 2 const intNV=105; 3 const intNE=10005*2; 4 mytype disNV; 5 intpreNV,visNV,heNV,ecnt; 6 structedge 7 8 intv,next; 9 mytype l;10 ENE;11 voidadde(intu,intv,mytype l)12 13 E+ecnt.v=v;14 Eecnt.l=l;15 Eecnt.next=heu;16 heu=ecnt;

30、17 18 voidinit(intn,intm,ints)19 20 ecnt=0;21 memset(pre,0,sizeof(pre);22 memset(vis,0,sizeof(vis);23 memset(he,-1,sizeof(he);24 for(inti=0;i=n;i+)25 disi=inf;26 diss=0;27 for(inti=1;i=m;i+)28 29 intu,v;30 mytype l;31 scanf(%d%d%d,&u,&v,&l);32 adde(u,v,l);33 adde(v,u,l);34 35 36 structpoint37 38 int

31、u;39 mytype l;40 point(inta,mytype b):u(a),l(b) 41 booloperatorp.l;44 45 ;46 voiddijkstra_heap(intn,intm,ints)47 48 priority_queueq;49 q.push(point(s,0);50 while(!q.empty()51 52 point p=q.top();53 q.pop();54 intu=p.u;55 if(visu)56 continue;57 visu=1;58 for(inti=heu;i!=-1;i=Ei.next)59 if(!visEi.v&p.l

32、+Ei.ldisEi.v)60 61 disEi.v=disu+Ei.l;62 preEi.v=u;63 q.push(point(Ei.v,disEi.v);64 65 66 kruskal1 typedefintmytype; 2 const intNV=105; 3 const intNE=10005; 4 structedge 5 6 intu,v; 7 mytype l; 8 booloperator(constedge e)const 9 10 returnlrkb)36 fb=a;37 else38 39 if(rka=rkb)40 rkb+;41 fa=b;42 43 44 v

33、oidinit(intn,intm)45 46 memset(rk,0,sizeof(rk);47 for(inti=1;i=n;i+)48 fi=i;49 for(inti=1;i=m;i+)50 scanf(%d%d%d,&Ei.u,&Ei.v,&Ei.l);51 52 mytypekruskal(intn,intm)53 54 sort(e+1,e+m+1);55 mytype ans=0;56 for(inti=1;i=m;i+)57 if(finds(Ei.u)!=finds(Ei.v)58 59 uni(Ei.u,Ei.v);60 ans+=Ei.l;61 62 returnans

34、;63 64 booljudge(intn)65 66 intflag=0;67 for(inti=1;i=n;i+)68 if(finds(i)=i)69 flag+;70 returnflag=1;71 prim+heap1 typedefintmytype; 2 const intNV=105; 3 const intNE=10005*2; 4 mytype disNV; 5 intpreNV,visNV,heNV,ecnt,pcnt; 6 structedge 7 8 intv,next; 9 mytype l;10 ENE;11 voidadde(intu,intv,mytype l

35、)12 13 E+ecnt.v=v;14 Eecnt.l=l;15 Eecnt.next=heu;16 heu=ecnt;17 18 voidinit(intn,intm,ints)19 20 ecnt=0;21 memset(pre,0,sizeof(pre);22 memset(vis,0,sizeof(vis);23 memset(he,-1,sizeof(he);24 for(inti=0;i=n;i+)25 disi=inf;26 diss=0;27 for(inti=1;i=m;i+)28 29 intu,v;30 mytype l;31 scanf(%d%d%d,&u,&v,&l

36、);32 adde(u,v,l);33 adde(v,u,l);34 35 36 structpoint37 38 intu;39 mytype l;40 point(inta,mytype b):u(a),l(b) 41 booloperatorp.l;44 45 ;46 mytypeprim_heap(intn,intm,ints)47 48 priority_queueq;49 q.push(point(s,0);50 mytype ans=0;51 pcnt=0;52 while(!q.empty()53 54 point p=q.top();55 q.pop();56 intu=p.

37、u;57 if(visu)58 continue;59 visu=1;60 ans+=p.l;/=disx61 pcnt+;62 for(inti=heu;i!=-1;i=Ei.next)63 if(!visEi.v&Ei.ldisEi.v)64 65 disEi.v=Ei.l;66 preEi.v=u;67 q.push(point(Ei.v,disEi.v);68 69 70 returnans;71 72 booljudge(intn)73 74 returnpcnt=n;75 最小树形图朱刘算法1 typedefint mytype; 2 const int NV=1005; 3 co

38、nst int NE=NV*NV; 4 struct edge 5 6 int u,v; 7 mytype l; 8 ENE; 9 int preNV,IDNV,visNV;10 mytype InNV;11 voidinit(int m)12 13 for(int i=1; i=m; i+)14 scanf(%d%d%d,&Ei.u,&Ei.v,&Ei.l);15 16 mytype Directed_MST(int root,int NV,int NE)17 18 / memset(pre,0,sizeof(pre);19 mytype ret = 0;20 while(1)21 22 /

39、1.找最小入边23 for(int i=1; i=NV; i+)24 Ini = inf;25 for(int i=1; i=NE; i+)26 27 int u = Ei.u;28 int v = Ei.v;29 if(Ei.l Inv & u != v)30 31 prev = u;32 Inv = Ei.l;33 34 35 for(int i=1; i=NV; i+)36 37 if(i = root)38 continue;39 if(fabs(Ini-inf)eps)40 return -1;/除了跟以外有点没有入边,则根无法到达它41 42 /2.找环43 int cntnode

40、 = 0;44 memset(ID,-1,sizeof(ID);45 memset(vis,-1,sizeof(vis);46 Inroot = 0;47 for(int i=1; i=NV; i+) /标记每个环48 49 ret += Ini;50 int v = i;51 while(visv != i & IDv = -1& v != root)52 53 visv = i;54 v = prev;55 56 if(v != root & IDv = -1)57 58 IDv = +cntnode;59 for(int u = prev ; u != v ; u = preu)60 I

41、Du = cntnode;61 62 63 if(cntnode = 0)64 break;/无环65 for(int i=1; i=NV; i+)66 if(IDi = -1)67 IDi = +cntnode;68 /3.缩点,重新标记69 for(int i=1; ieps;87 树的直径1 typedefintmytype; 2 const intNV=40005; 3 const intNE=2*NV; 4 intvisNV,heNV,ecnt; 5 structedge 6 7 intv,next; 8 mytype l; 9 ENE;10 voidadde(intu,intv,m

42、ytype l)11 12 E+ecnt.v=v;13 Eecnt.l=l;14 Eecnt.next=heu;15 heu=ecnt;16 17 voidinit(intn,intm)18 19 ecnt=0;20 memset(he,-1,sizeof(he);21 for(inti=1;iL)35 36 U=u;37 L=l;38 39 for(inti=heu;i!=-1;i=Ei.next)40 if(Ei.v!=uu)41 dfs(Ei.v,u,l+Ei.l);42 43 mytypesolve()44 45 dfs(1,0,0);46 dfs(U,0,0);47 returnL;

43、48 LCA的tarjan离线算法1 typedefintmytype; 2 const intNV=40005; 3 const intNE=NV; 4 const intNQ=10005; 5 mytype disNV,ansNV; 6 intvisNV,heNV,hqNV,ecnt,qcnt; 7 structedge 8 9 intv,next;10 mytype l;11 E2*NE;12 structquer13 14 intv,next,i;15 q2*NQ;16 voidadde(intu,intv,mytype l)17 18 E+ecnt.v=v;19 Eecnt.l=l;

44、20 Eecnt.next=heu;21 heu=ecnt;22 23 voidaddq(intu,intv,inti)24 25 q+qcnt.v=v;26 qqcnt.i=i;27 qqcnt.next=hqu;28 hqu=qcnt;29 30 intfaNV,rkNV;31 voidinit(intn,intm)32 33 ecnt=0;34 qcnt=0;35 memset(vis,0,sizeof(vis);36 memset(rk,0,sizeof(rk);37 memset(he,-1,sizeof(he);38 memset(hq,-1,sizeof(hq);39 for(i

45、nti=1;i=m;i+)40 41 intu,v;42 mytype l;43 scanf(%d%d%d,&u,&v,&l);44 adde(u,v,l);45 adde(v,u,l);46 47 48 intfinds(intx)49 50 intk,j,r;51 r=x;52 while(r!=far)53 r=far;54 k=x;55 while(k!=r)56 57 j=fak;58 fak=r;59 k=j;60 61 returnr;62 63 voidtarjan(intu,mytype d)64 65 disu=d;66 fau=u;67 visu=1;68 for(int

46、i=heu;i!=-1;i=Ei.next)69 if(!visEi.v)70 tarjan(Ei.v,d+Ei.l),faEi.v=u;71 for(inti=hqu;i!=-1;i=qi.next)72 if(visqi.v)73 ansqi.i=disu+disqi.v-2*disfinds(qi.v);74 75 voidsolve(intn,intm)76 77 init(n,m);78 intk;79 scanf(%d,&k);80 for(inti=1;i=k;i+)81 82 intu,v;83 scanf(%d%d,&u,&v);84 addq(u,v,i);85 addq(

47、v,u,i);86 87 tarjan(1,0);88 for(inti=1;i=k;i+)89 printf(%dn,ansi);90 二分图最大匹配 匈牙利算法1 const intNV=505; 2 const intNE=10005; 3 intheNV,ecnt,preNV,visNV; 4 structedge 5 6 intv,next; 7 ENE; 8 voidadde(intu,intv) 9 10 E+ecnt.v=v;11 Eecnt.next=heu;12 heu=ecnt;13 14 intdfs(intu)15 16 for(inti=heu;i!=-1;i=Ei

48、.next)17 18 intv=Ei.v;19 if(!visv)20 21 visv=1;22 if(prev=0|dfs(prev)23 24 prev=u;25 return1;26 27 28 29 return0;30 31 voidinit(intm)32 33 ecnt=0;34 memset(he,-1,sizeof(he);35 memset(pre,0,sizeof(pre);36 while(m-)37 38 intu,v;39 scanf(%d%d,&u,&v);40 adde(u,v);41 42 43 inthungary(intn)44 45 intans=0;

49、46 for(inti=1;i=n;i+)47 48 memset(vis,0,sizeof(vis);49 ans+=dfs(i);50 51 returnans;52 数据结构离散化1 voiddiscrete(intdata,intn,intdis) 2 3 intsubn+1; 4 memcpy(sub,data,sizeof(sub); 5 sort(sub+1,sub+n+1); 6 intm=unique(sub+1,sub+n+1)-sub-1; 7 for(inti=1;i=n;i+) 8 disi=lower_bound(sub+1,sub+m+1,datai)-sub;

50、9 一维树状数组1 intn; 2 inlineintlowbit(intt) 3 4 returnt&(-t); 5 6 voidupdate(intc,intx,intv) 7 8 while(x0)18 19 ans+=cx;20 x-=lowbit(x);21 22 returnans;23 RMQ1 const intNV=50005; 2 const intNVB=20; 3 intmxNVBNV,mnNVBNV,aNV; 4 voidrmqinit(intdata,intn) 5 6 intk=log2(n); 7 for(inti=1;i=n;i+) 8 mx0i=mn0i=d

51、atai; 9 for(inti=1;i=k;i+)10 for(intj=1;j+(1i)-1=n;j+)11 12 mxij=max(mxi-1j,mxi-1j+(11);13 mnij=min(mni-1j,mni-1j+(11);14 15 16 intrmq(intl,intr,intflag)17 18 intk=log2(r-l+1);19 if(flag)20 returnmax(mxkl,mxkr-(1k)+1);21 else22 returnmin(mnkl,mnkr-(1k)+1);23 线段树1 #define lson l,m,rt1 2 #define rson

52、m+1,r,rt1|1 3 const intNV=100005; 4 intaddNV*3,sumNV*3; 5 voidPushUp(intrt) 6 7 sumrt=sumrt1+sumrt1|1; 8 9 voidPushDown(intrt,intm)10 11 if(addrt)12 13 addrt1 +=addrt;14 addrt1|1 +=addrt;15 sumrt1);16 sumrt1);17 addrt =0;18 19 20 voidbuild(intl,intr,intrt=1)21 22 addrt =0;23 if(l=r)24 25 sumrt=0;26

53、return;27 28 intm= (l+r) 1;29 build(lson);30 build(rson);31 PushUp(rt);32 33 voidupdate(intL,intR,intc,intl,intr,intrt=1)34 35 if(L=l&r1;43 if(L=m)update(L,R,c,lson);44 if(mR)update(L,R,c,rson);45 PushUp(rt);46 47 intquery(intL,intR,intl,intr,intrt=1)48 49 if(L=l&r1;55 intret=0;56 if(L=m)ret+=query(

54、L,R,lson);57 if(mR)ret+=query(L,R,rson);58 returnret;59 对一棵树进行线段树操作1 const intNV=10005; 2 const intNE=NV; 3 intheNV,ecnt; 4 structedge 5 6 intv,next; 7 ENE; 8 voidadde(intu,intv) 9 10 ecnt+;11 Eecnt.v=v;12 Eecnt.next=heu;13 heu=ecnt;14 15 intlNV,rNV,p;16 voiddfs(intu)17 18 p+;19 lu=p;20 for(inti=heu

55、;i!=-1;i=Ei.next)21 dfs(Ei.v);22 ru=p;23 24 voidinit()25 26 ecnt=p=0;27 memset(he,-1,sizeof(he);28 KMP1 const intLEN=1000005; 2 intnextLEN; 3 charsLEN; 4 charsubLEN; 5 voidgetnext(charsub,intnext,intlen2) 6 7 inti=0,j=-1; 8 next0=-1; 9 while(ilen2)10 11 if(j=-1|subi=subj)12 13 i+;14 j+;15 nexti=j;16

56、 17 else18 j=nextj;19 20 21 intkmp(chars,charsub,intlen1,intlen2,intnext)22 23 inti,j;24 i=0;25 j=0;26 while(ilen1&j=len2)37 returni-len2;38 else39 return-1;40 数学De Bruijn序列（格雷码）1 /k为元素值范围，n为串长度 2 voiddb(int n,int k,vector&v,int a,int t=1,int p=1) 3 4 if (tn) 5 6 if (n%p=0) 7 for (int i=1; i=p; i+)

57、8 v.push_back(ai); 9 10 else11 12 at=at-p;13 db(n,k,v,a,t+1,p);14 for (int i=at-p+1; ik; i+)15 16 at=i;17 db(n,k,v,a,t+1,t);18 19 20 21 vectorde_bruijn(int n,int k)22 23 vector v;24 int an*k;25 memset(a,0,sizeof(a);26 db(n,k,v,a);27 return v;28 矩阵类1 typedeflong longmytype; 2 const intSZ=105; 3 const

58、 long longM=1000000007; 4 long longquickpow(long longa,long longb) 5 6 if(b=1,a= (a*a) %M)10 if(b&1)11 ret= (ret*a) %M;12 returnret;13 14 long longinv(long longa)15 16 returnquickpow(a,M-2);17 18 structmat19 20 intn,m;21 / mytype (*a)SZ=new mytypeSZSZ;22 mytype aSZSZ;23 voidinit()24 25 memset(a,0,si

59、zeof(a);26 27 mat(intn=SZ,intm=SZ):n(n),m(m) 28 / mat()29 / 30 / delete a;31 / 32 matunit()33 34 matt(n,n);35 t.init();36 for(inti=0;in;i+)37 t.aii=1;38 returnt;39 40 matoperator+(constmat&b)41 42 matt(n,m);43 for(inti=0;in;i+)44 for(intj=0;jm;j+)45 t.aij=(aij+b.aij+M)%M;46 returnt;47 48 matoperator

60、-(constmat&b)49 50 matt(n,m);51 for(inti=0;in;i+)52 for(intj=0;jm;j+)53 t.aij=(aij-b.aij+M)%M;54 returnt;55 56 matoperator*(constmat&b)57 58 matt(n,m);59 for(inti=0;in;i+)60 for(intj=0;jm;j+)61 62 t.aij=0;63 for(intk=0;km;k+)64 t.aij=(t.aij+(aik*b.akj)%M)%M;65 66 returnt;67 68 matoperator*(constmyty