OI算法复习

搜集一些算法，赛前背一背有好处的

转自各大网站

前排感谢：hzwer、风了咕凉

前辈。。。Orz

快速读入：

1 int read()
2 {
3     int x=0,f=1;char ch=getchar();
4     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
5     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
6     return x*f;
7 }

经典快排：虽说C++直接sort就好了。。。

 1 #include <iostream>
 2  
 3 using namespace std;
 4  
 5 void Qsort(int a[], int low, int high)
 6 {
 7     if(low >= high)
 8         return;
 9     int first = low;
10     int last = high;
11     int key = a[first];
12     while(first < last)
13     {
14         while(first < last && a[last] >= key)
15             --last;
16         a[first] = a[last];
17         while(first < last && a[first] <= key)
18             ++first;
19          a[last] = a[first];
20     }
21     a[first] = key;
22     Qsort(a, low, first-1);
23     Qsort(a, first+1, high);
24 }

归并排序：

 1 template <typename T>
 2 void MergeSort (T data[], int size)
 3 {
 4     if ( size>1 )
 5     {
 6         //预处理
 7         int mid=size/2;
 8         int numOfleft=mid;
 9         int numOfright=size-mid;
10         T* left=new T[numOfleft];
11         T* right=new T[numOfright];
12         //分
13         std::copy(data, data+numOfleft, left);
14         std::copy(data+numOfleft, data+size, right);
15         MergeSort(left, numOfleft);
16         MergeSort(right, numOfright);
17         //合
18         std::merge(left, left+numOfleft, right, right+numOfright, data);
19         //清理
20         delete[] left;
21         delete[] right;
22     }
23 }

堆排：

 1 template <typename T>
 2 void heap_down (T data[], int i, const int& size)
 3 {
 4     int p=i*2+1;
 5     while ( p<size )
 6     {
 7         if ( p+1<size )
 8         {
 9             if ( data[p]<data[p+1] )
10                 ++p;
11         }
12         if ( data[i]<data[p] )
13         {
14             std::swap(data[p], data[i]);
15             i=p;
16             p=i*2+1;
17         }
18         else
19             break;
20     }
21 }

 1 template <typename T>
 2 void HeapSort (T data[], int size)
 3 {
 4     int i;
 5     for (i=(size-1)/2; i>=0; --i)
 6         heap_down(data, i, size);
 7     for (i=size-1; i>0; --i)
 8     {
 9         std::swap(data[0], data[i]);
10         heap_down(data, 0, i);
11     }
12 }

拓扑排序：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 struct Edge
 6 {
 7     int to,next;
 8 }E[100001];
 9 int head[100001],r[100001],s[100001];
10 int node=0;
11 
12 int n;
13 
14 void insert(int u,int v)
15 {
16     E[++node]=(Edge){v,head[u]};
17     head[u]=node;
18     r[v]++;
19 }
20 
21 void topsort()
22 {
23     int t=1,top=0;
24     for(int i=1;i<=n;i++)
25         if(!r[i])
26         {
27             s[++top]=i;
28         }
29     while(t<=top)
30     {
31         int x=s[t++];
32         for(int i=head[x];i;i=E[i].next)
33         {
34             r[E[i].to]--;
35             if(!r[E[i].to])
36             {
37                 s[++top]=E[i].to;
38             }
39         }
40     }
41 }

kahn算法（NOIP2013车站分级为例子）纯过程形式：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int MAXN=1000+10;
 6 int n,m,ans=0;
 7 int B[MAXN]={0},R[MAXN]={0},SK[MAXN]={0};//R储存入度  SK储存入度为0的点
 8 bool A[MAXN]={0},F[MAXN]={0},E[MAXN][MAXN]={0};//F判断点是否已被访问  E判断两点是否存在边
 9 
