so easy的模板，各位大佬忽略此博即可。

随意来吧，不按顺序了。（反正我也不知道什么顺序）

 

No.1 线性筛素数 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int n,m,x; 7 static bool notp[10000005]; 8  9 int main(){10     scanf("%d%d",&n,&m);11     for (int i=1; i<=n; i++) if ((i!=2) & ((i % 2)==0)) notp[i]=1;12     notp[1]=1;13     for (int i=2; i<=n; i++) {14         if ((!notp[i]) & (i % 2!=0)) {15             for (int j=2; j*i<=n; j++) notp[i*j]=1;            16         }17     }18     for (int i=1; i<=m; i++) {19         scanf("%d",&x);20         if (notp[x]) printf("No\n"); else printf("Yes\n");        21     }22     return 0;23 }
       
      
     

 

No.2 堆

 

1 var 2     i,n,opt,x,y,tot            :longint; 3     heap                    :array[0..1000050] of longint; 4      5 procedure swap(var x,y:longint); 6 var 7     t                        :longint; 8 begin 9     t:=x;10     x:=y;11     y:=t;12 end;13     14 procedure insert(x:longint);15 var16     i                        :longint;17 begin18     inc(tot);19     heap[tot]:=x;20     i:=tot;21     while (i>>1)>0 do22     begin23         if (heap[i>>1]<=heap[i]) then break;24         swap(heap[i],heap[i>>1]);25         i:=i>>1;26     end;27 end;28 29 procedure delete(x:longint);30 var31     i,j                        :longint;32 begin33     heap[x]:=heap[tot];34     dec(tot);35     i:=x;36     while (i<<1)<=tot do37     begin38         j:=i<<1;39         if (j+1<=tot) and (heap[j+1]

 

 

No.3 最小生成树

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 struct bian { 7     int x,y,a;     8 } e[200050]; 9 10 bool cmp(const bian p,const bian q){11     return p.a
       
      
     

 

No.4 并查集

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int n,m,x,y,z,father[10005]; 5  6 int gf(int x) { 7     if (father[x]==x) return(x); 8     father[x]=gf(father[x]); 9     return(father[x]);10 }11 12 int main(){13     scanf("%d%d",&n,&m);14     for (int i=1; i<=n; i++) father[i]=i;15     for (int i=1; i<=m; i++){16         scanf("%d%d%d",&z,&x,&y);17         if (z==1) {18             int fx=gf(x);19             int fy=gf(y);20             if (fx!=fy) father[fx]=fy;21         } else {22             int fx=gf(x);23             int fy=gf(y);24             if (fx==fy) printf("Y\n"); else printf("N\n");25         }26     }27     return 0;28 }
      
     

 

 

No.5 KMP

 

1 var 2     i,j,nn,p,n            :longint; 3     st,stt                :ansistring; 4     next                :array[0..1000010] of longint; 5 begin 6     readln(st); 7     readln(stt); 8     nn:=length(stt); 9     n:=length(st);10     p:=0;11     for i:=2 to nn do12     begin13         while (p<>0) and (stt[p+1]<>stt[i]) do p:=next[p];14         if stt[p+1]=stt[i] then15         begin16             inc(p);17             next[i]:=p;18         end else next[i]:=0;19     end;20     for i:=1 to n do21     begin22         while (p<>0) and (stt[p+1]<>st[i]) do p:=next[p];23         if stt[p+1]=st[i] then inc(p);24         if p=nn then25         begin26             writeln(i-nn+1);27             p:=next[p];28         end;29     end;30     for i:=1 to nn do write(next[i],' ');31 end.

 

 

No.6 倍增lca

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 #define maxn 1000050 6  7 int pre[maxn],last[maxn],other[maxn],d[500050],anc[500050][30]; 8 int l,root,n,m,x,y,z; 9 bool vis[500050]={
   0};10 11 void add(int u,int v) {12     pre[++l]=last[u];13     last[u]=l;14     other[l]=v;15 }16 17 void dfs(int x) {18     for (int p=last[x]; p ; p=pre[p]) {19         int q=other[p];20         if (vis[q]) continue;21         vis[q]=1;22         d[q]=d[x]+1;23         anc[q][0]=x;24         dfs(q);25     }26 }27 28 int lca(int u,int v) {29     if (d[u]
        
         =0; i--) if (d[anc[u][i]]>=d[v]) u=anc[u][i];31     if (u==v) return(u);32     for (int i=25; i>=0; i--) {33         if (anc[u][i]!=anc[v][i]) {34             u=anc[u][i];35             v=anc[v][i];36         }37     }38     return anc[u][0];39 }40 41 42 int main(){43     scanf("%d%d%d",&n,&m,&root);44     for (int i=1; i
        
       
      
     

 

 

No.7 矩阵乘法+快速幂

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int n; 7 long long k; 8 const int mod=1e9+7; 9 10 struct jz {11     long long v[105][105];12 }a,ans;13 14 jz mul(jz a,jz b) {15     jz c;16     for (int i=1; i<=n; i++)17         for (int j=1; j<=n; j++) c.v[i][j]=0;18     for (int i=1; i<=n; i++) 19         for (int j=1; j<=n; j++)20             for (int k=1; k<=n; k++)21                 c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j]) % mod;22     return (c);23 }24 25 jz pow(jz c,long long x) {26     if (x==1) return(c);27     c=pow(c,x>>1);28     if (x % 2==0) return(mul(c,c)); else return(mul(mul(c,c),a));29 }30 31 int main(){32     scanf("%d%lld",&n,&k);33     for (int i=1; i<=n; i++) 34         for (int j=1; j<=n; j++) scanf("%lld",&a.v[i][j]);35     ans=pow(a,k);36     for (int i=1; i<=n; i++) {37         for (int j=1; j<=n; j++) printf("%lld ",ans.v[i][j]);38         printf("\n");39     }40     return 0;41 }
       
      
     

 

No.8 字符串hash

1 const mo=10000009; 2 var 3     hash                    :Array[0..mo] of longint; 4     a                        :array[0..10050] of ansistring; 5     i,j,l,tot,n                 :longint; 6     st                        :ansistring; 7     p,seed                    :int64; 8     f                        :boolean; 9 10 begin11     readln(n);12     fillchar(hash,sizeof(hash),false);13     for i:=1 to n do14     begin15         readln(st);16         a[i]:=st;17         l:=length(st);18         p:=0;19         seed:=137;20         for j:=1 to l do p:=(p*134+ord(st[j])) mod mo;21         f:=true;22         while hash[p]<>0 do23         begin24             if a[hash[p]]=st then25             begin26                 f:=false;27                 break;28             end;29             p:=(p+72) mod mo;30         end;31         if not f then continue;32         inc(tot);33         hash[p]:=i;34     end;35     writeln(tot);36 end.

 

No.9 树状数组

1 var 2     n,m,i,j,x,y,opt                :longint; 3     s                            :array[0..500050] of longint; 4      5 function lowbit(t:longint):longint; 6 begin 7     exit(t and (-t)); 8 end; 9     10 procedure plus(t,x:longint);11 begin12     while t<=n do13     begin14         inc(s[t],x);15         t:=t+lowbit(t);16     end;17 end;18 19 function find(t:longint):longint;20 var21     sum                            :longint;22 begin23     sum:=0;24     while t>0 do25     begin26         inc(sum,s[t]);27         t:=t-lowbit(t);28     end;29     exit(sum);30 end;31 32 begin33     read(n,m);34     for i:=1 to n do35     begin36         read(x);37         plus(i,x);38     end;39     for i:=1 to m do40     begin41         read(opt,x,y);42         if opt=1 then plus(x,y) else writeln(find(y)-find(x-1));43     end;44 end.

 

No.10 线段树

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 struct tree{ 7     int l,r; 8     long long lazy,sum;     9 } t[300050];10 int n,m,opt,x,y,z;11 long long a[100050];12 13 14 void build(int x, int l, int r) {15     t[x].l=l; 16     t[x].r=r;17     if (l==r) {18         t[x].sum=a[l];19         return;20     }21     int mid=(l+r)>>1;22     build(x*2,l,mid);23     build(x*2+1,mid+1,r);24     t[x].sum=t[x*2].sum+t[x*2+1].sum;25 }26 27 void update(int x) {28     t[x].sum+=t[x].lazy*(t[x].r-t[x].l+1);29     if (t[x].l==t[x].r) {30         t[x].lazy=0;31         return;32     }33     t[x*2].lazy+=t[x].lazy;34     t[x*2+1].lazy+=t[x].lazy;35     t[x].lazy=0;36 }37 38 void change(int x, int l, int r, int y) {39     if ((t[x].l==l) && (t[x].r==r)) {40         t[x].lazy+=y;41         return;42     }43     if (t[x].lazy!=0) update(x);44     int mid=(t[x].l+t[x].r)>>1;45     if (l>mid) change(x*2+1,l,r,y); else46     if (r<=mid) change(x*2,l,r,y); else {47         change(x*2,l,mid,y);48         change(x*2+1,mid+1,r,y);49     }50     t[x].sum=t[x*2].sum+t[x*2].lazy*(t[x*2].r-t[2*x].l+1) 51                 +t[x*2+1].sum+t[x*2+1].lazy*(t[x*2+1].r-t[x*2+1].l+1);52 }53 54 long long find(int x, int l, int r) {55     if ((t[x].l==l) && (t[x].r==r)) return(t[x].sum+t[x].lazy*(t[x].r-t[x].l+1));56     if (t[x].lazy!=0) update(x);57     int mid=(t[x].l+t[x].r)>>1;58     if (l>mid) return(find(x*2+1,l,r)); else59     if (r<=mid) return(find(x*2,l,r)); else60         return(find(x*2,l,mid)+find(x*2+1,mid+1,r));61 }62 63 int main(){64     scanf("%d%d",&n,&m);65     for (int i=1; i<=n; i++) scanf("%lld",&a[i]);66     build(1,1,n);67     for (int i=1; i<=m; i++){68         scanf("%d",&opt);69         if (opt==1) {70             scanf("%d%d%d",&x,&y,&z);71             change(1,x,y,z);72         } else {73             scanf("%d%d",&x,&y);74             printf("%lld\n",find(1,x,y));75         }76     }77     return 0;78 }
       
      
     

 

No.11 平衡树(SBT)

1 var  2     left,right,size,key                :Array[0..100050] of longint;  3     i,n,t,tot,opt,x                    :longint;  4       5 procedure lrot(var t:longint);  6 var  7     k                                :longint;  8 begin  9     k:=right[t]; 10     right[t]:=left[k]; 11     left[k]:=t; 12     size[k]:=size[t]; 13     size[t]:=size[left[t]]+size[right[t]]+1; 14     t:=k; 15 end; 16  17 procedure rrot(var t:longint); 18 var 19     k                                :longint; 20 begin 21     k:=left[t]; 22     left[t]:=right[k]; 23     right[k]:=t; 24     size[k]:=size[t]; 25     size[t]:=size[left[t]]+size[right[t]]+1; 26     t:=k; 27 end; 28      29 procedure maintain(var t:longint; flag:boolean); 30 begin 31     if not flag then 32     begin 33         if size[left[left[t]]]>size[right[t]] then rrot(t) else 34         if size[right[left[t]]]>size[right[t]] then 35         begin 36             lrot(left[t]); 37             rrot(t); 38         end else exit; 39     end else 40     begin 41         if size[right[right[t]]]>size[left[t]] then lrot(t) else 42         if size[left[right[t]]]>size[left[t]] then 43         begin 44             rrot(right[t]); 45             lrot(t); 46         end else exit; 47     end; 48     maintain(left[t],false); 49     maintain(right[t],true); 50     maintain(t,true); 51     maintain(t,false); 52 end; 53      54 procedure insert(var t:longint; v:longint); 55 begin 56     if t=0 then  57     begin 58         inc(tot); 59         t:=tot; 60         left[t]:=0; 61         right[t]:=0; 62         size[t]:=1; 63         key[t]:=v; 64         exit; 65     end; 66     inc(size[t]); 67     if v
     
      =key[t]); 69 end; 70  71 function delete(var t:longint; v:longint):longint; 72 begin 73     dec(size[t]); 74     if (v=key[t]) or (v
      
       key[t]) and (right[t]=0) then 75     begin 76         delete:=key[t]; 77         if (left[t]=0) or (right[t]=0) then t:=left[t]+right[t] else key[t]:=delete(left[t],v+1); 78     end else 79         if (v
       
        =key[t] then exit(succ(right[t],v));108     succ:=succ(left[t],v);109     if succ=-1 then exit(key[t]);110 end;111     112 begin113     read(n);114     for i:=1 to n do115     begin116         read(opt,x);117         if (opt=1) then insert(t,x);118         if (opt=2) then x:=delete(t,x);119         if (opt=3) then writeln(rank(t,x));120         if (opt=4) then writeln(select(t,x));121         if (opt=5) then writeln(pred(t,x));122         if (opt=6) then writeln(succ(t,x));123     end;124 end.
       
      
     

 

No.12 网路最大流(dinic)

1 var 2     n,m,i,j,x,y,z,l,s,t                :longint; 3     ans                                :int64; 4     pre,last,other,len                :Array[0..205000] of longint; 5     d,que                            :Array[0..55000] of longint; 6      7 function min(x,y:longint):longint; 8 begin 9     if x
     
      0 do36         begin37             q:=other[p];38             if (len[p]>0) and (d[q]=0) then39             begin40                 inc(ta);41                 que[ta]:=q;42                 d[q]:=d[cur]+1;43                 if q=t then exit(true);44             end;45             p:=pre[p];46         end;47     end;48     exit(false);49 end;50 51 function dinic(x,flow:longint):longint;52 var53     p,q,rest,tt                        :longint;54 begin55     if x=t then exit(flow);56     rest:=flow;57     p:=last[x];58     while p<>0 do59     begin60         q:=other[p];61         if (len[p]>0) and (d[q]=d[x]+1) and (rest>0) then62         begin63             tt:=dinic(q,min(rest,len[p]));64             dec(rest,tt);65             dec(len[p],tt);66             inc(len[p xor 1],tt);67         end;68         p:=pre[p];69     end;70     exit(flow-rest);71 end;72     73 begin74     read(n,m,s,t);75     l:=1;76     for i:=1 to m do77     begin78         read(x,y,z);79         add(x,y,z);80         add(y,x,0);81     end;82     while bfs(s) do inc(ans,dinic(s,maxlongint>>1));83     writeln(ans);84 end.
     

 

No.13 单源最短路(spfa+dijkstra)

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int n,m,x,y,z,l,ss,d[10050],que[10050],pre[500050],last[500050],other[500050],len[500050]; 7 bool vi[10050]; 8  9 void add(int u,int v,int r) {10     l++;11     pre[l]=last[u];12     last[u]=l;13     other[l]=v;14     len[l]=r;    15 }16 17 void spfa() {18     for (int i=1; i<=n; i++) d[i]=2147483647;19     int h=0;20     int t=1; 21     que[1]=ss;22     d[ss]=0;23     while (h
        
         d[cur]+len[p]) {30                 d[q]=d[cur]+len[p];31                 if (!vi[q]) {32                     t++;33                     que[t]=q;34                     vi[q]=1;35                 }36             }37         }38     }39 }40 41 int main(){42     scanf("%d%d%d",&n,&m,&ss);43     for (int i=1; i<=m; i++) {44         scanf("%d%d%d",&x,&y,&z);45         add(x,y,z);46     }47     spfa();48     for (int i=1; i<=n; i++) printf("%d ",d[i]);49     return 0;50 }
        
       
      
     

