算法模板【最后更新2014-05】

KMP算法#include<cstdio>#include<cstring>#define N 20000char st1[N],st2[N],pre[N];int ans,len1,len2;void kmp1(){int i,j=0;for(i=2;i<=len1;i++){while(j&&st1[j+1]!=st1[i])j=pre[j];if(st1[j+1]==st1[i])j++;pre[i]=j;}}void kmp2(){int i,j=0;for(i=1;i<=len2;i++){while(j&&st1[j+1]!=st2[i])j=pre[j];if(st1[j+1]==st2[i])j++;if(j==len1)ans++,j=pre[j];}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%s",st1+1);len1=strlen(st1+1);scanf("%s",st2+1);len2=strlen(st2+1);kmp1();kmp2();printf("%d\n",ans);return 0;}trie#include<cstdio>#include<cstring>#define N 1000using namespace std;int n,i,len,ok,tot,trie[N][30];int flag[N];char s[100];void addtrie(int len){int x,i,ch;x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}if(flag[x]==1)ok=1;else ok=0;flag[x]=1;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);tot=1;for(i=1;i<=n;i++){scanf("%s",s+1);len=strlen(s+1);addtrie(len);if(ok)printf("YES\n");else printf("NO\n");}return 0;}karp-rabin#include<cstdio>#include<cstring>#define M 1000000#define N 100000#define mo 10000int n,m,i,key[N],ha,w,len,ss,ans;char s[10000];int last[N],other[M],next[M];int jianyan(int x,int y){for(int i=0;i<n;i++)if(s[x+i]!=s[y+i])return 0;return 1;}int inhash(int ha,int wz){int w1;for(w1=last[ha];w1;w1=next[w1])if(jianyan(other[w1],wz))return 0;w++;next[w]=last[ha];last[ha]=w;other[w]=wz;return 1;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);scanf("%s",s+1);len=strlen(s+1);for(i=1;i<=len;i++)key[i]=(key[i-1]*m+s[i])%mo;ss=1;for(i=1;i<=n;i++)ss=ss*m%mo;for(i=n;i<=len;i++){ha=((key[i]-key[i-n]*ss)%mo+mo)%mo;if(inhash(ha,i-n+1))ans++;}printf("%d\n",ans);return 0;}AC自动机#include<cstdio>#include<cstring>#include<queue>using namespace std;#define N 251000int test,n,tot,ans,i;int js[N],flag[N],g[N];int trie[N][26];char s[1001000];void addtrie(int len){int i,ch,x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}js[x]++;}void bfs(){int x,i,j,y;queue<int>q;q.push(1);while(q.size()){x=q.front();q.pop();for(i=0;i<26;i++){for(j=g[x];j;j=g[j])if(trie[j][i])break;if(y=trie[x][i])g[y]=j?trie[j][i]:1,q.push(y);else trie[x][i]=j?trie[j][i]:1;}}}void ac(int len){int i,ch,x=1,j;for(i=1;i<=len;i++){ch=s[i]-'a';x=trie[x][ch];for(j=x;j;j=g[j]){if(flag[j])break;ans+=js[j];flag[j]=1;}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&test);while(test--){scanf("%d",&n);tot=1;ans=0;memset(trie,0,sizeof(trie));memset(flag,0,sizeof(flag));memset(js,0,sizeof(js));memset(g,0,sizeof(g));for(i=1;i<=n;i++)scanf("%s",s+1),addtrie(strlen(s+1));bfs();scanf("%s",s+1);ac(strlen(s+1));printf("%d\n",ans);}return 0;}后缀数组#include<cstdio>#include<cstring>#define N 10000char s[N];int height[N],r[N],wa[N],wb[N],wc[N],wv[N],rank[N],sa[N];int test,i,ans,len;int cmp(int *y,int a,int b,int l){return y[a]==y[b]&&y[a+l]==y[b+l];}void da(int *r,int *sa,int n,int m){int i,j,p,*x=wa,*y=wb,*t;for(i=0;i<m;i++)wc[i]=0;for(i=0;i<n;i++)wc[x[i]=r[i]]++;for(i=1;i<m;i++)wc[i]+=wc[i-1];for(i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;for(j=1,p=1;p<n;j*=2,m=p){for(p=0,i=n-j;i<n;i++)y[p++]=i;for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;for(i=0;i<p;i++)wv[i]=x[y[i]];for(i=0;i<m;i++)wc[i]=0;for(i=0;i<p;i++)wc[wv[i]]++;for(i=1;i<m;i++)wc[i]+=wc[i-1];for(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<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}}void calheight(int *r,int *sa,int n){int i,j,k=0;for(i=1;i<=n;i++)rank[sa[i]]=i;for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); }int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&test);while(test--){scanf("%s",s);len=strlen(s);s[len]='$';for(i=0;i<=len;i++)r[i]=s[i];da(r,sa,len+1,128);calheight(r,sa,len);ans=len*(1+len)/2;for(i=2;i<=len;i++)ans-=height[i];printf("%d\n",ans);}return 0;}spfa#include<cstdio>#include<cstring>#include<queue>using namespace std;#define N 10000#define M 100000struct edge{int n,o,j;}e[M];int n,m,i,x,y,z,w,j;int dist[N],flag[N],last[N];void add(int x,int y,int z){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].j=z; }void spfa(int qi){int x,y,w1;queue<int>q;q.push(qi);memset(dist,42,sizeof(dist));dist[qi]=0;memset(flag,0,sizeof(flag));flag[qi]=1;while(q.size()){x=q.front();q.pop();flag[x]=0;for(w1=last[x];w1;w1=e[w1].n){y=e[w1].o;if(dist[x]+e[w1].j<dist[y]){dist[y]=dist[x]+e[w1].j;if(flag[y]==0)flag[y]=1,q.push(y);}}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);spfa(1);printf("%d\n",dist[n]);return 0;}folyd#include<cstdio>#include<cstring>#define max(x,y) x>y?x:y#define maxlongint 2147483647using namespace std;int f[101][101],max1,min1,i,j,k,m,n,x,y,w,ff[101];int main(){while(scanf("%d",&n)&&n!=0){memset(f,42,sizeof(f));for(i=1;i<=n;i++){f[i][i]=0;scanf("%d",&m);for(j=1;j<=m;j++)scanf("%d%d",&x,&y),f[i][x]=y;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j];for(i=1;i<=n;i++){max1=0;for(j=1;j<=n;j++)max1=max(max1,f[i][j]);ff[i]=max1;}min1=maxlongint;for(i=1;i<=n;i++)if(ff[i]<min1)min1=ff[i],w=i;if(min1>100000000)puts("disjoint");else printf("%d %d\n",w,min1);}}folyd求最小环#include<cstdio>#include<cstring>#define oo 100000000#define min(x,y) ((x)<(y)?(x):(y))#define N 110int dist[N][N],edge[N][N],pre[N][N],a[N];int n,m,i,x,y,z,ans,ge,j;void extend_floyd(){int i,j,k,s1,st;for(k=1;k<=n;k++){for(i=1;i<k;i++)for(j=i+1;j<k;j++)if((s1=dist[i][j]+edge[j][k]+edge[k][i])<ans){ans=s1;st=j;ge=0;for(;st!=i;st=pre[i][st])a[++ge]=st;a[++ge]=i;a[++ge]=k;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)if((s1=dist[i][k]+dist[k][j])<dist[i][j])dist[i][j]=s1,pre[i][j]=pre[k][j];}}int main(){freopen("delite2.in","r",stdin);freopen("delite2.out","w",stdout);scanf("%d%d",&n,&m);memset(dist,42,sizeof(dist));memset(edge,42,sizeof(edge));for(i=1;i<=n;i++)for(j=1;j<=n;j++)pre[i][j]=i;for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);dist[x][y]=dist[y][x]=edge[x][y]=edge[y][x]=min(dist[x][y],z);}ans=oo;extend_floyd();if(ans>10000000)printf("-1\n");else for(i=1;i<=ge;i++)printf("%d%c",a[i],i<ge?' ':'\n');return 0;}堆优化dijkstra#include<cstdio>#include<cstring>#include<queue>using namespace std;#define maxn 110000#define maxm 500000#define CH getchar()typedef pair<int,int>pp;int last[maxn],dist[maxn],flag[maxn];int pre[maxm],other[maxm],ju[maxm];int n,m,home,noi,cmo,i,x,y,z,ans,w;inline int min(int x,int y){return x<y?x:y;}inline void read(int &x){char ch;for(ch=CH;ch<'0'||ch>'9';ch=CH);for(x=0;ch>='0'&&ch<='9';ch=CH)x=x*10+ch-48;}inline void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;}void dijkstra(int x){pp po;int p,point,w1;memset(dist,42,sizeof(dist));dist[x]=0;memset(flag,0,sizeof(flag));priority_queue<pp,vector<pp>,greater<pp> >heap;heap.push(make_pair(0,x));while(heap.size()){po=heap.top();p=po.second;heap.pop();if(flag[p])continue;flag[p]=1;for(w1=last[p];w1;w1=pre[w1])if(dist[p]+ju[w1]<dist[point=other[w1]]){dist[point]=dist[p]+ju[w1];heap.push(make_pair(dist[point],point));}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d%d%d%d",&m,&n,&home,&noi,&cmo);for(i=1;i<=m;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);dijkstra(noi);ans=dist[home]+dist[cmo];dijkstra(cmo);ans=min(ans,dist[home]+dist[noi]);printf("%d\n",ans);return 0;}K短路#include<cstdio>#include<queue>#include<cstring>using namespace std;#define maxn 1100#define maxm 11000struct rec{int p,l,g;};rec h[1000000];int last[maxn],flag[maxn],dist[maxn];int other[maxm],ju[maxm],pre[maxm],a[maxm],b[maxm],c[maxm];int n,m,k,i,x,y,w,r,p,l,w1,point;void swap(int &x,int &y){x=x+y;y=x-y;x=x-y;}void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;} inline int heapcmp(rec a,rec b){return a.g>b.g;}void spfa(int x){int p,w1,point;queue<int>q;q.push(x);memset(dist,42,sizeof(dist));dist[x]=0;memset(flag,0,sizeof(flag));flag[x]=1;while(q.size()){p=q.front();q.pop();flag[p]=0;for(w1=last[p];w1;w1=pre[w1])if(dist[p]+ju[w1]<dist[point=other[w1]]){dist[point]=dist[p]+ju[w1];if(!flag[point])flag[point]=1,q.push(point);}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(i=1;i<=m;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);if(a[i]<b[i])swap(a[i],b[i]);add(b[i],a[i],c[i]);}spfa(1);memset(last,0,sizeof(last));w=0;for(i=1;i<=m;i++)add(a[i],b[i],c[i]);r=1;h[r].p=n;h[r].l=0;h[r].g=dist[n];while(r&&k){p=h[1].p;l=h[1].l;if(p==1)printf("%d\n",l),k--;pop_heap(h+1,h+r+1,heapcmp);r--;for(w1=last[p];w1;w1=pre[w1]){point=other[w1];r++;h[r].p=point;h[r].l=l+ju[w1];h[r].g=h[r].l+dist[point];push_heap(h+1,h+r+1,heapcmp);}}for(;k;k--)printf("-1\n");return 0;}拓扑排序#include<cstdio>#include<queue>using namespace std;#define N 100#define M 200int n,m,i,x,y,w1,w,p;int last[N],fb[N],ru[N];int next[M],other[M];queue<int>q;int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);w++;next[w]=last[x];last[x]=w;other[w]=y;ru[y]++;}for(i=1;i<=n;i++)if(ru[i]==0)q.push(i);while(q.size()){p=q.front();q.pop();printf("%d\n",p);for(w1=last[p];w1;w1=next[w1]){y=other[w1];ru[y]--;if(ru[y]==0)q.push(y);}}return 0;}匈牙利算法#include<cstdio>#include<cstring>using namespace std;#define N 1000#define M 10000struct edge{int n,o;}e[M];int n,m,i,x,y,w,ans;int last[N],flag[N],fa[N];void add(int x,int y){w++;e[w].n=last[x];last[x]=w;e[w].o=y;}int xyl(int x){int w1;for(w1=last[x];w1;w1=e[w].n){y=e[w1].o;if(flag[y]==1)continue;flag[y]=1;if(fa[y]==0||xyl(fa[y])){fa[y]=x;return 1;}}return 0;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),add(x,y);for(i=1;i<=n;i++){memset(flag,0,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",ans);return 0;}最小路径覆盖#include<cstdio>#include<cstdlib>#include<cstring>#define maxn 300using namespace std;int test,w,ans,i,n,m,x,y,last[maxn],other[maxn],pre[maxn],fa[maxn];bool flag[maxn];bool xyl(int x){int point;for(int w1=last[x];w1;w1=pre[w1]){point=other[w1];if(!flag[point]){flag[point]=true;if(!fa[point]||xyl(fa[point])){fa[point]=x;return true;}}}return false;}int main(){scanf("%d",&test);while(test--){scanf("%d",&n);scanf("%d",&m);memset(last,0,sizeof(last));w=0;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),w++,pre[w]=last[x],last[x]=w,other[w]=n+y;memset(fa,0,sizeof(fa));ans=0;for(i=1;i<=n;i++){memset(flag,false,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",n-ans);}}可重复最小路径覆盖#include<cstdio>#include<cstring>using namespace std;int n,m,i,j,k,ans,x,y,w,last[600],pre[300000],other[300000],fa[1200]; bool flag[1200],ff[600][600];bool xyl(int x){int w1,point;for(w1=last[x];w1;w1=pre[w1]){point=other[w1];if(!flag[point]){flag[point]=true;if(!fa[point]||xyl(fa[point])){fa[point]=x;return true;} }}return false;}int main(){while(scanf("%d%d",&n,&m)&&(n||m)){memset(ff,false,sizeof(ff));for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ff[x][y]=true;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(ff[i][k]&&ff[k][j])ff[i][j]=true;memset(last,0,sizeof(last));w=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(ff[i][j])w++,pre[w]=last[i],last[i]=w,other[w]=j+n;memset(fa,0,sizeof(fa));ans=0;for(i=1;i<=n;i++){memset(flag,false,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",n-ans);}}最大流#include<cstdio>#include<cstring>#include<queue>using namespace std;#define oo 1000000#define N 10000#define M 100000struct edge{int n,o,v;}e[M];int n,m,w,S,T,ans,x,y,z,i;int d[N],last[N];;int min(int x,int y){return x<y?x:y;}void addflow(int x,int y,int z){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].v=z;w++;e[w].n=last[y];last[y]=w;e[w].o=x;e[w].v=0; }int build(){int x,y,w1;queue<int>q;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]==0&&e[w1].v){d[y]=d[x]+1;q.push(y);if(y==T)return 1;}}}return 0;}int dinic(int x,int limit){int v,w1,y,flow;if(x==T)return limit;for(v=0,w1=last[x];w1&&v<limit;w1=e[w1].n){y=e[w1].o;if(d[y]==d[x]+1&&e[w1].v){flow=dinic(y,min(limit-v,e[w1].v));v+=flow;e[w1].v-=flow;e[w1^1].v+=flow;}}if(v==0)d[x]=0;return v;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;S=1;T=n;ans=0;for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),addflow(x,y,z);while(build())ans+=dinic(S,oo);printf("%d\n",ans);return 0;}费用流#include<cstdio>#include<cstring>#include<queue>using namespace std;#define oo 100000000#define N 10000#define M 100000struct edge{int n,o,v,f;}e[M];int n,m,i,x,y,z,money,ans,w,S,T;int dist[N],last[N],minf[N],flag[N],path[N];inline int min(int x,int y){return x<y?x:y;}void addfei(int x,int y,int z,int money){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].v=z;e[w].f=money; }int spfa(int qi){int x,y,w1;queue<int>q;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].f<dist[y]){dist[y]=dist[x]+e[w1].f;minf[y]=min(minf[x],e[w1].v);path[y]=w1;if(flag[y]==0)flag[y]=1,q.push(y);}}}if(dist[T]>10000000)return 0;return 1;}void calcfei(){int x,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;}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;ans=0;for(i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&z,&money);addfei(x,y,z,money);addfei(y,x,0,-money);}S=1;T=n;while(spfa(S))calcfei();printf("%d\n",ans);return 0;}上下限网络流#include<cstdio>#include<cstring>#define min(x,y) (x)<(y)?(x):(y)#define maxn 300#define maxm 100000#define oo 1000000000struct edge1{int u;int v;int high;int low;};edge1 a[maxm];int last[maxn],d[maxn],q[maxn],f[maxn];int pre[maxm],other[maxm],rong[maxm],ans[maxm];int w,n,m,start,end,i,l,r,mid,maxflow,s1,now;void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;rong[w]=z;w++;pre[w]=last[y];last[y]=w;other[w]=x;rong[w]=0; }int build(){int l,r,p,w1,point;memset(d,0,sizeof(d));d[start]=1;l=0;r=1;q[1]=start;while(l!=r){l++;p=q[l];for(w1=last[p];w1;w1=pre[w1]){point=other[w1];if(!d[point]&&rong[w1]){d[point]=d[p]+1;if(point==end)return 1;r++;q[r]=point;}}}return 0;}int find(int x,int tot){int v,w1,point,s1;if(x==end)return tot;for(v=0,w1=last[x];v<tot&&w1;w1=pre[w1]){point=other[w1];if(d[point]==d[x]+1&&rong[w1]){s1=find(point,min(tot-v,rong[w1]));v+=s1;rong[w1]-=s1;rong[w1^1]+=s1;}}if(!v)d[x]=0;return v;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].high,&a[i].low);if(a[i].low)a[i].low=a[i].high;f[a[i].u]-=a[i].low;f[a[i].v]+=a[i].low;}a[m+1].u=n;a[m+1].v=1;start=n+1;end=start+1;l=-1;r=oo;while(l+1<r){mid=(l+r)/2;a[m+1].high=mid;a[m+1].low=0;memset(last,0,sizeof(last));w=1;maxflow=0;now=0;for(i=1;i<=m+1;i++)add(a[i].u,a[i].v,a[i].high-a[i].low);for(i=1;i<=n;i++)if(f[i]<0)add(i,end,-f[i]);else add(start,i,f[i]),maxflow+=f[i];while(build())while(1){s1=find(start,oo);if(!s1)break;now+=s1;}if(now==maxflow){r=mid;for(i=1;i<=m;i++)ans[i]=a[i].high-rong[i*2];}else l=mid;}if(r==oo){puts("Impossible");return 0;}printf("%d\n",r);for(i=1;i<m;i++)printf("%d ",ans[i]);printf("%d\n",ans[m]);}tarjan#include<cstdio>#define N 10000#define M 100000#define min(x,y) ((x)<(y)?(x):(y))int n,m,i,x,y,w,top,num,ss;int last[N],other[M],next[M],dfn[N],low[N],v[N],stack[N],team[N]; void addedge(int x,int y){w++;next[w]=last[x];last[x]=w;other[w]=y;} void tarjan(int x){int w1,y;dfn[x]=low[x]=++num;stack[++top]=x;v[x]=1;for(w1=last[x],y=other[w1];w1;w1=next[w1],y=other[w1])if(dfn[y]==0)tarjan(y),low[x]=min(low[x],low[y]);else if(v[y]==1)low[x]=min(low[x],dfn[y]);if(dfn[x]==low[x]){ss++;while(stack[top]!=x)y=stack[top],team[y]=ss,v[y]=0,top--;y=stack[top];team[y]=ss;v[y]=0;top--;}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),addedge(x,y);for(i=1;i<=n;i++)if(dfn[i]==0)num=0,top=0,tarjan(i);for(i=1;i<=n;i++)printf("%d %d\n",i,team[i]);return 0;}凸包#include<cstdio>#include<algorithm>#include<cmath>using namespace std;#define sqr(x) ((x)*(x))#define N 10000#define eps 1e-8struct po{double x,y;}a[N],stack[N];int n,i,top;double ans;void swap(po x,po y){po z=x;x=y;y=z;}double chaji(double x,double y,double xx,double yy){return x*yy-xx*y;} double dis(po a,po b){return sqrt(sqr(b.x-a.x)+sqr(b.y-a.y));}double cross(po a,po b,po c){return chaji(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);}int sortcmp(po aa,po bb){double s=cross(a[1],aa,bb);if(fabs(s)>eps)return s>0;return dis(a[1],aa)>dis(a[1],bb);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);for(i=2;i<=n;i++)if(a[i].x<a[1].x||(a[i].x==a[1].x&&a[i].y<a[1].y))swap(a[1],a[i]);sort(a+2,a+n+1,sortcmp);top=1;stack[1]=a[1];for(i=2;i<=n;i++){while(top>1&&cross(stack[top-1],stack[top],a[i])<0)top--;top++;stack[top]=a[i];}for(i=2;i<=top;i++)ans+=dis(stack[i-1],stack[i]);ans+=dis(stack[top],stack[1]);printf("%.2lf\n",ans);return 0;}lca#include<cstdio>#include<queue>using namespace std;#define N 10000#define M 100000queue<int>q;int n,m,i,j,x,y,z,w,w1,test;bool fb[N];int last[N],fa[N][21],shen[N],dist[N];int other[M],next[M],ju[M];void swap(int &x,int &y){int z;z=x;x=y;y=z;}void addedge(int x,int y,int z){w++;next[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;} int lca(int x,int y){int cha,i;if(shen[x]>shen[y])swap(x,y);cha=shen[y]-shen[x];for(i=20;i>=0;i--)if(cha>=1<<i)y=fa[y][i],cha-=1<<i;if(x==y)return x;for(i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),addedge(x,y,z),addedge(y,x,z);q.push(1);fb[1]=1;while(q.size()){x=q.front();q.pop();for(w1=last[x];w1;w1=next[w1])if(!fb[y=other[w1]])fb[y]=1,fa[y][0]=x,shen[y]=shen[x]+1,dist[y]=dist[x]+ju[w1],q.push(y);}for(i=1;i<=20;i++)for(j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];scanf("%d",&test);while(test--){scanf("%d%d",&x,&y);z=lca(x,y);printf("%d\n",dist[x]+dist[y]-dist[z]*2);}return 0;}kruskal#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define M 100000#define N 10000struct arr{int x,y,z;}a[M];int n,m,i,x,y,fa1,fa2,sum;int fa[N];int sortcmp(arr a,arr b){return a.z<b.z;}int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);sort(a+1,a+m+1,sortcmp);for(i=1;i<=n;i++)fa[i]=i;for(i=1;i<=m;i++){x=a[i].x;y=a[i].y;fa1=getfa(x);fa2=getfa(y);if(fa1!=fa2)fa[fa1]=fa2,sum+=a[i].z;}printf("%d\n",sum);return 0;}线段树#include<cstdio>#define N 10000struct arr{int sum,jia;}t[N*4];int n,i,x,y,z,sum,test;int a[N];char s[10];void downdate(int w,int l,int r){int ss=t[w].jia,m=(l+r)/2;t[w].jia=0;t[w*2].jia+=ss;t[w*2].sum+=ss*(m-l+1);t[w*2+1].jia+=ss;t[w*2+1].sum+=ss*(r-m);}void update(int w){t[w].sum=t[w*2].sum+t[w*2+1].sum;} void buildtree(int w,int l,int r){int m;if(l==r){t[w].sum=a[l];return;}m=(l+r)>>1;buildtree(w*2,l,m);buildtree(w*2+1,m+1,r);update(w);}void modify(int w,int l,int r,int ll,int rr,int z){int m;if(l>=ll&&r<=rr){t[w].jia+=z;t[w].sum+=z*(r-l+1);return;}m=(l+r)>>1;downdate(w,l,r);if(ll<=m)modify(w*2,l,m,ll,rr,z);if(rr>m)modify(w*2+1,m+1,r,ll,rr,z);update(w);}void query(int w,int l,int r,int ll,int rr){int m;if(l>=ll&&r<=rr){sum+=t[w].sum;return;}downdate(w,l,r);m=(l+r)>>1;if(ll<=m)query(w*2,l,m,ll,rr);if(rr>m)query(w*2+1,m+1,r,ll,rr);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);buildtree(1,1,n);scanf("%d",&test);while(test--){scanf("%s",s);if(s[0]=='a')scanf("%d%d%d",&x,&y,&z),modify(1,1,n,x,y,z);if(s[0]=='q')scanf("%d%d",&x,&y),sum=0,query(1,1,n,x,y),printf("%d\n",sum);}return 0;}树状数组#include<cstdio>#define N 100000char s[10];int x,y,n,i,test;int a[N];void modify(int x,int y){for(;x<=n;x+=x&-x)a[x]+=y;}int query(int x){int sum=0;for(;x;x-=x&-x)sum+=a[x];return sum;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&x),modify(i,x);scanf("%d",&test);while(test--){scanf("%s%d%d",s,&x,&y);if(s[0]=='a')modify(x,y);if(s[0]=='q')printf("%d\n",query(y)-query(x-1));}return 0;}树链剖分#include<cstdio>#include<cstring>const int N=110000;const int M=220000;struct arr{int cc,sum;}t[N];struct edge{int n,o;}e[M];struct tree{int sum,ge,add;}c[N*4];int n,m,i,x,y,ans,jia,z,w;int team[N],path[N],rank[N],q[N],b[N],a[N],deep[N],fa[N],flag[N],last[N],sum[N]; char s[10];inline void addedge(int x,int y){w++;e[w].n=last[x];last[x]=w;e[w].o=y;}inline void swap(int &x,int &y){int z=x;x=y;y=z;}void update(int w,int cc){c[w+cc].sum=c[w+w+cc].sum+c[w+w+1+cc].sum;c[w+cc].ge=c[w+w+cc].ge+c[w+w+1+cc].ge;}void build(int w,int l,int r,int cc){int mid;。