10 int main()
11 {
12     /*cin>>n>>m;
13     for(int i=1;i<=m;i++)
14     {
15         int s;
16         memset(A,0,sizeof(A));
17         cin>>s;
18         for(int j=1;j<=s;j++)
19         {
20             cin>>B[j];
21             A[B[j]]=1;
22         }
23         for(int j=B[1];j<=B[s];j++)
24             if(!A[j])
25                 for(int k=1;k<=s;k++)
26                     if(!E[j][B[k]])
27                     {
28                         E[j][B[k]]=1;
29                         R[B[k]]++;
30                     }
31     }*///初始化
32     int top;
33     while(1)
34     {
35         top=0;
36         for(int i=1;i<=n;i++)//遍历n个点
37             if(!R[i]&&!F[i])//如果入度为0且没有被访问过，则加入SK数组
38             {
39                 SK[++top]=i;//加入SK数组
40                 F[i]=1;//i点已被访问
41             }
42         if(top==0)break;//如果所有的点都被访问则跳出
43         for(int i=1;i<=top;i++)
44             for(int j=1;j<=n;j++)
45                 if(E[SK[i]][j])//判断是否有边
46                 {
47                     E[SK[i]][j]=0;//将边移除
48                     R[j]--;//入度-1
49                 }
50         ans++;
51     }
52     cout<<ans<<endl;
53     return 0;
54 }

并查集：

1 int find(int x)
2 {
3     while(f[x]!=0) x=f[x];
4     return x;
5 }

快速幂：

 1 int modexp(int a,int b,int n)   
 2 {   
 3     int ret=1;   
 4     int tmp=a;   
 5     while(b)   
 6     {
 7        if(b&0x1) ret=ret*tmp%n;   
 8        tmp=tmp*tmp%n;   
 9        b>>=1;   
10     }   
11     return ret;   
12 }

欧几里得算法：

1 int gcd(int a,int b)
2 {
3     return b?gcd(b,a%b):a;
4 }

拓展欧几里德算法：

1 int gcd(int a,int b,int &x,int &y){
2     if (b==0){
3         x=1,y=0;
4         return a;
5     }
6     int q=gcd(b,a%b,y,x);
7     y-=a/b*x;
8     return q;
9 }

spfa：

 1 struct Edge
 2 {
 3     int to,w,next;
 4 }E[1000];
 5 int node=0,head[50];
 6 
 7 void insert(int u,int v,int w)
 8 {
 9     node++;
10     E[node]=Edge{v,w,head[u]};
11     head[u]=node;
12 }
13 
14 int spfa(int s,int t)
15 {
16     int dist[21];
17     bool vis[21];
18     memset(dist,0x7f,sizeof(dist));
19     memset(vis,0,sizeof(vis));
20     dist[s]=0;vis[s]=1;
21     queue<int> Q;
22     Q.push(s);
23     while(!Q.empty())
24     {
25         int q=Q.front();Q.pop();
26         for(int i=head[q];i;i=E[i].next)
27             if(dist[E[i].to]>dist[q]+E[i].w)
28             {
29                 dist[E[i].to]=dist[q]+E[i].w;
30                 if(!vis[E[i].to])
31                 {
32                     Q.push(E[i].to);
33                     vis[E[i].to]=1;
34                 }
35             }
36         vis[q]=0;
37     }
38     return dist[t];
39 }

spfa_dfs判负环：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 struct Edge
 6 {
 7     int to,w,next;
 8 }E[10000001];
 9 int node=0,head[10001],dist[10001];
10 bool vis[10001];
11 
12 int n,m;
13 bool flag;
14 
15 void insert(int u,int v,int w)
16 {
17     E[++node]=(Edge){v,w,head[u]};
18     head[u]=node;
19 }
20 
21 void spfa_dfs(int s)
22 {
23     vis[s]=1;
24     for(int i=head[s];i;i=E[i].next)
25     {
26         if(dist[E[i].to]>dist[s]+E[i].w)
27         {
28             if(vis[E[i].to]){flag=1;return;}
29             else
30             {
31                 dist[E[i].to]=dist[s]+E[i].w;
32                 spfa_dfs(E[i].to);
33             }
34         }
35     }
36     vis[s]=0;
37 }
38 
39 bool check()
40 {
41     flag=0;
42     memset(dist,0x7f,sizeof(dist));
43     memset(vis,0,sizeof(vis));
44     for(int i=1;i<=n;i++)
45     {
46         dist[i]=0;
47         spfa_dfs(i);
48         if(flag) return 1;
49     }
50     return 0;
51 }

floyd:

 1 const int maxn=105,
 2           INF=10000000;
 3 int n,Dist[maxn][maxn],Graph[maxn][maxn];
 4 int minn=INF;
 5 void floyd()
 6 {
 7     //memcpy(Graph,Dist,sizeof(Dist));
 8     for(int k=1;k<=n;k++)
 9     {/*拓展求最小环
10         for(int i=1;i<k;i++)
11             for(int j=i+1;j<k;j++)
12                 minn=min(minn,Dist[i][j]+Graph[j][k]+Graph[k][i]);*/
13         for(int i=1;i<=n;i++)
14             for(int j=1;j<=n;j++)
15             {
16                 int temp=Dist[i][k]+Dist[k][j];
17                 if(temp<Dist[i][j])
18                     Dist[i][j]=Dist[j][i]=temp;
19             }
20     }
21 }