1 var 2     n,m,i,j,s,x,y,z,l        :longint; 3     pre,other,dis            :Array[0..500050] of longint; 4     last,len                :array[0..500050] of longint; 5     flag                    :array[0..500050] of boolean; 6      7 procedure add(u,v,r:longint); 8 begin 9     inc(l);10     pre[l]:=last[u];11     last[u]:=l;12     other[l]:=v;13     len[l]:=r;14 end;15 16 procedure dijkstra;17 var18     i,j,cur,p,q                :longint;19 begin20     for i:=1 to n do21     begin22         cur:=0;23         for j:=1 to n do if (not flag[j]) and (dis[j]
     
      0 do27         begin28             q:=other[p];29             if (dis[q]>dis[cur]+len[p]) then dis[q]:=dis[cur]+len[p];30             p:=pre[p];31         end;32     end;33 end;34 35 begin36     read(n,m,s);37     for i:=1 to m do38     begin39         read(x,y,z);40         add(x,y,z);41     end;42     for i:=0 to n do43     begin44         dis[i]:=maxlongint>>1;45         flag[i]:=false;46     end;47     dis[s]:=0;48     dijkstra;49     for i:=1 to n do 50     begin51         if dis[i]=maxlongint>>1 then dis[i]:=maxlongint;52         write(dis[i],' ');53     end;54 end.
     

 

No.14 tarjan(noip2015信息传递)

1 var 2     n,i,j,x,l,ans,time,top        :longint; 3     pre,last,other                :Array[0..200050] of longint; 4     dfn,low,stack                :array[0..200050] of longint; 5     vis                            :Array[0..200050] of boolean; 6      7 function min(x,y:longint):longint; 8 begin 9     if x
     
      0 do32     begin33         q:=other[p];34         if (dfn[q]=0) then 35         begin36             tarjan(q);37             low[x]:=min(low[x],low[q]);38         end else 39         if (vis[q]) then low[x]:=min(low[x],dfn[q]);40         p:=pre[p];41     end;42     if dfn[x]=low[x] then43     begin44         sum:=0;45         repeat46             now:=stack[top];47             dec(top);48             vis[now]:=false;49             inc(sum);50         until (now=x);51         if sum<>1 then ans:=min(ans,sum);52     end;53 end;54     55     56 begin57     read(n);58     for i:=1 to n do59     begin60         read(x);61         add(i,x);62     end;63     ans:=maxlongint;64     for i:=1 to n do65     begin66         if (dfn[i]<>0) then continue;67         tarjan(i);68     end;69     writeln(ans);70 end.