算法模板网络122王硕目录1.数学1.1 矩阵 (2)1.2 一次方程组的解 (3)1.3 矩阵的逆 (4)1.4 最大公约数 (6)1.5 欧几里得扩展 (6)1.6 素数表 (7)1.7 判断素数 (8)1.8 分解质因数 (9)1.9 欧拉函数 (10)1.10 欧拉函数表 (11)1.11 mobius函数 (12)1.12 数值积分 (12)1.13 数值积分（精确） (13)1.14 快速幂求余 (14)1.15 进制转换 (15)1.16 格雷码 (16)1.17 高精度类 (16)1.18 Fibonacci数列 (22)1.19 FFT (23)2.图论2.1 拓扑排序 (24)2.2 dijkstra (25)2.3 floyd-warshall (26)2.4 kruskal …………………263.序列3.1 快速排序 (28)3.2 逆序对 (28)3.3 最长不降子序列长度 (30)3.4 最长公共子序列长度 (31)3.5 最长公共上升子序列长度 (31)3.6 最长公共上升子序列 (32)4.字符串4.1 Sunday (34)4.2 子串清除 (34)4.3 KMP (37)5.数据结构5.1 并查集 (38)5.2 树状数组 (39)5.3 左偏树 (40)5.4 哈希 (41)5.5 RMQ线段树 (41)6.其他6.1 多边形面积 (43)6.2 幻方构造 (43)6.3 奇数阶次幻方 (45)1.1矩阵#include <iostream>#include <cstring>using namespace std;const int MAXN=100;const int MAXM=100;struct Matrix{int n,m;int a[MAXN][MAXM];void clear(){m=n=0;memset(a,0,sizeof(a));}Matrix operator +(const Matrix &b) const {Matrix tmp;tmp.n=n; tmp.m=m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)tmp.a[i][j]=a[i][j]+b.a[i][j];return tmp;}Matrix operator *(const Matrix &b) const {Matrix tmp;tmp.clear();tmp.n=n; tmp.m=m;for(int i=0;i<n;i++)for(int j=0;j<b.m;j++)for(int k=0;k<m;k++)tmp.a[i][j]+=a[i][k]*b.a[k][j];return tmp;}};1.2一次方程组的解#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#define MAX 10#define EPS 1e-8using namespace std;double a[MAX][MAX+1];bool l[MAX];double ans[MAX];void swap(double &x,double &y){double t;t=x;x=y;y=t;}inline int solve(double a[MAX][MAX+1],bool l[],double ans[],const int &n) {int res=0,r=0;int i,j,k;memset(ans,0,sizeof(a));memset(l,false,n);for(i=0;i<n;i++){for(j=r;j<n;j++)if(fabs(a[i][j])>EPS){for(k=i;k<=n;k++)swap(a[j][k],a[r][k]);break;}if(fabs(a[r][i])<EPS){res++;continue;}for(j=0;j<n;j++)if(j!=r&&fabs(a[j][i])>EPS){double tmp=a[j][i]/a[r][i];for(k=i;k<=n;k++)a[j][k]-=tmp*a[r][k];}l[i]=true;r++;}for(i=0;i<n;i++)if(l[i])for(j=0;j<n;j++)if(fabs(a[j][i])>EPS)ans[i]=a[j][n]/a[j][i];for(i=0;i<n;i++)if(fabs(ans[i])<EPS)ans[i]=0;return res;}int main(){int n;int i,j,res;cin>>n;for(i=0;i<n;i++)for(j=0;j<n+1;j++)cin>>a[i][j];res=solve(a,l,ans,n);for(i=0;i<n;i++)cout<<ans[i]<<" ";return 0;}1.3矩阵的逆#include <iostream>#include <vector>#include <cmath>#include <algorithm>#define MAX 10using namespace std;vector<double> a[MAX];vector<double> c[MAX];inline vector<double> operator *(vector<double> a,double b) {int i;int n=a.size();vector<double> res(n,0);res[i]=a[i]*b;return res;}inline vector<double> operator -(vector<double> a,vector<double> b) {int i;int n=a.size();vector<double> res(n,0);for(i=0;i<n;i++)res[i]=a[i]-b[i];return res;}inline void inverse(vector<double> a[],vector<double> c[],int n) {int i,j;for(i=0;i<n;i++)c[i]=vector<double> (n,0);for(i=0;i<n;i++)c[i][i]=1;for(i=0;i<n;i++){for(j=i;j<n;j++)if(fabs(a[j][i]>0)){swap(a[i],a[j]);swap(c[i],c[j]);break;}c[i]=c[i]*(1/a[i][i]);a[i]=a[i]*(1/a[i][i]);for(j=0;j<n;j++)if(j!=i&&fabs(a[j][i])>0){c[j]=c[j]-c[i]*a[j][i];a[j]=a[j]-a[i]*a[j][i];}}}int main(){int n,i,j;double x;cin>>n;for(j=0;j<n;j++){cin>>x;a[i].push_back(x);}inverse(a,c,n);for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<c[i][j]<<" ";cout<<endl;}return 0;}1.4最大公约数#include <stdio.h>int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int lcm(int a,int b){return a*b/gcd(a,b);}1.5欧几里得扩展#include <iostream>using namespace std;int gcd(int a,int b,int &x,int &y) {if(b==0){x=1;y=0;return a;}else{int r=gcd(b,a%b,y,x);y-=x*(a/b);return r;}}int main(){int a,b,x,y;scanf("%d%d",&a,&b);printf("%d ",gcd(a,b,x,y));printf("%d %d",x,y);return 0;}/*求AB的最大公约数，且求出X,Y使得AX+BY=gcd(A,B);15 205 -1 1*/1.6素数表#include <iostream>#include <cmath>#include <cstring>#define MAX 350000000using namespace std;bool valid[MAX];int prime[MAX];void getprime(int n,int &tot,int ans[]){int i,j;memset(valid,true,sizeof(valid));for(i=2;i<=n;i++){if(valid[i]){tot++;ans[tot]=i;}for(j=1;(j<=tot)&&(i*ans[j]<=n);j++){valid[i*ans[j]]=false;if(i%ans[j]==0)break;}}}int main(){int i,n,sum=0,j=0;cin>>n;getprime(n,sum,prime);for(i=1;i<=sum;i++){cout<<prime[i]<<" ";j++;if(j%10==0)cout<<endl;}return 0;}1.7判断素数#include <iostream>#include <cmath>using namespace std;long long int rsa(long long int a,long long int k,long long int m) {if(k==0)return 1%m;long long int tmp=rsa(a,k>>1,m);tmp=tmp*tmp%m;if(k&1)tmp=tmp*a%m;return tmp;}bool test(int n,int a,int d){if(n==2)return true;if(n==a)return true;if((n&1)==0)return false;while(!(d&1))d=d>>1;long long int t=rsa(a,d,n);while((d!=n-1)&&(t!=1)&&(t!=n-1)){t=t*t%n;d=d<<1;}return (t==n-1)||((d&1)==1);}bool isprime(int n){if(n<2)return false;int a[]={2,3,61,4567,23456789},i;for(i=0;i<5;i++)if(!test(n,a[i],n-1))return false;return true;}int main(){long long int i,n,sum=0;cin>>n;for(i=2;i<=n;i++)if(isprime(i)){cout<<i<<" ";sum++;if(sum%10==0)cout<<endl;}return 0;}1.8分解质因数#include <iostream>#include <cmath>#define MAX 10000long long int a[MAX],b[MAX],tot;using namespace std;void factor(long long int n,long long int a[],long long int b[],long long int &tot) {long long int temp=sqrt(n)+1,now=n;int i;tot=0;for(i=2;i<=temp;i++)if(now%i==0)a[++tot]=i;b[tot]=0;while(now%i==0){b[tot]++;now/=i;}temp=sqrt(now)+1;}if(now!=1){a[++tot]=now;b[tot]=1;}}int main(){long long int n,i;cin>>n;//fenjie(n,2);factor(n,a,b,tot);for(i=1;i<=tot;i++)cout<<a[i]<<" ";cout<<endl;for(i=1;i<=tot;i++)cout<<b[i]<<" ";return 0;}/*7212345678900630630*/1.9欧拉函数#include <stdio.h>long long int eular(long long int n) {long long int ret=1,i;for(i=2;i*i<=n;i++)if(n%i==0){n/=i,ret*=i-1;while(n%i==0)n/=i,ret*=i;}ret*=n-1;return ret;}int main(){long long int n;scanf("%lld",&n);printf("%lld",eular(n));return 0;}//小于或等于n的数中与n互质的数的个数。