Dijkstra:

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 #define MAXN 10000000
 6 
 7 int n,e;
 8 int matrix[100][100];
 9 int dist[100];
10 
11 void Dijkstra(int s)
12 {
13     int u,minn;
14     bool vis[100];
15     memset(vis,0,sizeof(vis));
16     for(int i=0;i<n;i++)
17         if(matrix[s][i]>0)
18             dist[i]=matrix[s][i];
19         else dist[i]=MAXN;
20     vis[s]=1;dist[s]=0;
21     for(int i=1;i<n;i++)
22     {
23         minn=MAXN;
24         for(int j=0;j<n;j++)
25             if(!vis[j]&&dist[j]<minn)
26             {
27                 u=j;
28                 minn=dist[j];
29             }
30         vis[u]=1;
31         for(int j=0;j<n;j++)
32             if(!vis[j]&&matrix[u][j]>0&&minn+matrix[u][j]<dist[j])
33                 dist[j]=minn+matrix[u][j];
34     }
35 }
36 
37 int main()
38 {
39     int v;
40     cin>>n;
41     cin>>e;
42     memset(matrix,0,sizeof(matrix));
43     for(int i=0;i<e;i++)
44     {
45         int x,y,w;
46         cin>>x>>y>>w;
47         matrix[x][y]=w;
48     }
49     Dijkstra(0);
50     cin>>v;
51     cout<<dist[v];
52     return 0;
53 }

线段树：详见Codevs1082线段树练习3

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     int left,right,flag;
 9     long long sum;
10 }tree[600000];
11 
12 int n,q;
13 int a[200001];
14 
15 void build(int node,int left,int right)
16 {
17     tree[node].left=left;tree[node].right=right;
18     if(left==right)
19     {
20         tree[node].sum=a[left];
21         return;
22     }
23     int mid=(left+right)>>1;
24     build(node<<1,left,mid);
25     build(node<<1|1,mid+1,right);
26     tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
27 }
28 
29 void pushdown(int node)
30 {
31     int x=tree[node].right-tree[node].left+1;
32     tree[node<<1].flag+=tree[node].flag;
33     tree[node<<1|1].flag+=tree[node].flag;
34     tree[node<<1].sum+=(x-(x>>1))*tree[node].flag;
35     tree[node<<1|1].sum+=(x>>1)*tree[node].flag;
36     tree[node].flag=0;
37 }
38 
39 void update(int node,int left,int right,int x)
40 {
41     int mid=(tree[node].left+tree[node].right)>>1;
42     tree[node].sum+=(right-left+1)*x;
43     if(tree[node].left==left&&tree[node].right==right)
44     {
45         tree[node].flag+=x;
46         return;
47     }
48     if(tree[node].left==tree[node].right) return;
49     if(tree[node].flag>0) pushdown(node);
50     if(right<=mid) update(node<<1,left,right,x);
51     else if(left>mid) update(node<<1|1,left,right,x);
52     else
53     {
54         update(node<<1,left,mid,x);
55         update(node<<1|1,mid+1,right,x);
56     }
57     tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
58 }
59 
60 long long query(int node,int left,int right)
61 {
62     int mid=(tree[node].left+tree[node].right)>>1;
63     if(tree[node].left==left&&tree[node].right==right)
64         return tree[node].sum;
65     if(tree[node].flag>0) pushdown(node);
66     if(right<=mid)
67         return     query(node<<1,left,right);
68     else if(left>mid)
69         return query(node<<1|1,left,right);
70     else
71         return query(node<<1,left,mid)+query(node<<1|1,mid+1,right);
72 }

树状数组：

详见

Codevs1080 线段树练习

Codevs1081 线段树练习 2

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 int f[100001];
 8 
 9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 
