C常用算法模板

本文格式为Word版，下载可任意编辑——C常用算法模板KMP算法

#include#include#defineN20000

charst1[N],st2[N],pre[N];intans,len1,len2;voidkmp1(){

inti,j=0;

for(i=2;i#include#defineN1000

usingnamespacestd;

intn,i,len,ok,tot,trie[N][30];intflag[N];chars[100];

voidaddtrie(intlen){

intx,i,ch;x=1;

for(i=1;i#include#defineM1000000#defineN100000#definemo10000

intn,m,i,key[N],ha,w,len,ss,ans;chars[10000];

intlast[N],other[M],next[M];intjianyan(intx,inty){

for(inti=0;i#include#includeusingnamespacestd;#defineN251000inttest,n,tot,ans,i;intjs[N],flag[N],g[N];inttrie[N][26];chars[1001000];voidaddtrie(intlen){

inti,ch,x=1;

for(i=1;iq;q.push(1);while(q.size()){

x=q.front();q.pop();for(i=0;i#include#defineN10000chars[N];

intheight[N],r[N],wa[N],wb[N],wc[N],wv[N],rank[N],sa[N];inttest,i,ans,len;

intcmp(int*y,inta,intb,intl)

{returny[a]==y[b]}voidda(int*r,int*sa,intn,intm){

inti,j,p,*x=wa,*y=wb,*t;for(i=0;i=0;i--)sa[--wc[x[i]]]=i;for(j=1,p=1;p=j)y[p++]=sa[i]-j;for(i=0;ifor(i=n-1;i>=0;i--)sa[--wc[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i

for(i=1;i#include#includeusingnamespacestd;#defineoo1000000#defineN10000#defineM100000

structedge{intn,o,v;}e[M];intn,m,w,S,T,ans,x,y,z,i;intd[N],last[N];;

intmin(intx,inty){returnxq;q.push(S);

memset(d,0,sizeof(d));d[S]=1;while(q.size()){

x=q.front();q.pop();

for(w1=last[x];w1;w1=e[w1].n){

y=e[w1].o;

if(d[y]==0q.push(y);if(y==T)return1;

}}}

return0;}

intdinic(intx,intlimit){

intv,w1,y,flow;if(x==T)returnlimit;

for(v=0,w1=last[x];w1

if(d[y]==d[x]+1

v+=flow;e[w1].v-=flow;e[w1^1].v+=flow;}}

if(v==0)d[x]=0;returnv;}

intmain(){

freopen(\freopen(\scanf(\w=1;S=1;T=n;ans=0;

for(i=1;i#include#includeusingnamespacestd;#defineoo100000000#defineN10000

#defineM100000

structedge{intn,o,v,f;}e[M];intn,m,i,x,y,z,money,ans,w,S,T;

intdist[N],last[N],minf[N],flag[N],path[N];inlineintmin(intx,inty){returnxq;

memset(dist,42,sizeof(dist));dist[qi]=0;memset(flag,0,sizeof(flag));flag[qi]=1;minf[qi]=oo;q.push(qi);while(q.size()){

x=q.front();q.pop();flag[x]=0;for(w1=last[x];w1;w1=e[w1].n)if(e[w1].v>0){

y=e[w1].o;

if(dist[x]+e[w1].f10000000)return0;return1;}

voidcalcfei(){

intx,y;

ans+=dist[T]*minf[T];for(x=T;x!=S;){

y=path[x];

e[y].v-=minf[T];e[y^1].v+=minf[T];

x=e[y^1].o;}}

intmain(){

freopen(\freopen(\scanf(\w=1;ans=0;

for(i=1;i#include

#definemin(x,y)(x)intmain(){

freopen(\freopen(\scanf(\while(test--){

scanf(\

for(i=1;i>1;boolyou=kboolxia=kif(a[i][j]){

f[i][j][k]=f[i][j-1][k^x^y];

if(you!=xia)f[i][j][k]+=f[i][j-1][k];}else{

if(you+xia==0)f[i][j][k]=f[i][j-1][k];elsef[i][j][k]=0;}}}

printf(\}

return0;}

dancinglink

#include#include

#defineoo1000000000#definemaxn1000#definemaxs500000structnode{intx,y;};nodea[maxn];

intL[maxs],R[maxs],U[maxs],D[maxs],lie[maxs],hang[maxs];inthead[maxn],sum[maxn],b[maxn];inti,j,n,ok,g,h,m,now,k;chars[100];

voidremove(intx){

inti,j;

R[L[x]]=R[x];L[R[x]]=L[x];for(i=U[x];i!=x;i=U[i])for(j=L[i];j!=i;j=L[j])

D[U[j]]=D[j],U[D[j]]=U[j],sum[lie[j]]--;}

voidresume(intx){

inti,j;

R[L[x]]=x;L[R[x]]=x;for(i=D[x];i!=x;i=D[i])for(j=R[i];j!=i;j=R[j])

D[U[j]]=j,U[D[j]]=j,sum[lie[j]]++;}

voiddlx(){

inti,j,k,x,min1,y;

if(!L[0]){ok=1;return;}

min1=oo;for(i=L[0];i;i=L[i])if(sum[i]#definestart100intq[10];intf[10][200];inti,test,j,k,x,y;intfind(intx){

intl,sum,ans,i,j;if(x#include#include#includeusingnamespacestd;boolflag[1001];

intw,pre[1000000],other[1000000],ju[1000000],last[1001];intx,y,z,test,t,i,j,n,l,r,mid,m;voidadd(intx,inty,intz){

w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;}

booldfs(intx){

intw1,point;

if(x==n)returntrue;flag[x]=true;w1=last[x];while(w1!=0){

point=other[w1];

if(!flag[point]w1=pre[w1];}

returnfalse;}

intmain(){

scanf(\for(t=1;t>1;

memset(flag,false,sizeof(flag));if(dfs(1))l=mid;elser=mid;}

printf(\printf(\}}

1){a[root].size--;a[root].cnt--;return;}splay(a[root].l,findpre(x));a[a[root].l].r=a[root].r;root=a[root].l;update(root);}

voidfindrank(intx){

splay(root,x);

printf(\}

voidfindkth(intx){

intsum,y=root;for(;;){

sum=a[a[y].l].size+a[y].cnt;

if(x>a[a[y].l].sizeif(x#defineN100000

intn,i,b[N],tot,root,test,x,y,L[N],R[N];chars[10];

structarr{intx,size,rev,sum,l,r;}a[N];voidupdate(intx){

a[x].size=a[a[x].l].size+a[a[x].r].size+1;

a[x].sum=a[a[x].l].sum+a[a[x].r].sum+a[x].x;}

voidswap(intx=y;y=z;}voidrever(intx){

a[x].rev^=1;

swap(a[x].l,a[x].r);}

voidzig(inta[x].l=a[y].r;a[y].r=x;update(x);update(y);x=y;}

voidzag(inta[x].r=a[y].l;a[y].l=x;update(x);update(y);x=y;}

voidspread(intx)

{

if(a[x].rev){a[x].rev=0;rever(a[x].l);rever(a[x].r);}}

voidsplay(intL[0]=R[0]=0;for(;;){

spread(x);spread(a[x].l);spread(a[x].r);temp=a[a[x].l].size+1;if(y==temp)break;if(ytemp){

y-=temp;temp1=a[a[a[x].r].l].size+1;if(y>temp1)zag(x),y-=temp1;L[++L[0]]=x;x=a[x].r;}}

L[++L[0]]=a[x].l;R[++R[0]]=a[x].r;

for(i=L[0]-1;i;i--)a[L[i]].r=L[i+1],update(L[i]);for(i=R[0]-1;i;i--)a[R[i]].l=R[i+1],update(R[i]);a[x].l=L[1];a[x].r=R[1];update(x);}

voidreverse(intx,inty){

splay(root,y+1);splay(a[root].l,x-1);rever(a[a[root].l].r);}

voidquery(intx,inty){

splay(root,y+1);splay(a[root].l,x-1);printf(\}

intbuild(intl,intr){

intmid,now;if(l>r)return0;

mid=(l+r)/2;tot++;now=tot;a[now].x=b[mid];a[now].l=build(l,mid-1);

a[now].r=build(mid+1,r);update(now);returnnow;}

intmain(){

freopen(\freopen(\scanf(\

for(i=2;iintn,m,mo,x,y;intmain(){

freopen(\freopen(\scanf(\x=1;y=n;while(m){

if(my=y*y%mo;m>>=1;}

printf(\return0;}

矩阵乘法

#include#includeintn,mo;

inta[3][3],b[3][3],f[3],ff[3];voidmul(intf[],inta[3][3]){

inti,j;

memset(ff,0,sizeof(ff));for(i=1;i>=1;}printf(\}

高斯消元

#include#include#defineN1000

#defineeps1e-8intn,i,j,ok;

doublea[N][N],b[N];

voidswap(doublex=y;y=z;}voidgauss(){

inti,j,k,u;doubletemp;

for(i=1,j=1;ieps)break;if(k>n){i--;continue;}

for(u=j;ueps){

temp=a[i][j]/a[k][j];

for(u=j;ueps){ok=0;return;}for(i=n;i;i--)

if(fabs(a[i][i])>eps){

b[i]=a[i][n+1];

for(j=i+1;j

__int64xx,yy,M,N,d,temp,a,b,n,L,x,y;__int64gcd(__int64a,__int64b){returnb?gcd(b,a%b):a;}

voidegcd(__int64a,__int64b,__int64y=0;return;}egcd(b,a%b,x