一、粒子群算法粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为PSO，是近年来发展起来的一种新的进化算法((Evolu2tionary Algorithm - EA）.PSO 算法属于进化算法的一种，和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的交叉(Crossover）和变异(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。

这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。

优化问题是工业设计中经常遇到的问题，许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题，人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点，二是要求有较高的收敛速度。

爬山法精度较高，但是易于陷入局部极小。

遗传算法属于进化算法(EvolutionaryAlgorithms）的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解。

遗传算法有三个基本算子:选择、交叉和变异.但是遗传算法的编程实现比较复杂,首先需要对问题进行编码，找到最优解之后还需要对问题进行解码，另外三个算子的实现也有许多参数，如交叉率和变异率，并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验。

1995年Eberhart 博士和kennedy博士提出了一种新的算法；粒子群优化（ParticalSwarmOptimization-PSO）算法。

这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。

粒子群优化(ParticalSwarmOptimization—PSO）算法是近年来发展起来的一种新的进化算法（Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种，和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质。

一、基本算法1．交换（两量交换借助第三者）例1、任意读入两个整数，将二者的值交换后输出。

main(){int a,b,t;scanf("%d%d",&a,&b);printf("%d,%d\n",a,b);t=a; a=b; b=t;printf("%d,%d\n",a,b);}【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。

假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。

其中t为中间变量，起到“空杯子”的作用。

注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例2、任意读入三个整数，然后按从小到大的顺序输出。

main(){int a,b,c,t;scanf("%d%d%d",&a,&b,&c);/*以下两个if语句使得a中存放的数最小*/if(a>b){ t=a; a=b; b=t; }if(a>c){ t=a; a=c; c=t; }/*以下if语句使得b中存放的数次小*/if(b>c) { t=b; b=c; c=t; }printf("%d,%d,%d\n",a,b,c);}2．累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。

“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。

例1、求1+2+3+……+100的和。

main(){int i,s;s=0; i=1;while(i<=100){s=s+i; /*累加式*/i=i+1; /*特殊的累加式*/}printf("1+2+3+...+100=%d\n",s);}【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。

常⽤算法模板开始存模板快速排序#include <cstdio>#include <algorithm>#include <iostream>using namespace std ;typedef long long ll ;const int maxN = 100010 ;int a[ maxN ] ;inline ll INPUT ( ) {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(x=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}void quick_sort ( const int l , const int r ) {if ( l > r ) {return ; ;}int i = l , j = r ;while ( i < j ) {while ( a[ j ] >= a[ l ] && j > i ) {--j ;}while ( a[ i ] <= a[ l ] && j > i ) {++i ;}if ( j > i )swap ( a[ i ] , a[ j ] ) ;}swap ( a[ l ] , a[ i ] ) ;quick_sort ( l , i - 1 ) ;quick_sort ( i + 1 , r ) ;}int main ( ) {int N = INPUT( ) ;for ( int i=1 ; i<=N ; ++i ) {a[ i ] = INPUT( ) ;}quick_sort ( 1 , N ) ;for ( int i=1 ; i<=N ; ++i ) {cout << a[ i ] << endl ;}return0 ;}View Code快速选择#include <cstdio>#include <algorithm>#include <iostream>using namespace std ;typedef long long ll ;const int maxN = 100010 ;int a[ maxN ] ;inline ll INPUT ( ) {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(x=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int quick_select ( const int l , const int r , const int K ) {int i = l , j = r ;while ( i < j ) {while ( a[ j ] >= a[ l ] && j > i ) {--j ;}while ( a[ i ] <= a[ l ] && j > i ) {++i ;}if ( j > i )swap ( a[ i ] , a[ j ] ) ;}swap ( a[ l ] , a[ i ] ) ;if ( i - l == K - 1 )return a[ i ] ;else if ( i - l >= K )return quick_select ( l , i - 1 , K ) ;elsereturn quick_select( i + 1 , r , K - ( i - l + 1 ) ) ;}int main ( ) {int N = INPUT ( ) ;int K = INPUT ( ) ;for ( int i=1 ; i<=N ; ++i ) {a[ i ] = INPUT( ) ;}cout << quick_select ( 1 , N , K ) << endl ;return0 ;}View Code树的重⼼//#include <bits/stdc++.h>#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;const int maxN = 20010 ;const int inf = 2147483647 ;struct Edge {int to , next ;}e[ maxN << 1 ] ;int head[ maxN ] , size[ maxN ] , hv[ maxN ] ;int _cnt ;int INPUT ( ) {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}void addEdge ( int x , int y ) {e[ ++_cnt ].to = y ;e[ _cnt ].next = head[ x ] ;head[ x ] = _cnt ;}void Dfs ( const int x , int fa ) {size[ x ] = 1 ;for ( int i=head[ x ] ; i ; i=e[ i ].next ) {if ( e[ i ].to != fa ) {Dfs ( e[ i ].to , x ) ;size[ x ] += size[ e[ i ].to ] ;}}for ( int i=head[ x ] ; i ; i=e[ i ].next ) {if ( e[ i ].to != fa && size[ e[ i ].to ] > size[ hv[ x ] ] ) {hv[ x ] = e[ i ].to ;}}}void init ( ){_cnt = 0 ;memset ( size , 0 , sizeof ( size ) ) ;memset ( hv , 0 , sizeof ( hv ) ) ;memset ( head , 0 , sizeof ( head ) ) ;}int main ( ) {for ( int T = INPUT ( ) ; T ; --T ) {init ( ) ;int N = INPUT ( ) ;for ( int i=1 ; i<N ; ++i ) {int x = INPUT ( ) , y = INPUT ( );addEdge ( x , y ) ;addEdge ( y , x ) ;}Dfs ( 1 , 1 ) ;int tmp , minNode = 0 , minval = inf ;for ( int i=1 ; i<=N ; ++i ) {int tmp = max ( size[ hv[ i ] ] , N - size[ i ] ) ;if ( tmp < minval ) {minval = tmp ;minNode = i ;}}printf ( "%d %d\n" , minNode , minval ) ;}return0 ;}poj1655Tire树#include <bits/stdc++.h>using namespace std ;const int maxN = 5010 ;typedef long long LL ;struct tireNode {int cnt ;bool last ;struct tireNode *next[ 26 ] ;tireNode ( ) {//构造⽅法初始化cnt = 0 ;last = false ;memset ( next , 0 , sizeof ( next ) ) ;}};char str_[ maxN ] ;void insert ( tireNode *root , char str[ ] ) {int len = strlen ( str + 1 ) ;tireNode *cur = root ;for ( int i=1 ; i<=len ; ++i ) {char ch = str[ i ] - 'a' ;if ( cur -> next[ ch ] == NULL ) {tireNode* newNode = new tireNode ;cur -> next[ ch ] = newNode ;}cur = cur -> next[ ch ] ;cur->cnt++ ;}cur -> last = true ;}bool find ( tireNode *root , char str[ ] ) {int len = strlen ( str + 1 ) ;tireNode *cur = root ;for ( int i=1 ; i<=len ; ++i ) {char ch = str[ i ] - 'a' ;if ( cur -> next[ ch ] == NULL ) return false ; cur = cur -> next[ ch ] ;}if ( cur -> last == true ) return true ;return false ;}int main ( ) {int N , M ;tireNode* root = new tireNode ;scanf ( "%d" , &N ) ;for ( int i=1 ; i<=N ; ++i ) {scanf ( "%s" , str_ + 1 ) ;insert ( root , str_ ) ;}scanf ( "%d" , &M ) ;for ( int i=1 ; i<=M ; ++i ) {scanf ( "%s" , str_ + 1 ) ;if ( find ( root , str_ ) ) printf ( "Yes\n" ) ;else printf ( "No\n" ) ;}return0 ;}动态字典树#include <bits/stdc++.h>using namespace std ;const int maxNode = 10010 ;typedef long long LL ;struct tireTree {static const int maxLen = 26 ;int tr[ maxNode ][ maxLen ] ;bool end[ maxNode ] ;int count[ maxNode ] ;int _cnt ;tireTree ( ) {_cnt = 1 ;memset ( tr , 0 , sizeof ( tr ) ) ;memset ( end , false , sizeof ( end ) ) ; }public :void insert ( char str[ ] ) {int cur = 1 , len = strlen ( str + 1 ) ;for ( int i=1 ; i<=len ; ++i ) {int idx = str[ i ] - 'a' ;if ( !tr[ cur ][ idx ] ) {tr[ cur ][ idx ] = ++_cnt ;}cur = tr[ cur ][ idx ] ;}end[ cur ] = true ;}public :bool exist ( char str[ ] ) {int cur = 1 , len = strlen ( str + 1 ) ;for ( int i=1 ; i<=len ; ++i ) {int idx = str[ i ] - 'a' ;if ( !tr[ cur ][ idx ] ) {return false ;}cur = tr[ cur ][ idx ] ;}return end[ cur ] ;}};tireTree tree ;char str[ 2000 ] ;int main ( ) {int N , M ;scanf ( "%d" , &N ) ;for ( int i=1 ; i<=N ; ++i ) {scanf ( "%s" , str + 1 ) ;tree.insert ( str ) ;}scanf ( "%d" , &M ) ;for ( int i=1 ; i<=M ; ++i ) {scanf ( "%s" , str + 1 ) ;if ( tree.exist ( str ) )printf ( "YES\n" ) ;elseprintf ( "NO\n" ) ;}return0 ;}静态字典树单调栈#include <iostream>#include <stack>#include <cstdio>using namespace std ;const int INF = 2147483647 ;class Element {private :int Val , Index ;public :Element ( ) {Val = 0 ;Index = -1 ;}Element ( const int __x , const int __y ) { Val = __x ;Index = __y ;}int getVal ( ) {return Val ;}int getIndex ( ) {return Index ;}void print ( ) {if ( Index == -1 ) cout << "Do not exist!!" << endl ;else cout << Index << "" << Val << endl ;}};stack <Element> stk ;int arr[ 100 ] ;Element Ans[ 100 ] ;int In ( ) {int x = 0 , f = 1 ; char ch = getchar ( ) ;while ( ch < '0' || ch > '9' ) { if ( ch == '-')f = -1 ; ch = getchar ( ) ;}while ( ch >= '0' && ch <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + ch - '0' ; ch = getchar ( ) ;} return x * f ;}int main ( ) {int N = In ( ) ;for ( int i=1 ; i<=N ; ++i ) arr[ i ] = In ( ) ;for ( int i=1 ; i<=N+1 ; ++i ) {Element ele ;if ( i != N+1 ) ele = Element ( arr[i] , i ) ;else ele = Element ( INF , -1 ) ;while ( !stk.empty ( ) && stk.top().getVal( ) < ele.getVal() ) {Ans[ stk.top().getIndex() ] = ele ;stk.pop ( ) ;}stk.push(ele) ;}for ( int i=1 ; i<=N ; ++i ) Ans[ i ].print ( ) ;return0 ;}View Code。

专用模板目录：一、图论1．最大团2．拓扑排序3．最短路和次短路4．SAP模板5．已知各点度，问能否组成一个简单图6．KRUSKAL7. Prim算法求最小生成树8. Dijkstra9 . Bellman-ford10. SPFA11. Kosaraju 模板12. tarjan 模板二、数学1. 剩余定理2. N!中质因子P的个数3.拓展欧几里得4.三角形的各中心到顶点的距离和5.三角形外接圆半径周长6.归并排序求逆序数7. 求N！的位数8.欧拉函数9. Miller-Rabin,大整数分解，求欧拉函数10. 第一类斯特林数11.计算表达式12.约瑟夫问题13．高斯消元法14. Baby-step,giant-step n是素数.n任意15. a^b%c=a ^(b%eular(c)+eular(c)) % c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20.行列式计算21. 返回x 的二进制表示中从低到高的第i位22.高精度运算 +-*/23.超级素数筛选三、数据结构1．树状数组2.线段树求区间的最大、小值3.线段树求区间和4.单调队列5.KMP模板6. 划分树，求区间第k小数7.最大堆，最小堆模板8. RMQ模板求区间最大、最小值9.快速排序，归并排序求逆序数.10.拓展KMP四、计算几何1.凸包面积2.Pick公式求三角形内部有多少点3.多边形边上内部各多少点以及面积pick4.平面最远点对5.判断矩形是否在矩形内6.判断点是否在多边形内7.判断4个点(三维)是否共面8.凸包周长9.等周定理变形一直两端点和周长求最大面积10.平面最近点对11.单位圆最多覆盖多少点(包括边上)12.多边形费马点求点到多边形各个点的最短距离13.矩形并周长14.zoj 2500 求两球体积并一、图论1.最大团#include<iostream>#include<algorithm>using namespace std;int n,m;int cn;//当前顶点数int best;//当前最大顶点数int vis[50];//当前解int bestn[50];//最优解int map[50][50];//临界表void dfs(int i){if(i>n){for(int j=1;j<=n;j++) bestn[j]=vis[j];best=cn;return ;}int ok=1;for(int j=1;j<i;j++){if(vis[j]==1&&map[i][j]==0){ok=0;break;}}if(ok){//进入左子树vis[i]=1;cn++;dfs(i+1);cn--;}if(cn+n-i>best){//进入右子树vis[i]=0;dfs(i+1);}}int main(){while(scanf("%d%d",&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){int p,q;scanf("%d%d",&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf("%d\n",best);}return 0;}2.拓扑排序#include<iostream>#include<cstring>using namespace std;int map[105][105],in[105],vis[105],ans[105],n;int flag;void dfs(int step){if(flag) return ;if(step==n+1) {flag=1; printf("%d",ans[1]);for(int i=2;i<=n;i++) printf(" %d",ans[i]);printf("\n");return ;}for(int i=1;i<=n;i++){if(vis[i]==0&&in[i]==0){vis[i]=1;for(int j=1;j<=n;j++){if(map[i][j]>0){map[i][j]=-map[i][j];in[j]--;}}ans[step]=i;dfs(step+1);vis[i]=0;for(int j=1;j<=n;j++){if(map[i][j]<0){map[i][j]=-map[i][j];in[j]++;}}}}}int main(){while(scanf("%d",&n)==1){flag=0;memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i=1;i<=n;i++){int t;while(scanf("%d",&t),t){map[i][t]=1;in[t]++;}}dfs(1);}return 0;}3．最短路和次短路#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;class Node{public:int e,w;//表示终点和边权};const int inf=(1<<25);int main(){int ci;cin>>ci;while(ci--){vector<Node> G[1005];//用邻接表存边int n,m;cin>>n>>m;for(int i=1;i<=m;i++){Node q;int u;cin>>u>>q.e>>q.w;G[u].push_back(q);}int s,f;//起点和终点cin>>s>>f;//dijkstra 求最短路和次短路int flag[1005][2];int dis[1005][2],cnt[1005][2];//0表示最短路，1表示次短路memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=inf;dis[s][0]=0;cnt[s][0]=1;//初始化for(int c=0;c<2*n;c++) //找最短路和次短路，故要进行2*n次循环也可以改成while(1){int temp=inf,u=-1,k;//找s-S'集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路for(int j=1;j<=n;j++){if(flag[j][0]==0&&temp>dis[j][0]) temp=dis[j][0],u=j,k=0;else if(flag[j][1]==0&&temp>dis[j][1]) temp=dis[j][1],u=j,k=1;}if(temp==inf) break;//S'集合为空或者不联通，算法结束//更新路径flag[u][k]=1;for(int l=0;l<G[u].size();l++){int d=dis[u][k]+G[u][l].w,j=G[u][l].e;//important//4种情况if(d<dis[j][0]){dis[j][1]=dis[j][0];cnt[j][1]=cnt[j][0];dis[j][0]=d;cnt[j][0]=cnt[u][k];}else if(d==dis[j][0]){cnt[j][0]+=cnt[u][k];}else if(d<dis[j][1]){dis[j][1]=d;cnt[j][1]=cnt[u][k];}else if(d==dis[j][1]){cnt[j][1]+=cnt[u][k];}}}int num=cnt[f][0];//最短路int cc=cnt[f][1];//次短路}return 0;}4．SAP模板#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int inf=(1<<31)-1;const int point_num=300;int cap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面int s0,t0,n;//源,汇和点数int find_path(int p,int limit=0x3f3f3f3f){if(p==t0) return limit;for(int i=0;i<n;i++)if(dist[p]==dist[i]+1 && cap[p][i]>0){int t=find_path(i,min(cap[p][i],limit));if(t<0) return t;if(t>0){cap[p][i]-=t;cap[i][p]+=t;return t;}}int label=n;for(int i=0;i<n;i++) if(cap[p][i]>0) label=min(label,dist[i]+1);if(--gap[dist[p]]==0 || dist[s0]>=n ) return -1;++gap[dist[p]=label];return 0;}int sap(){//初始化s,ts0=0,t0=n-1;int t=0,maxflow=0;gap[0]=n;while((t=find_path(s0))>=0) maxflow+=t;return maxflow;}int main(){int ci;while(cin>>ci>>n){//初始化memset(cap,0,sizeof(cap));memset(dist,0,sizeof(dist));memset(gap,0,sizeof(gap));//初始化capwhile(ci--){int x,y,c;cin>>x>>y>>c;x--;y--;cap[x][y]+=c;//因题而异}int ans=sap();cout<<ans<<endl;}return 0;}5．已知各点度，问能否组成一个简单图#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int inf=(1<<30);int d[1100];bool cmp(int x,int y){return x>y;}int main(){int ci;scanf("%d",&ci);while(ci--){int n,flag=1,cnt=0;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d",&d[i]);if(d[i]>n-1||d[i]<=0) flag=0; cnt+=d[i];}if(flag==0||cnt%2){printf("no\n");continue;}sort(d,d+n,cmp);for(int l=n;l>0;l--){for(int i=1;i<l&&d[0];i++){d[0]--,d[i]--;if(d[i]<0){flag=0;break;}}if(d[0]) flag=0;if(flag==0) break;d[0]=-inf;sort(d,d+l,cmp);}if(flag) printf("yes\n");else printf("no\n");}return 0;}6.KRUSKAL#include<iostream>#include<algorithm>using namespace std;int u[15005],v[15005],w[15005],fath[15005],r[15005];int ans1[15005],ans2[15005];bool cmp(int i,int j){return w[i]<w[j];}int find(int x){return fath[x]==x?x:fath[x]=find(fath[x]);}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) fath[i]=i;for(int i=1;i<=m;i++) r[i]=i;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];}sort(r+1,r+m+1,cmp);int maxn=0,ans=0,k=0;for(int i=1;i<=m;i++){int e=r[i];int x=find(u[e]),y=find(v[e]);if(x!=y){ans+=w[e];fath[x]=y;if(w[e]>maxn) maxn=w[e];ans1[k]=u[e];ans2[k++]=v[e];}}return 0;}7.prime求最小生成树语法：prim(Graph G,int vcount,int father[]);参数：G：图，用邻接矩阵表示vcount：表示图的顶点个数father[]：用来记录每个节点的父节点返回值：null注意：常数max_vertexes 为图最大节点数常数infinity为无穷大源程序：#define infinity 1000000#define max_vertexes 5typedef int Graph[max_vertexes][max_vertexes];void prim(Graph G,int vcount,int father[]){int i,j,k;intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes]; for (i=0;i<vcount;i++){lowcost[i]=G[0][i];closeset[i]=0;used[i]=0;father[i]=-1;}used[0]=1;for (i=1;i<vcount;i++){j=0;while (used[j]) j++;for (k=0;k<vcount;k++)if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;father[j]=closeset[j];used[j]=1;for (k=0;k<vcount;k++)if (!used[k]&&(G[j][k]<lowcost[k])){ lowcost[k]=G[j][k];closeset[k]=j; }}}8.Dijkstra语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]); 参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径返回值：最短路径长度注意：输入的图的权必须非负顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Dijkstra(Graph G,int n,int s,int t, int path[]){int i,j,w,minc,d[max_vertexes],mark[max_vertexes];for (i=0;i<n;i++) mark[i]=0;for (i=0;i<n;i++){ d[i]=G[s][i];path[i]=s; }mark[s]=1;path[s]=0;d[s]=0;for (i=1;i<n;i++){minc=infinity;w=0;for (j=0;j<n;j++)if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}mark[w]=1;for (j=0;j<n;j++)if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){ d[j]=d[w]+G[w][j];path[j]=w; }}return d[t];}9.Bellman-ford语法：result=Bellman_ford(Graph G,int n,int s,int t,int path[],int success);参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径success：函数是否执行成功返回值：最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Bellman_ford(Graph G,int n,int s,int t,int path[],int success){int i,j,k,d[max_vertexes];for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}d[s]=0;for (k=1;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]) return 0;success=1;return d[t];}10. SPFA#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const __int64 maxn=1001000;const __int64 inf=1000100000;struct edge//邻接表{__int64 t,w;//s->t=w;__int64 next;//数组模拟指针};__int64 p[maxn],pf[maxn];//邻接表头节点edge G[maxn],Gf[maxn];//邻接表__int64 V,E;//点数[1-n] 边数__int64 dis[maxn];__int64 que[maxn],fro,rear;//模拟队列__int64 vis[maxn];__int64 inque[maxn];//入队次数bool spfa(__int64 s0){fro=rear=0;for(__int64 i=1;i<=V;i++) dis[i]=inf;dis[s0]=0;memset(vis,0,sizeof(vis));memset(inque,0,sizeof(inque));que[rear++]=s0;vis[s0]=1;inque[s0]++;while(fro!=rear){__int64 u=que[fro];fro++;if(fro==maxn) fro=0;vis[u]=0;for(__int64 i=p[u];i!=-1;i=G[i].next){__int64 s=u,t=G[i].t,w=G[i].w;if(dis[t]>dis[s]+w){dis[t]=dis[s]+w;if(vis[t]==0){que[rear++]=t,vis[t]=1;inque[t]++;if(inque[t]>V) return false;if(rear==maxn) rear=0;}}}}return true;}int main(){__int64 ci;scanf("%I64d",&ci);while(ci--){scanf("%I64d%I64d",&V,&E);memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf)); for(__int64 i=0;i<E;i++){__int64 u,v,w;scanf("%I64d%I64d%I64d",&u,&v,&w);G[i].t=v;G[i].w=w;G[i].next=p[u];p[u]=i;Gf[i].t=u;Gf[i].w=w;Gf[i].next=pf[v];pf[v]=i;}__int64 ans=0;spfa(1);//求第一个点到其他点的最短距离和for(__int64 i=1;i<=V;i++) ans+=dis[i];//反方向再来一次spfa 求其他点到第一个点的最短距离和 for(__int64 i=1;i<=V;i++) p[i]=pf[i];for(__int64 i=0;i<E;i++) G[i]=Gf[i];spfa(1);for(__int64 i=1;i<=V;i++) ans+=dis[i];printf("%I64d\n",ans);}return 0;}11.Kosaraju模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;struct edge{int t,w;//u->t=w;int next;};int V,E;//点数(从1开始)，边数int p[maxn],pf[maxn];//邻接表原图,逆图edge G[maxn],Gf[maxn];//邻接表原图,逆图int l,lf;void init(){memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf));l=lf=0;}void addedge(int u,int t,int w,int l){G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}void addedgef(int u,int t,int w,int lf){Gf[l].w=w;Gf[l].t=t;Gf[l].next=pf[u];pf[u]=l;}///Kosaraju算法,返回为强连通分量个数bool flag[maxn]; //访问标志数组int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点//用于第一次深搜,求得numb[1..n]的值void VisitOne(int cur, int &sig){flag[cur] = true;for (int i=p[cur];i!=-1;i=G[i].next){if (!flag[G[i].t]){VisitOne(G[i].t,sig);}}numb[++sig] = cur;}//用于第二次深搜,求得belg[1..n]的值void VisitTwo(int cur, int sig){flag[cur] = true;belg[cur] = sig;for (int i=pf[cur];i!=-1;i=Gf[i].next){if (!flag[Gf[i].t]){VisitTwo(Gf[i].t,sig);}}//Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent(){int i, sig;//第一次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=1; i<=V; ++i ){if ( false==flag[i] ){VisitOne(i,sig);}}//第二次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=V; i>0; --i ){if ( false==flag[numb[i]] ){VisitTwo(numb[i],++sig);}}return sig;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int u=i,t,w=1;while(scanf("%d",&t)==1&&t){E++;addedge(u,t,w,l++);addedgef(t,u,w,lf++);}}int ans=Kosaraju_StronglyConnectedComponent(); printf("%d\n",ans);}return 0;12.tarjan模板//自己模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int belg[maxn];//第i个节点属于belg[i]个强连通分量int stck[maxn],stop;//stck栈int instck[maxn];//第i个节点是否在栈中int scnt;//强联通分量int index;void dfs(int i){dfn[i]=lowc[i]=++index;instck[i]=1;//节点i入栈stck[++stop]=i;for(int j=p[i];j!=-1;j=G[j].next){int t=G[j].t;//更新lowc数组if(!dfn[t])//t没有遍历过{dfs(t);if(lowc[i]>lowc[t]) lowc[i]=lowc[t];}//t是i的祖先节点else if(instck[t]&&lowc[i]>dfn[t]) lowc[i]=dfn[t];}//是强连通分量的根节点if(dfn[i]==lowc[i]){scnt++;int t;do{t=stck[stop--];instck[t]=0;belg[t]=scnt;}while(t!=i);}}int tarjan(){stop=scnt=index=0;memset(dfn,0,sizeof(dfn));memset(instck,0,sizeof(instck));for(int i=1;i<=V;i++){if(!dfn[i]) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}//吉大模板邻接表版#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int stck[maxn],stop;//stck栈int pre[maxn];//int scnt;//强联通分量int cnt;//void dfs(int v)//1-V{int t,minc=lowc[v]=pre[v]=cnt++;stck[stop++]=v;for(int i=p[v];i!=-1;i=G[i].next){int pv=G[i].t;if(pre[pv]==-1) dfs(pv);if(lowc[pv]<minc) minc=lowc[pv]; }if(minc<lowc[v]){lowc[v]=minc;return ;}do{dfn[t=stck[--stop]]=scnt;lowc[t]=V;}while(t!=v);++scnt;}int tarjan(){stop=cnt=scnt=0;memset(pre,-1,sizeof(pre));for(int i=1;i<=V;i++){if(pre[i]==-1) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}二、数学1．剩余定理int mod(int c[],int b[],int n){int all_multy=1,sum=0;int i,j,x[5];for(i=0;i<n;i++)all_multy*=c[i];for(i=0;i<n;i++)x[i]=all_multy/c[i];for(i=0;i<n;i++){j=1;while((x[i]*j)%c[i]!=1)j++;x[i]*=j;}for(i=0;i<n;i++)sum+=(b[i]*x[i]);return sum%all_multy;}2．N!中质因子P的个数//对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p。

核心算法——ACM模板一、贪心算法 (2)1、区间选点 (2)2、区间覆盖 (2)3、不相交区间 (2)4、哈夫曼编码 (2)5、最小值最大化、最大值最小化（二分查找） (2)二、动态规划 (5)1、最长公共子序列（LCS） (5)2、最长上升公共子序列（LIS） (7)3、子段和 (9)4、DAG上的动态规划 (13)5、区间DP (17)6、状态压缩DP (24)7、双线DP (30)8、背包问题(见背包九讲) (32)三、数据结构 (32)1、并查集 (32)2、树状数组 (34)3、（字符串）KMP匹配 (37)四、最小生成树算法 (41)Prime核心算法 (41)Kruskal算法 (44)五、单源最短路径 (50)Dijkstra核心算法 (50)Bellman_Ford算法 (54)SPFA算法（Bellman_Ford的队列实现） (58)六、二分图匹配 (61)1、匈牙利算法 (61)七、网络流 (63)1、SAP算法 (64)2、Dinic算法 (68)一、贪心算法1、区间问题区间选点选取尽量少的点覆盖所有的区间，是每个区间至少包含一个点。

对区间右端点进行排序。

区间覆盖选取尽量少的区间覆盖整个区域。

对左端点进行排序。

不相交区间选取尽量多的不相交区间。

对区间右端点进行排序。

2、哈夫曼编码3、最小值最大化、最大值最小化（二分查找）NYOJ 疯牛问题（最小值最大化）农夫John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000).但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。

为了不让牛互相伤害。

John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？#include#include#includeusing namespace std;int n, c;int pos[100005];bool judge(int k){int cnt = 1;int st = pos[0];for(int i = 1; i < n; ++i){if(pos[i] - st >= k){++cnt;if(cnt >= c)return true;st = pos[i];}}return false;}int Binary_search(int left, int right) /// 二分枚举满足条件的最大距离{while(left <= right){int mid = (left + right) >> 1;if(judge(mid)) /// 所求距离 >= mid，可以继续增大试探left = mid+1;else /// 所求距离 < mid,所以必须减小来试探right = mid-1;}return left-1;}int main(){while(~scanf("%d%d", &n, &c)){for(int i = 0; i < n; ++i)scanf("%d", &pos[i]);sort(pos, pos+n);printf("%d\n", Binary_search(0, pos[n-1] - pos[0]));}return 0;}NYOJ 摘枇杷（最大值最小化）理工学院的枇杷快熟了，ok，大家都懂得。

OI 算法模板1. 介绍OI（Olympiad in Informatics）是信息学奥林匹克竞赛的缩写，是一种选拔优秀计算机程序设计员的竞赛形式。

OI 算法模板是 OI 竞赛中常用的一些算法和数据结构的模板总结，可以帮助选手在竞赛中快速解决问题。

本文将介绍常见的 OI 算法模板，包括搜索算法、排序算法、图算法、动态规划等，以及一些常用的数据结构。

每个算法和数据结构都会给出详细的算法思想、实现方法和复杂度分析。

2. 搜索算法2.1 深度优先搜索（DFS）深度优先搜索是一种常见的搜索算法，通过递归或栈实现。

其基本思想是从起点出发，尽可能深地搜索每个可能的路径，直到找到目标或无法继续搜索为止。

def dfs(node):if node is None:return# 处理当前节点process(node)# 递归处理相邻节点for neighbor in node.neighbors:if neighbor not in visited:visited.add(neighbor)dfs(neighbor)时间复杂度：O(V+E)，其中 V 是顶点数，E 是边数。

2.2 广度优先搜索（BFS）广度优先搜索是一种常见的搜索算法，通过队列实现。

其基本思想是从起点出发，逐层地向外扩展，直到找到目标或无法继续扩展为止。

from collections import dequedef bfs(start):queue = deque([start])visited = set([start])while queue:node = queue.popleft()# 处理当前节点process(node)# 处理相邻节点for neighbor in node.neighbors:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)时间复杂度：O(V+E)，其中 V 是顶点数，E 是边数。

算法模板数论：1、筛法素数产⽣器int findprime(int prime[],int n){int num,i,j,k,counter,*base,pown; n++; n/=2;pown=n*2;base=(int*)malloc(sizeof(int)*(n+1)*2); prime[0]=2;prime[1]=3;counter=2; for(i=1;i<=pown;i++)base[i]=0;for(i=3;i<=n;i+=3)for(j=0;j<2;j++){num=2*(i+j)-1;while(0==base[num]){prime[counter++]=num;for(k=num;k<=pown;k+=num){base[k]=1;}}}free(base);return counter;}数据结构1、中缀表达式转后缀表达式string str,suf;void translate();{ios::sync_with_stdio(false);co['+']=1,co['-']=1,co['*']=2,co['/']=2,co['%']=2;cin>>str;translate();cout<return 0;} void translate(){stacks;int size=str.size();for(register int i=0;i{if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')) suf.push_back(str[i]); else{if(s.empty()||(co[str[i]]>co[s.top ()])) s.push(str[i]);else{while(!s.empty()&&(co[s.top ()]>=co[str[i]])){suf.push_back(s.top());s.pop();}s.push(str[i]);}}}while(!s.empty()){s.pop();}}STL应⽤1、map: find() 找到返回指针，否则返回.end();Count()找到返回⼤于零的整数，否组返回0 mymap.insert ( pair('a',100) ); mymap['a']="an element";2、stringsize_t found;found=str.find(str2);if (found!=string::npos)图的遍历（深搜，⼴搜）深搜1、⽆路可逃？bool matrix[maxn][maxn]={0};bool tag[maxn][maxn]={0};int mx[]={0,1,0,-1};int my[]={-1,0,1,0};int t,n,m,sx,sy,tx,ty;int tempx,tempy;bool judge(){if(tempx>=0&&tempx=0&&tempyreturn true;else return false;}bool find(int x,int y){if(x==tx&&y==ty)return true;for(register int i=0;i<4;++i){tempx=x+mx[i];tempy=y+my[i];i f(tag[tempx][tempy]==false&&judge()&&matrix[tempx][tempy])tag[tempx][tempy]=1;if(find(tempx,tempy))return true;else tag[tempx][tempy]=false; }}return false;}2、How many setsint n,m;int count;void find(int start,int num){if(num==m){count++;return;}for(register int i=start;i<=n;++i) {find(i+2,num+1);}return;}⼴搜：1、knight movesstruct point{short x;short y;};short mx[]={1,2,2,1,-1,-2,-2,-1}; short my[]={2,1,-1,-2,2,1,-1,-2}; bool judge(int x,int y)if(x>0&&x<9&&y>0&&y<9)return true; else return false;}int bfs(point start,point end){bool tag[9][9]={0};int path[9][9]={0};queueq;q.push(start);tag[start.x][start.y]=1;struct point cur,nex;while(!q.empty()){cur=q.front();q.pop();if(cur.x==end.x&&cur.y==end.y) return path[cur.x][cur.y];for(register int i=0;i<8;++i){nex=cur;nex.x+=mx[i];nex.y+=my[i];if(!tag[nex.x][nex.y]&&judge(nex.x,nex.y)){q.push(nex);tag[nex.x][nex.y]=1;path[nex.x][nex.y]=path[cur.x][cur.y]+1;}}}return path[end.x][end.y];}int jie[9]={0,1,2,6,24,120,720,5040,40320}; struct points {string steps;int num;};int contor(int num){int temp[9],result=0,count;for(register int i=8;i>=1;--i){temp[i]=num%10;num/=10;}for(register int i=1;i<=8;++i){count=0;for(register int j=i+1;j<=8;++j)if(temp[i]>temp[j]) ++count;result+=count*jie[8-i];}return result;}while(!q.empty()){cur=q.front();q.pop();if(cur.steps.size()>limit){cout<<"-1\n";break;}if(cur.num==target){cout<}temp=cur.num;fac[0]=A(temp);fac[1]=B(temp);fac[2]=C(temp);for(register int i=0;i<3;++i){con=contor(fac[i]);if(lable[con]==0){lable[con]=1;next.num=fac[i];next.steps=cur.steps+char('A'+i); q.push(next);}}}3、马的周游问题（剪枝）bool dfs(int x,int y,int count){if(count==64){path[count]=(x-1)*8+y;return true;}vectorv;struct points cur;visit[x][y]=1;for(register int i=0;i<8;++i){if(judge(x+mx[i],y+my[i])){cur.x=x+mx[i];cur.y=y+my[i];v.push_back(cur);}}sort(v.begin(),v.end(),comp);//剪枝short size=v.size();for(register short i=0;i{if(dfs(v[i].x,v[i].y,count+1)){path[count]=(v[i].x-1)*8+v[i].y; return true;}}visit[x][y]=0;return false;}图论：Dijkstra算法：1、Campusvoid dijkstra(int start,int end,int count) {int minalen=0,index;memset(tag,false,sizeof(tag));for(register int i=0;i{mina[i]=road[start][i];}mina[start]=0;tag[start]=1;for(int k=0;k{minalen=INF;for(register int i=0;i{if(mina[i]{minalen=mina[i];index=i;}}tag[index]=1;if(index==end)break;for(register int i=0;i{if(!tag[i])if(mina[i]>(minalen+road[index][i])) mina[i]=minalen+road[index][i];}}}2、kruskal算法for(register int k=0;kfor(register int i=0;ifor(register int j=0;j{if(dist[i][j]!=-1||dist[i][k]+ dist[k][j] dist[i][j]=dist[i][k]+dist[k][j];//Path[i][j]=Path[k][j];}3、prim算法for(register int j=1;j{minlen=MAX;for(register int i=1;i{if(!tag[i]&&dist[i]{index=i;}}tag[index]=1;if(maxfor(register int i=1;i{if(!tag[i]&&dist[i]>road[index][i]) dist[i]=road[index][i];}}图的存储、并查集1、邻接表struct node{int end;int len;node(int e,int l){end=e;len=l;}};vectorM[maxn];for(register int i=1;i{cin>>from>>to>>l;node N1(to,l);node N2(from,l);M[from].push_back(N1);M[to].push_back(N2);}2、并查集int father[MAX];int Rank[MAX];{father[x]=x;Rank[x]=0;}int Find_Set(int x){if(x!=father[x]){father[x]=Find_Set(father[x]);}return father[x];}void Union(int x,int y){x=Find_Set(x);y=Find_Set(y);if(x==y)return;if(Rank[x]>Rank[y]){father[y]=x;}else{if(Rank[x]==Rank[y]){Rank[y]++;}father[x]=y;}}int main(){int x,y;memset(father,-1,sizeof(father)); memset(Rank,0,sizeof(Rank));while(cin>>x>>y){if(father[x]==-1)Make_Set(x);if(father[y]==-1)Make_Set(y);if(Find_Set(x)!=Find_Set(y))cout<Union(x,y);}return0;}动态规划（DP背包）1、采药2、int value[maxnv];3、int max(int a,int b){4、return a>b?a:b;5、}6、for(i=0;i7、for(j=t;j>=w[i];j--)value[j]=max(value[j],value[j-w[i]]+v[i]);8、cout<9、return 0;10、}⾼精度1、⾼精度加法void add(int sum[],int num[]){for(int i=0;i<200;i++){sum[i]=sum[i]+num[i];sum[i+1]+=sum[i]/10;sum[i]=sum[i]%10;}}2、⾼精度乘法void mutiply(int sum[],int num[])int numsize;int store[200];register int i,j,k,carry=0,tempcarry;for(i=199;i>=0;i--)if(num[i]!=0){numsize=i;break;} for(i=0;i<200;i++) store[i]=sum[i];memset(sum,0,200*sizeof(int));for(j=0;j<=numsize;j++){memset(temp,0,200*sizeof(int));for(k=0;k<200-j;k++){temp[k+j]=store[k];}for(i=0;i<200;i++){temp[i]=num[j]*temp[i];tempcarry=temp[i]/10;temp[i]=temp[i]%10+carry;carry=tempcarry;carry+=temp[i]/10;temp[i]=temp[i]%10;}add(sum,temp);}}KMP算法int index_KMP(char*s,char*t,int pos){int i=pos,j=1;while(i<=(int)strlen(s)&&j<=(int)strlen(t)) {if(j==0||s[i]==t[j-1]){j++;}else j=next[j];}if(j>(int)strlen(t))return i-strlen(t)+1;elsereturn0;}void get_next(char*t,int*next) {int i=1,j=0;next[0]=next[1]=0;while(i<(int)strlen(t)){if(j==0||t[i]==t[j]){i++;j++;next[i]=j;}else j=next[j];}}int main(){int n;get_next(t,next);n=index_KMP(s,t,pos); printf("%d",n);return0;}并查集int father[maxn] = {0};int Rank[maxn] = {0};void make_set(int x){father[x] = x;Rank[x] = 0;}int find_set(int x){if(father[x] != x){father[x] = find_set(father[x]); }return father[x];}void union_set(int x, int y) {x = find_set(x);y = find_set(y);if(x == y) return;if(Rank[x] > Rank[y]){father[y] = x;}else{if(Rank[x] == Rank[y]){Rank[y]++;}father[x] = y;}}。

基本算法模板一、头文件#include<cstdio>#include<cstdlib> ///常用函数库，主要可以提供一些函数与符号常量。

#include<cstring>#include<iostream>#include<cmath>#include<list> ///STL链表#include<map> ///STL映射容器#include<queue> ///STL队列#include<stack> ///STL栈#include<vector> ///STL矢量容器#include <ctype.h>///字符处理#include <errno.h>///定义错误码#include <float.h>///浮点数处理#include <fstream>///文件输入／输出#include <iomanip>///参数化输入／输出#include <iostream> ///数据流输入／输出#include <limits.h> ///定义各种数据类型最值常量#include <locale.h> ///定义本地化函数#include <math.h> ///定义数学函数#include <stdio.h> ///定义输入／输出函数#include <stdlib.h> ///定义杂项函数及内存分配函数#include <string.h> ///字符串处理//#include <strstrea> //基于数组的输入／输出#include <time.h> ///定义关于时间的函数#include <wchar.h> ///宽字符处理及输入／输出#include <wctype.h> ///宽字符分类#include <algorithm> ///STL 通用算法#include <bitset> ///STL 位集容器#include <cctype> ///字符测试函数#include <cerrno>二、qsort 基本比较函数。

算法报告模板1. 简介本文是一份算法报告模板，适用于对算法进行深入研究和分析时的撰写。

报告主要包括算法的基本概念、算法流程、优缺点分析以及应用实例等方面。

我们以冒泡排序算法为例来进行详细讲解。

2. 算法介绍冒泡排序，也叫交换排序，是一种简单直观的排序算法。

它的核心思想是比较相邻的两个元素，将较大的元素交换到右边，较小的元素交换到左边，借此完成排序。

具体来说，它通过不断的交换相邻的元素，最终使数组中所有元素都按照从小到大的顺序排列。

3. 算法流程冒泡排序的算法流程如下：将要排序的数组arr视为由n个元素组成的数列1.从第一个元素开始对相邻的两个元素进行比较2.如果左侧元素大于右侧元素，则进行交换，将左侧元素移动到右侧3.对剩余元素重复以上两步，直到最后一对元素比较完成4.对于整个数据集，重复以上所有步骤，直到没有任何交换操作发生4. 优缺点分析4.1 优点1.对于小规模数据集排序效果较好2.冒泡排序的时间复杂度为O(n^2)，相较于其他排序算法，它具有代码实现简单的特点4.2 缺点1.冒泡排序的交换过程需要进行多次，因此在规模较大的数据集中，它的时间复杂度较高，性能不佳2.冒泡排序的稳定性较差，存在相邻元素相等时，可能会出现交换后顺序变化的情况。

5. 应用实例冒泡排序算法作为一种简单易懂的排序算法，广泛应用于各类编程语言和应用场景中，如：•数据库中的查询操作•线性数据结构如链表、队列和栈的排序•小规模数据集的排序6. 结论冒泡排序是一种简单而实用的排序算法，它具有易于实现、理解等优点，但在大规模数据集的排序中效率较低。

在使用冒泡排序来解决排序问题时，应根据实际情况选择是否使用改进的冒泡排序或者其他排序算法。

递归算法模板概述递归算法是一种解决问题的常见方法，它通过将问题分解成更小的子问题，并使用相同的算法来解决子问题，从而最终解决整个问题。

递归算法通常具有以下特点：一个基线情况（base case），它是一个可以被直接解决的问题。

一个递归步骤（recursive step），它将问题分解成更小的子问题，并使用相同的算法来解决子问题。

基本结构递归算法的基本结构如下：def recursive_function(problem):if problem is base_case:return solutionelse:subproblems = decompose_problem(problem)solutions = [recursive_function(subproblem) for subproblem in subproblems]return combine_solutions(solutions)recursive_function是递归函数，它接受一个问题作为参数，并返回一个解决方案。

base_case是基线情况，如果问题是基线情况，则直接返回解决方案。

decompose_problem将问题分解成更小的子问题。

recursive_function对每个子问题进行递归调用，并得到对应的解决方案。

combine_solutions将子问题的解决方案组合成整个问题的解决方案。

递归算法的优点和缺点递归算法的主要优点是：简洁性：递归算法通常比非递归算法更简洁，更容易理解和编写。

模块化：递归算法可以将问题分解成更小的子问题，并使用相同的算法来解决子问题，从而具有很强的模块化。

可重用性：递归算法可以很容易地被重用，以解决类似的问题。

递归算法的主要缺点是：效率低：递归算法通常比非递归算法效率更低，因为递归调用需要额外的空间和时间。

栈溢出：递归算法可能会导致栈溢出，特别是对于深度递归或递归次数过多的情况。

⼋种排序算法模板1 #include<iostream>2 #include<cstdlib>3 #include<ctime>4using namespace std;5const int len = 20;//待排序数组元素的个数，下标从1开始6//1、冒泡排序7void Bubble_sort(int s[],int len){8bool flag;9for(int i=1;i<len-1;++i){10 flag=false;11for(int j=1;j<=len-i;++j)12if(s[j]>s[j+1]){flag=true;swap(s[j],s[j+1]);}13if(!flag)break;14 }15 }16//2、选择排序17void Select_sort(int s[],int len){18int k;19for(int i=1;i<len;++i){20 k=i;21for(int j=i+1;j<=len;++j)22if(s[k]>s[j])k=j;23if(k!=i)swap(s[i],s[k]);24 }25 }26//3、插⼊排序27void Insert_sort(int s[],int len){28int tmp,j;29for(int i=2;i<=len;++i){30 tmp=s[i];31for(j=i-1;j>0&&tmp<s[j];--j);32for(int k=i;k>j+1;--k)s[k]=s[k-1];33 s[j+1]=tmp;34 }35 }36//4、快速排序37int Quick_sort(int s[],int low,int high){38int tmp=s[low];//⾸元素是枢轴39while(low<high){//待排序序列长度⼤于140while(low<high&&tmp<=s[high])--high;//⼤于枢轴的元素依旧在右边41 s[low]=s[high];//将⼩于枢轴的元素放左边42while(low<high&&tmp>=s[low])++low;//⼩于枢轴的元素依旧在左边43 s[high]=s[low];//将⼤于枢轴的元素放右边44 }45 s[low]=tmp;//枢轴记录到位46return low;//返回枢轴的位置，表⽰该位置已经排好序47 }48void Qsort(int s[],int low,int high){49if(low<high){50int key=Quick_sort(s,low,high); // 第key个元素已经排好序，继续两边搜索排序51 Qsort(s,low,key-1);52 Qsort(s,key+1,high);53 }54 }55//5、希尔排序(采⽤直接插⼊)56void Shell_sort(int s[],int len){57int tmp,j;58for(int step=len/2;step>0;step/=2){//设置步长59for(int i=step;i<=len;++i){60 tmp=s[i];61for(j=i-step;j>0&&tmp<s[j];j-=step);62for(int k=i;k>j+step;k-=step)s[k]=s[k-step];63 s[j+step]=tmp;64 }65 }66 }67//6、归并排序68void Merge(int s[],int t[],int low,int mid,int high){69int i=low,j=mid+1,k=low;70while(i<=mid&&j<=high){71if(s[i]<=s[j])t[k++]=s[i++];72else t[k++]=s[j++];73 }74while(i<=mid)t[k++]=s[i++];75while(j<=high)t[k++]=s[j++];76for(int i=low;i<=high;++i)s[i]=t[i];//将区间[low,high]拷贝到原来数组s对应的位置，表⽰该区间元素已排好序77 }78void Merge_sort(int s[],int t[],int low,int high){79if(low<high){80int mid=(low+high)/2;81 Merge_sort(s,t,low,mid);//递归分成左部分82 Merge_sort(s,t,mid+1,high);//递归分成右部分83 Merge(s,t,low,mid,high);//将两部分归并84 }85 }86//7、堆排序(⼤根堆实现升序排序)87void Heap_Adjust(int s[],int cur,int len){88int tmp=s[cur];//先取出当前元素cur89for(int j=2*cur;j<=len;j*=2){//向下筛选90if(j<len&&s[j]<s[j+1])++j;91if(tmp>=s[j])break;92 s[cur]=s[j];cur=j;//将⼦节点j值赋给⽗节点cur（不⽤进⾏交换）93 }94 s[cur]=tmp;95 }96void Heap_sort(int s[],int len){97//1、构建⼤根堆98for(int i=len/2;i>0;--i)Heap_Adjust(s,i,len);99//2.调整堆结构+交换堆顶元素与末尾元素100for(int i=len;i>1;--i){101 swap(s[i],s[1]);102 Heap_Adjust(s,1,i-1);//将[1,i-1]重新调整为⼤根堆103 }104 }105//8、基数排序106int Max_bit(int s[],int len){//获取数组中最⼤值的位数107int dit=1,p=10;108for(int i=1;i<=len;++i)109while(s[i]>=p){++dit;p*=10;}110return dit;111 }112void Radix_sort(int s[],int len){113int exp=1,dit=Max_bit(s,len),*cnt=new int[10],*tmp=new int[len+1]; 114for(int j=1;j<=dit;++j){115for(int i=0;i<10;++i)cnt[i]=0;116for(int i=1;i<=len;++i)cnt[s[i]/exp%10]++;117for(int i=1;i<10;++i)cnt[i]+=cnt[i-1];//叠加元素个数118for(int i=len;i>0;--i)tmp[cnt[s[i]/exp%10]--]=s[i];//将桶中元素倒出来119for(int i=1;i<=len;++i)s[i]=tmp[i];//将倒出来的元素依次放到原数组中去120 exp*=10;121 }122delete[]cnt;//释放内存123delete[]tmp;124 }125//打印数组元素值126void print(int s[],int len){127for(int i=1;i<=len;++i)128 cout<<s[i]<<(i==len?"\n":"");129 }130int main(){131int *s=new int[len+1];132int *t=new int[len+1];//t为辅助数组133 srand((unsigned)time(NULL));134for(int i=1;i<=len;++i)s[i]=rand();135 cout<<"排序前："<<endl;136 print(s,len);//打印原数组137/*1、冒泡排序138 Bubble_sort(s,len);*/139/*2、选择排序140 Select_sort(s,len);*/141/*3、插⼊排序142 Insert_sort(s,len);*/143/*4、快速排序144 Qsort(s,1,len);*/145/*5、希尔排序146 Shell_sort(s,len);*/147/*6、归并排序148 Merge_sort(s,t,1,len);*/149/*7、堆排序150 Heap_sort(s,len);*/151/*8、基数排序152 Radix_sort(s,len);153 cout<<"排序后："<<endl;*/154 print(s,len);//打印排序后的数组元素155156delete[]s;//释放内存157delete[]t;158return0;159 }。