14 void update(int x,int num)
15 {
16     while(x<=n)
17     {
18         f[x]+=num;
19         x+=lowbit(x);
20     }
21 }
22 
23 int sum(int x)
24 {
25     int sum=0;
26     while(x>0)
27     {
28         sum+=f[x];
29         x-=lowbit(x);
30     }
31     return sum;
32 }
33 
34 int main()
35 {
36     n=read();
37     for(int i=1;i<=n;i++)
38         update(i,read());
39     m=read();
40     for(int i=1;i<=m;i++)
41     {
42         int a=read(),x=read(),y=read();
43         if(a==1)update(x,y);
44         if(a==2)printf("%d
",sum(y)-sum(x-1));
45     }
46     return 0;
47 }

分块法：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int n,m,q,block;
 8 int a[1000001],b[1000001],pos[1000001],add[1000001];
 9 
10 void reset(int x)
11 {
12     int l=(x-1)*block+1,r=min(x*block,n);
13     for(int i=l;i<=r;i++)
14         b[i]=a[i];
15     sort(b+l,b+r+1);//对单个块内进行排序
16 }
17 
18 int find(int x,int z)//单个块内二分查找
19 {
20     int l=(x-1)*block+1,r=min(x*block,n);
21     int last=r;
22     while(l<=r)
23     {
24         int mid=(l+r)>>1;
25         if(b[mid]<z) l=mid+1;
26         else r=mid-1;
27     }
28     return last-l+1;
29 }
30 
31 void update(int x,int y,int z)
32 {
33     if(pos[x]==pos[y])//同个块则暴力修改
34         for(int i=x;i<=y;i++) a[i]=a[i]+z;
35     else//不同块修改左右两边的块
36     {
37         for(int i=x;i<=pos[x]*block;i++) a[i]=a[i]+z;
38         for(int i=(pos[y]-1)*block+1;i<=y;i++) a[i]=a[i]+z;
39     }
40     reset(pos[x]);reset(pos[y]);
41     for(int i=pos[x]+1;i<pos[y];i++)//其余块用add标记，表示增加了z
42         add[i]+=z;
43 }
44 
45 int query(int x,int y,int z)
46 {
47     int sum=0;
48     if(pos[x]==pos[y])//单个块暴力查找
49     {
50         for(int i=x;i<=y;i++)
51             if(a[i]+add[pos[i]]>=z) sum++;
52     }
53     else//多个块左右两边的块暴力查找
54     {
55         for(int i=x;i<=pos[x]*block;i++)
56             if(a[i]+add[pos[i]]>=z) sum++;
57         for(int i=(pos[y]-1)*block+1;i<=y;i++)
58             if(a[i]+add[pos[i]]>=z) sum++;
59     }
60     for(int i=pos[x]+1;i<pos[y];i++)//其余块每个二分查找
61         sum+=find(i,z-add[i]);
62     return sum;
63 }
64 
65 int main()
66 {
67     scanf("%d %d",&n,&q);
68     block=(int)sqrt(n);//每个块的大小
69     for(int i=1;i<=n;i++)
70     {
71         scanf("%d",&a[i]);
72         pos[i]=(i-1)/block+1;
73         b[i]=a[i];
74     }
75     if(n%block) m=n/block+1;//计算块的个数，如有多余则+1
76     else m=n/block;
77     for(int i=1;i<=m;i++) reset(i);//对每个块进行块内排序
78     for(int i=1;i<=q;i++)
79     {
80         char ch;int x,y,z;
81         scanf("
%c %d %d %d",&ch,&x,&y,&z);
82         if(ch=='M') update(x,y,z);
83         else printf("%d
",query(x,y,z));
84     }
85     return 0;
86 }

倍增算法：

RMQ：这里借鉴了一下黄学长的模板。。。Orz膜拜前辈

 1 #include<iostream>
 2 #include<cmath>
 3 #include<iostream>
 4 using namespace std;
 5 int A[200001];
 6 int MX[200001][18];
 7 int n,q;
 8 void RMP_INIT()
 9 {
10     for(int i=1;i<=n;i++)
11         MX[i][0]=A[i];
12     int m=log(n)/log(2);
13     for(int i=1;i<=m;i++)
14         for(int j=n;j>0;j--)
15         {
16              MX[j][i]=MX[j][i-1];
17             if(j+(1<<(i-1))<=n)MX[j][i]=max(MX[j][i],MX[j+(1<<(i-1))][i-1]); 
18         }
19  }
20 int RMP(int l,int r)
21 {
22     int m=log(r-l+1)/log(2);
23     return max(MX[l][m],MX[r-(1<<m)+1][m]);
24 }

KMP算法：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 char S[255],T[255];
 6 int ls,lt;
 7 int next[255];
 8 
 9 void initnext(char *t,int *next)
10 {
11     int j=0;
12     int len=strlen(t);
13     memset(next,0,sizeof(next));
14     for(int i=1;i<len;i++)
15     {
16         while(j&&t[i]!=t[j]) j=next[j];
17         if(t[i]==t[j]) j++;
18         next[i+1]=j;
19     }
20 }
21 
22 int KMP(char *s,char *t)
23 {
24     int j=0,ans=0;
25     int ls=strlen(s),lt=strlen(t);
26     for(int i=0;i<ls;i++)
27     {
28         while(j&&s[i]!=t[j]) j=next[j];
29         if(s[i]==t[j]) j++;
30         if(j==lt)
31         {
32             ans++;
33             j=next[j];
34         }
35     }
36     return ans;
37 }

高斯消元：感谢浙大学长。。。Orz

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 
 5 #define eps 1e-9
 6 const int MAXN=220;
 7 double a[MAXN][MAXN],x[MAXN]; //方程的左边的矩阵和等式右边的值，求解之后 x存的就是结果  
 8 int equ,var;//方程数和未知数个数
 9  /* *返回0表示无解，1表示有解*/ 
10 int Gauss()
11 {
12     int i,j,k,col,max_r;
13     for(k=0,col=0;k<equ&&col<var;k++,col++)
14     {
15         max_r=k;
16         for(i=k+1;i<equ;i++)
17             if(fabs(a[i][col])>fabs(a[max_r][col])) max_r=i;
18         if(fabs(a[max_r][col])<eps) return 0;
19         if(k!=max_r)
20         {
21             for(j=col;j<var;j++) swap(a[k][j],a[max_r][j]);
22             swap(x[k],x[max_r]);
23         }
24         x[k]/=a[k][col];
25         for(j=col+1;j<var;j++) a[k][j]/=a[k][col];
26         a[k][col]=1;
27         for(i=0;i<equ;i++)
28             if(i!=k)
29             {
30                 x[i]-=x[k]*a[i][k];
31                 for(j=col+1;j<var;j++) a[i][j]-=a[k][j]*a[i][col];
32                 a[i][col]=0;
33             }
34     }
35     return 1;
36 }

分解质因数：感谢浙大学长。。。Orz

 1 long long fac[100],fac_num;
 2 void getfactor(int num)
 3 {
 4     fac_num=0; 
 5     for(int i=2;i*i<=num;i++)
 6     {
 7         if(num%i==0)
 8         {
 9              fac[fac_num++]=i;
10              while(num%i==0) num/=i; 
11          }
12      }
13      if(num>1) fac[fac_num++]=num;
14  }

欧拉函数：

 1 /*1.欧拉函数是积性函数,但不是完全积性函数,即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立. 
 2 2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.
 3     φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).
 4 3.除了N=2,φ(N)都是偶数.
 5 4.设N为正整数,∑φ(d)=N (d|N).  求小于等于N的与N互质的数的和 ：ans=N*phi(N)/2;*/
 6 /* 欧拉phi(x)函数等于不超过x且和x互素的整数个数。 */ 
 7 #include<iostream>
 8 #include<cstring>
 9 #include<algorithm>
10 using namespace std;
11 
12 const int MAXN=1000;
13 int phi[MAXN]; /* 单个欧拉函数值*/  
14 int euler_phi(int n)
15 {
16     int m=sqrt(n+0.5),ans=n;
17     for(int i=2;i<=m;i++)
18     {
19         if(n%i==0) ans=ans/i*(i-1);
20         while(n%i==0)n/=i;
21     }
22     if(n>1) ans=ans/n*(n-1);
23     return ans;
24 } 
25 /*欧拉函数 表*/  
26 void phi_table(int n)
27 {
28     memset(phi,0,sizeof(phi));
29     phi[1]=1;
30     for(int i=2;i<=n;i++)
31         if(!phi[i])
32             for(int j=i;j<=n;j+=i)
33             {
34                 if(!phi[j])phi[j]=j;
35                 phi[j]=phi[j]/i*(i-1);
36             }
37 }

埃氏筛法：O（nlog(logn)）

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int MAXN=1000;
 6 int isprime[MAXN];
 7 void getprime(int n)
 8 {
 9     memset(isprime,1,sizeof(isprime));
10     isprime[0]=isprime[1]=0;
11     for(int  i=0;i*i<n;i++)
12         if(isprime[i])
13             for(int j=i*i;j<=n;j+=i)
14                 isprime[j]=0;
15 }

欧拉筛法：

 1 const int MAXN=1000;
 2 int cnt=0;
 3 int prime[MAXN];
 4 bool mark[MAXN];
 5 void Prime(int x)
 6 {
 7     for(int i=2;i<=x;i++)
 8     {
 9         if(!mark[i]) prime[++cnt]=i;
10         for(int j=1;j<=cnt&&prime[j]*i<=x;j++)
11         {
12             mark[prime[j]*i]=1;
13             if(i%prime[j]==0) break;
14         }
15     }
16 }

后缀数组：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int MAXN=100000+5;
 6 int WA[MAXN],WB[MAXN],WV[MAXN],WS[MAXN];
 7 int Rank[MAXN],Height[MAXN];
 8  
 9 int cmp(int *r , int a, int b, int l)
10 {
11     return r[a] == r[b] && r[a+l] == r[b+l];
12 }
13 void DA(char *r , int *sa , int n, int m)
14 {
15     int i, j, p, *x = WA, *y = WB;
16     for(i = 0; i < m; i++)  WS[i] = 0;
17     for(i = 0; i < n; i++) WS[x[i] = r[i]]++;
18     for(i = 1; i < m; i++) WS[i] += WS[i-1];
19     for(i = n-1; i >= 0; i--) sa[--WS[x[i]]] = i;
20 
21     for(j = 1,p = 1; p < n ; j <<= 1,m = p)
22     {
23         for(p = 0, i = n - j; i < n; i++) y[p++]=i;
24         for(i = 0; i < n; i++)
25             if(sa[i] >= j)
26                 y[p++] = sa[i] - j;
27         for(i = 0; i < n; i++) WV[i] = x[y[i]];
28         for(i = 0; i < m; i++) WS[i] = 0;
29         for(i = 0; i < n; i++) WS[WV[i]]++;
30         for(i = 1; i < m; i++) WS[i] += WS[i-1];
31         for(i = n-1; i >= 0; i--) sa[--WS[WV[i]]] = y[i];
32         for(swap(x,y),p = 1,x[sa[0]] = 0,i = 1; i < n;i++)
33             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
34     }
35 }
36 
37 void calheight(char *r,int *sa,int n)
38 {
39     int i,j,k=0;
40     for(i=1;i<=n;i++)Rank[sa[i]]=i;
41     for(i=0;i<n;Height[Rank[i++]]=k)
42         for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
43     return;
44 }
45 
46 char str[MAXN];
47 int sa[MAXN];
48 
49 int main()
50 {
51     cin>>str;
52     int n=strlen(str);
53     str[n]=0;
54     DA(str,sa,n+1,128);
55     calheight(str,sa,n);
56 
57     return 0;
58 }

最大子串：

1 int maxSubstr() {
2     int sum = 0, answer = -INF;
3     for (int i = 1; i <= n; i++) {
4         sum += a[i];
5         answer = max(answer, sum);
6         sum = max(sum,0);
7     }
8     return answer;
9 }

SG函数：（转自SimonS大佬征战亚洲赛时用的模板

 1 #define MAX 1005  
 2 /* 计算从1-n范围内的SG值。     
 3 Array(存储可以走的步数，Array[0]表示可以有多少种走法)     
 4 Array[]需要从小到大排序 */ 
 5 /*HDU1847博弈SG函数  
 6 1.可选步数为1-m的连续整数，直接取模即可，SG(x) = x % (m+1);  
 7 2.可选步数为任意步，SG(x) = x;  
 8 3.可选步数为一系列不连续的数，用GetSG(计算) */   
 9 
10 int SG[MAX], hash[MAX];  
11 void GetSG(int Array[], int n = MAX-1) 
12 {
13     memset(SG, 0, sizeof(SG));
14     for(int i = 0; i <= n; ++i)
15     {
16         memset(hash, 0, sizeof(hash));
17         for(int j = 1; j <= Array[0]; ++j) 
18         {
19             if(i < Array[j]) break;
20             hash[SG[i - Array[j]]] = 1;      
21         }
22         for(int j = 0; j <= n; ++j)
23             if(!hash[j]){ SG[i] = j;break; }
24     }
25 }

先占坑，慢慢填