C++博客-Knight

poj 3648 Wedding

KNIGHT — Sun, 07 Jun 2009 09:19:00 GMT

Wedding

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 821		Accepted: 249		Special Judge

Description

Up to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table. The bride and groom sit at one end, opposite each other, and the bride wears an elaborate headdress that keeps her from seeing people on the same side as her. It is considered bad luck to have a husband and wife seated on the same side of the table. Additionally, there are several pairs of people conducting adulterous relationships (both different-sex and same-sex relationships are possible), and it is bad luck for the bride to see both members of such a pair. Your job is to arrange people at the table so as to avoid any bad luck.

Input

The input consists of a number of test cases, followed by a line containing 0 0. Each test case gives n, the number of couples, followed by the number of adulterous pairs, followed by the pairs, in the form "4h 2w" (husband from couple 4, wife from couple 2), or "10w 4w", or "3h 1h". Couples are numbered from 0 to n - 1 with the bride and groom being 0w and 0h.

Output

For each case, output a single line containing a list of the people that should be seated on the same side as the bride. If there are several solutions, any one will do. If there is no solution, output a line containing "bad luck".

Sample Input

10 6
3h 7h
5w 3w
7h 6w
8w 3w
7h 3w
2w 5h
0 0

Sample Output

1h 2h 3w 4h 5h 6h 7h 8h 9h

Source

Waterloo Local Contest, 2007.9.29
。。。。。。。。。。。。。。。。。。。。
郁闷。。。。。。。。。。。。。。。。。。
搞的一下午。。。。。。。。。。。。。。。错了N次。。。。
题目很WS最后从读一遍。。。。。。。。。终于读懂。。。。。
饿死我了。。。。。。。。。。。。。。还不会构图。。。。。。
先吃饭，回来在搞。。。。。。。，今天就这5道题还困难了。。。郁闷。
--------------------------------------------------------------------------------------------------------------------------------------------------------------
2009.6.8 22:34
代码很丑不贴了，再有6分钟就熄灯了。。。。。躺下想了一会感觉一起思路是对的就是没有考虑0w-》0h的这条边。。。。
结果一改之。。。。。。。。。。AC

5281113

xujiaming

3648

Accepted

364K

0MS

C++

2635B

2009-06-08 22:33:58

2009-06-08 22:33:58 AC时间 AC完了之后说了两个字“我日”耗费了两秒钟。然后直接打开Blog。今晚终于搞出来了
感谢指出Bug的大牛。
啊，自习了、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

KNIGHT 2009-06-07 17:19 发表评论

poj 3678 Priest John's Busiest Day

KNIGHT — Sun, 07 Jun 2009 02:39:00 GMT

第一次考虑到输出路径点。。。。。
开始的时候本以为不用拓扑，而在见图的时候全部建成无向图。。。。结果不言而喻
部分代码如下：

#include<iostream>
#include<stack>
#include<vector>
#define MAXN 2100
using namespace std;
vector<int>v[MAXN],nv[MAXN],cont[MAXN];
int pre[MAXN],low[MAXN],id[MAXN];
int ans[MAXN],dfn[MAXN];
int cnt,scnt,n,m,N;
stack<int>ST;
struct NODE{
    int x,y;
}arr[MAXN];
void Tarjan(int x){
    int t,i;
    int min=low[x]=pre[x]=cnt++;
    ST.push(x);
    for(i=0;i<v[x].size();i++){
        t=v[x][i];
        if(pre[t]==-1)Tarjan(t);
        if(low[t]<min)min=low[t];
    }
    if(min<low[x]){
        low[x]=min;
        return;
    }
    do{
        id[t=ST.top()]=scnt;
        low[t]=m;ST.pop();
    }while(t!=x);
    scnt++;
}
int SCC(){
    scnt=cnt=0;
    while(!ST.empty())ST.pop();
    memset(pre,0xff,sizeof(pre));
    memset(low,0,sizeof(low));
    for(int i=0;i<m;i++)
        if(pre[i]==-1)Tarjan(i);
    for(int i=0;i<m;i++)
        cont[id[i]].push_back(i);
    return scnt;
}
void DFS(int k){
    dfn[k]=cnt++;
    for(int i=0;i<nv[k].size();i++){
        int w=nv[k][i];
        if(dfn[w]==-1)DFS(w);
    }
    ans[scnt++]=k;
}
void ColDFS(int k){
    dfn[k]=2;
    for(int i=0;i<nv[k].size();i++){
        int w=nv[k][i];
        if(dfn[w]==-1)ColDFS(w);
    }
}
void GetOneAnswer(){
    memset(dfn,0xff,sizeof(dfn));
    for(int i=0;i<m;i++)
        for(int j=0;j<v[i].size();j++){
            int x=id[i],y=id[v[i][j]];
            if(x!=y)nv[x].push_back(y);
        }
    cnt=scnt=0;
    for(int i=0;i<N;i++)
        if(dfn[i]==-1)DFS(i);
    memset(dfn,0xff,sizeof(dfn));
    for(int i=scnt-1;i>=0;i--)
        if(dfn[ans[i]]==-1) {
            int a=cont[ans[i]][0],b;
            if(a<n)b=a+n;
            else b=a-n;
            dfn[ans[i]]=1;
            if (dfn[id[b]]==-1)ColDFS(id[b]);
        }
}
void PRINTF(){
    printf("YES\n");
    GetOneAnswer();
    for(int i=0;i<n;i++){
        int x=arr[i].x,y=arr[i].y;
        int tx=arr[i+n].x,ty=arr[i+n].y;
        if(dfn[id[i]]==2)printf("%02d:%02d %02d:%02d\n",x/60,x%60,y/60,y%60);
        else printf("%02d:%02d %02d:%02d\n",tx/60,tx%60,ty/60,ty%60);
    }
}
void solve(){
    int i=0;
    for(N=SCC();i<n;i++)
        if(id[i]==id[n+i])break;
    if(i==n)PRINTF();
    else printf("NO\n");
}

KNIGHT 2009-06-07 10:39 发表评论

poj 3207 Ikki's Story IV - Panda's Trick

KNIGHT — Sat, 06 Jun 2009 12:12:00 GMT

Faint.开始的时候理解错题目意思。。。。晕。。。。。Wa了一次
结果从读之后又因为界限Wa了一次。。。。晕
47ms比较慢，可能是使用了STL的vector和stack的原因吧
部分代码如下

#include<iostream>
#include<stack>
#include<vector>
#define MAXN 1200
using namespace std;
int pre[MAXN],low[MAXN],id[MAXN];
int cnt,scnt,n,N,M;
vector<int>v[MAXN];
stack<int>ST;
struct NODE{
    int x,y;
}arr[MAXN];
void Tarjan(int x){
    int t,i;
    int min=low[x]=pre[x]=cnt++;
    ST.push(x);
    for(i=0;i<v[x].size();i++){
        t=v[x][i];
        if(pre[t]==-1)Tarjan(t);
        if(low[t]<min)min=low[t];
    }
    if(min<low[x]){
        low[x]=min;
        return;
    }
    do{
        id[t=ST.top()]=scnt;
        low[t]=n;ST.pop();
    }while(t!=x);
    scnt++;
}
int SCC(){
    scnt=cnt=0;
    memset(pre,0xff,sizeof(pre));
    memset(low,0,sizeof(low));
    for(int i=0;i<n;i++)
        if(pre[i]==-1)Tarjan(i);
    return scnt;
}

KNIGHT 2009-06-06 20:12 发表评论

浅谈2—SAT问题

KNIGHT — Sat, 06 Jun 2009 07:00:00 GMT

2-SAT：

1 2 - SAT就是2判定性问题，是一种特殊的逻辑判定问题。
2 2 - SAT问题有何特殊性？该如何求解？
3 我们从一道例题来认识2 - SAT问题，并提出对一类2 - SAT问题通用的解法。
4

Poi 0106 Peaceful Commission [和平委员会]：

某国有n个党派，每个党派在议会中恰有2个代表。
现在要成立和平委员会，该会满足：
每个党派在和平委员会中有且只有一个代表
如果某两个代表不和，则他们不能都属于委员会
代表的编号从1到2n，编号为2a - 1 、2a的代表属于第a个党派

输入n（党派数），m（不友好对数）及m对两两不和的代表编号
其中1≤n≤ 8000 ， 0 ≤m ≤ 20000

求和平委员会是否能创立。若能，求一种构成方式。
输入：     输出：
3 2         1
1 3         4
2 4         5

原题可描述为：

有n个组，第i个组里有两个节点Ai, Ai ' 。需要从每个组中选出一个。而某些点不可以同时选出（称之为不相容）。任务是保证选出的n个点都能两两相容。

（在这里把Ai, Ai ' 的定义稍稍放宽一些，它们同时表示属于同一个组的两个节点。也就是说，如果我们描述Ai，那么描述这个组的另一个节点就可以用Ai ' ）

初步构图
如果Ai与Aj不相容，那么如果选择了Ai，必须选择Aj‘ ；同样，如果选择了Aj，就必须选择Ai’ 。
Ai Aj '
Aj Ai‘
这样的两条边对称

我们从一个例子来看：
假设4个组，不和的代表为：1和4，2和3，7和3，那么构图：
假设：首先选1 3必须选，2不可选 8必须选， 4 、7不可选 5 、6可以任选一个

矛盾的情况为：
存在Ai，使得Ai既必须被选又不可选。

得到算法1：
枚举每一对尚未确定的Ai, Ai‘ ，任选1个，推导出相关的组，若不矛盾，则可选择；否则选另1个，同样推导。若矛盾，问题必定无解。
此算法正确性简要说明：
由于Ai,Ai ' 都是尚未确定的，它们不与之前的组相关联，前面的选择不会影响Ai, Ai ' 。

算法的时间复杂度在最坏的情况下为O(nm)。
在这个算法中，并没有很好的利用图中边的对称性

更一般的说：
在每个一个环里，任意一个点的选择代表将要选择此环里的每一个点。不妨把环收缩成一个子节点（规定这样的环是极大强连通子图）。新节点的选择表示选择这个节点所对应的环中的每一个节点.
对于原图中的每条边Ai -> Aj（设Ai属于环Si，Aj属于环Sj）如果Si≠Sj，则在新图中连边:Si -> Sj

这样构造出一个新的有向无环图。
此图与原图等价。

通过求强连通分量，可以把图转换成新的有向无环图，在这个基础上，介绍一个新的算法。

新算法中，如果存在一对Ai, Ai ' 属于同一个环，则判无解，否则将采用拓扑排序，以自底向上的顺序进行推导，一定能找到可行解。

至于这个算法的得来及正确性，将在下一段文字中进行详细分析。

回忆构图的过程：
对于两个不相容的点 Ai, Aj，构图方式为：Ai -> Aj ' ,Aj->Ai ' ,前面提到过，这样的两条边对称，也就是说：
如果存在Ai -> Aj，必定存在Aj ' ->Ai ' 。

等价于：Ai -> Ak,Ak ' ->Ai ' 方便起见，之后“ -> ”代表这样一种传递关系.

猜测1：图中的环分别对称
如果存在Ai,Aj，Ai,Aj属于同一个环(记作Si),那么Ai ' , Aj ' 也必定属于一个环(记作Si ' ).
再根据前面的引理，不难推断出每个环分别对称。

证明方式与引理相类似
一个稍稍复杂点的结构,其中红、蓝色部分分别为两组对称的链结构
推广2：对于任意一对Si, Si ' ，Si的后代节点与Si ' 的前代节点相互对称。
继而提出:
猜测2：若问题无解，则必然存在Ai, Ai ' ，使得Ai,Ai ' 属于同一个环。也就是，如果每一对Ai,Ai ' 都不属于同一个环，问题必定有解。下面给出简略证明：

先提出一个跟算法1相似的步骤：
如果选择Si，那么对于所有Si -> Sj，Sj都必须被选择。
而Si ' 必定不可选，这样Si’的所有前代节点也必定不可选（将这一过程称之为删除）。
由推广2可以得到，这样的删除不会导致矛盾。

假设选择S3 '
选择S3 ' 的后代节点, S1 '
删除S3
删除S3的前代节点S1
S1与S1 ' 是对称的

每次找到一个未被确定的Si，使得不存在Si -> Si ' 选择Si及其后代节点而删除Si’及Si‘的前代节点。一定可以构造出一组可行解。
因此猜测2成立。

另外，若每次盲目的去找一个未被确定的Si，时间复杂度相当高。
以自底向上的顺序进行选择、删除，这样还可以免去“选择Si的后代节点”这一步。
用拓扑排序实现自底向上的顺序。

一组可能的拓扑序列(自底向上）:S1 ' ,S2,S2 ' ,S3 ' ,S3,S1

算法2的流程：

1 ．构图
2 ．求图的极大强连通子图
3 ．把每个子图收缩成单个节点，根据原图关系构造一个有向无环图
4 ．判断是否有解，无解则输出（退出）
5 ．对新图进行拓扑排序
6 ．自底向上进行选择、删除
7 ．输出

小结：
整个算法的时间复杂度大概是O(m)，解决此问题可以说是相当有效了。
在整个算法的构造、证明中反复提到了一个词：对称。发现、利用了这个图的特殊性质，我们才能够很好的解决问题。
并且，由2 - SAT问题模型变换出的类似的题目都可以用上述方法解决。

全文总结：
充分挖掘图的性质，能够更好的解决问题。
不仅仅是对于图论，这种思想可以在很多问题中得到很好的应用。
希望我们能掌握此种解题的思想，在熟练基础算法的同时深入分析、灵活运用、大胆创新，从而解决更多更新的难题。

KNIGHT 2009-06-06 15:00 发表评论

决定考研。。。

KNIGHT — Sun, 31 May 2009 13:44:00 GMT

开始习惯自习室生活。尽量少Coding。
从此一节课不逃。。。。。周六，周日去573.或者看资料。。。
Bless pip!

KNIGHT 2009-05-31 21:44 发表评论

写点头文件之类

KNIGHT — Fri, 29 May 2009 14:14:00 GMT

也做个小小的应用，做TC的时候省了许多代码时间

#define MFW() freopen("MyData.out","w",stdout);
#define FW() freopen("Data.out","w",stdout);
#define FR() freopen("Data.in","r",stdin);
#define FOR(s,i,t) for(i=s;i<=t;i++)
#define FUCK puts("Fuck You!");
#define PAUSE system("pause");
#define getmax(x,y) x>y?x:y;
#define getmin(x,y) x
#define Abs(x) x>0?x?-x;
#define OK puts("OK!");
#define INF 0x7fffffff
#define MIO FR()FW()
#define IO FR()FW()
#define MAXN 1200
#define EPS 1E-8
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
int main(){
IO OK
}

KNIGHT 2009-05-29 22:14 发表评论

[ZZ]后缀数组

KNIGHT — Thu, 28 May 2009 11:53:00 GMT

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法，以及配合后缀数组的最长公共前缀数组的构造方法，最后结合一些例子谈谈后缀数组的应用。

基本概念

首先明确一些必要的定义：

字符集一个字符集∑是一个建立了全序关系的集合，也就是说，∑中的任意两个不同的元素α和β都可以比较大小，要么α<β，要么β<α（也就是α>β）。字符集∑中的元素称为字符。
字符串一个字符串S是将n个字符顺次排列形成的数组，n称为S的长度，表示为len(S)。S的第i个字符表示为S[i]。
子串字符串S的子串S[i..j]，i≤j，表示S串中从i到j这一段，也就是顺次排列S[i],S[i+1],...,S[j]形成的字符串。
后缀后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。

关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u[i]和v[i]，如果相等则令i加1，否则若u[i]v[i]则认为u>v（也就是vlen (u)或者i>len(v)仍未比较出结果，那么若len(u)len(v)则u>v。
从字符串的大小比较的定义来看，S的两个开头位置不同的后缀u和v进行比较的结果不可能是相等，因为u=v的必要条件len(u)=len(v)在这里不可能满足。

下面我们约定一个字符集∑和一个字符串S，设len(S)=n，且S[n]='$'，也就是说S以一个特殊字符'$'结尾，并且'$'小于∑中的任何一个字符。除了S[n]之外，S中的其他字符都属于∑。对于约定的字符串S，从位置i开头的后缀直接写成Suffix(i)，省去参数S。

后缀数组后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1],SA[2],...SA[n]，并且保证 Suffix(SA[i])名次数组名次数组Rank=SA-1，也就是说若SA[i]=j，则Rank[j]=i，不难看出Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。

构造方法
如何构造后缀数组呢？最直接最简单的方法当然是把S的后缀都看作一些普通的字符串，按照一般字符串排序的方法对它们从小到大进行排序。
不难看出，这种做法是很笨拙的，因为它没有利用到各个后缀之间的有机联系，所以它的效率不可能很高。即使采用字符串排序中比较高效的Multi-key Quick Sort，最坏情况的时间复杂度仍然是O(n2)的，不能满足我们的需要。
下面介绍倍增算法(Doubling Algorithm)，它正是充分利用了各个后缀之间的联系，将构造后缀数组的最坏时间复杂度成功降至O(nlogn)。

对一个字符串u，我们定义u的k-前缀

定义k-前缀比较关系设两个字符串u和v，
uu=kv 当且仅当 uk=vk
u≤kv 当且仅当 uk≤vk

直观地看这些加了一个下标k的比较符号的意义就是对两个字符串的前k个字符进行字典序比较，特别的一点就是在作大于和小于的比较时如果某个字符串的长度不到k也没有关系，只要能够在k个字符比较结束之前得到第一个字符串大于或者小于第二个字符串就可以了。
根据前缀比较符的性质我们可以得到以下的非常重要的性质：
性质1.1 对k≥n，Suffix(i)性质1.2 Suffix(i)=2kSuffix(j)等价于
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性质1.3 Suffix(i)<2kSuffix(j) 等价于
Suffix(i)这里有一个问题，当i+k>n或者j+k>n的时候Suffix(i+k)或Suffix(j+k)是无明确定义的表达式，但实际上不需要考虑这个问题，因为此时Suffix(i)或者Suffix(j)的长度不超过k，也就是说它们的k-前缀以'$'结尾，于是k-前缀比较的结果不可能相等，也就是说前k个字符已经能够比出大小，后面的表达式自然可以忽略，这也就看出我们规定S以'$'结尾的特殊用处了。

定义k-后缀数组 SAk保存1..n的某个排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk[i]) ≤kSuffix(SAk[i+1]),1≤i定义k-名次数组Rankk，Rankk[i]代表Suffix(i)在k-前缀关系下从小到大的“名次”，也就是1加上满足Suffix(j)假设我们已经求出了SAk和Rankk，那么我们可以很方便地求出SA2k和Rank2k，因为根据性质1.2和1.3，2k-前缀比较关系可以由常数个k -前缀比较关系组合起来等价地表达，而Rankk数组实际上给出了在常数时间内进行Suffix(i)Suffix(i)=kSuffix(j) 当且仅当 Rankk[i]=Rankk[j]
因此，比较Suffix(i)和Suffix(j)在k-前缀比较关系下的大小可以在常数时间内完成，于是对所有的后缀在≤k关系下进行排序也就和一般的排序没有什么区别了，它实际上就相当于每个Suffix(i)有一个主关键字Rankk[i]和一个次关键字Rankk[i+k]。如果采用快速排序之类O (nlogn)的排序，那么从SAk和Rankk构造出SA2k的复杂度就是O(nlogn)。更聪明的方法是采用基数排序，复杂度为O(n)。
求出SA2k之后就可以在O(n)的时间内根据SA2k构造出Rank2k。因此，从SAk和Rankk推出SA2k和Rank2k可以在O(n)时间内完成。
下面只有一个问题需要解决：如何构造出SA1和Rank1。这个问题非常简单：因为<1，=1和≤1这些运算符实际上就是对字符串的第一个字符进行比较，所以只要把每个后缀按照它的第一个字符进行排序就可以求出SA1，不妨就采用快速排序，复杂度为O(nlogn)。
于是，可以在O(nlogn)的时间内求出SA1和Rank1。
求出了SA1和Rank1，我们可以在O(n)的时间内求出SA2和Rank2，同样，我们可以再用O(n)的时间求出SA4和Rank4，这样，我们依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中m=2k且m≥n。而根据性质1.1，SAm和SA是等价的。这样一共需要进行logn次O(n)的过程，因此
可以在O(nlogn)的时间内计算出后缀数组SA和名次数组Rank。

最长公共前缀
现在一个字符串S的后缀数组SA可以在O(nlogn)的时间内计算出来。利用SA我们已经可以做很多事情，比如在O(mlogn)的时间内进行模式匹配，其中m,n分别为模式串和待匹配串的长度。但是要想更充分地发挥后缀数组的威力，我们还需要计算一个辅助的工具——最长公共前缀（Longest Common Prefix）。
对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv}，也就是从头开始顺次比较u和v的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。
对正整数i,j定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j均为1至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。
关于LCP有两个显而易见的性质：
性质2.1 LCP(i,j)=LCP(j,i)
性质2.2 LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1
这两个性质的用处在于，我们计算LCP(i,j)时只需要考虑ij时可交换i,j，i=j时可以直接输出结果n-SA[i]+1。

直接根据定义，用顺次比较对应字符的方法来计算LCP(i,j)显然是很低效的，时间复杂度为O(n)，所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。
经过仔细分析，我们发现LCP函数有一个非常好的性质：
设i
要证明LCP Theorem，首先证明LCP Lemma:
对任意1≤i证明：设p=min{LCP(i,j),LCP(j,k)}，则有LCP(i,j)≥p,LCP(j,k)≥p。
设Suffix(SA[i])=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
由u=LCP(i,j)v得u=pv；同理v=pw。
于是Suffix(SA[i])=pSuffix(SA[k])，即LCP(i,k)≥p。 (1)

又设LCP(i,k)=q>p，则
u[1]=w[1],u[2]=w[2],...u[q]=w[q]。
而min{LCP(i,j),LCP(j,k)}=p说明u[p+1]≠v[p+1]或v[p+1]≠w[q+1]，
设u[p+1]=x,v[p+1]=y,w[p+1]=z，显然有x≤y≤z，又由p于是，q>p不成立，即LCP(i,k)≤p。 (2)
综合(1),(2)知 LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}，LCP Lemma得证。

于是LCP Theorem可以证明如下：
当j-i=1和j-i=2时，显然成立。
设j-i=m时LCP Theorem成立，当j-i=m+1时，
由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)}，
因j-(i+1)≤m，LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j}，故当j-i=m+1时，仍有
LCP(i,j)=min{LCP(i,i+1),min{LCP(k-1,k)|i+2≤k≤j}}=min{LCP(k-1,k}|i+1≤k≤j)
根据数学归纳法，LCP Theorem成立。

根据LCP Theorem得出必然的一个推论：
LCP Corollary 对i≤j
定义一维数组height，令height[i]=LCP(i-1,i)，1由LCP Theorem，LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是说，计算LCP(i,j)等同于询问一维数组height中下标在i+1到j范围内的所有元素的最小值。如果height数组是固定的，这就是非常经典的RMQ（Range Minimum Query）问题。
RMQ问题可以用线段树或静态排序树在O(nlogn)时间内进行预处理，之后每次询问花费时间O(logn)，更好的方法是RMQ标准算法，可以在O(n)时间内进行预处理，每次询问可以在常数时间内完成。
对于一个固定的字符串S，其height数组显然是固定的，只要我们能高效地求出height数组，那么运用RMQ方法进行预处理之后，每次计算LCP(i,j)的时间复杂度就是常数级了。于是只有一个问题——如何尽量高效地算出height数组。
根据计算后缀数组的经验，我们不应该把n个后缀看作互不相关的普通字符串，而应该尽量利用它们之间的联系，下面证明一个非常有用的性质：
为了描述方便，设h[i]=height[Rank[i]]，即height[i]=h[SA[i]]。h数组满足一个性质：
性质3 对于i>1且Rank[i]>1，一定有h[i]≥h[i-1]-1。
为了证明性质3，我们有必要明确两个事实：

设i1，则成立以下两点：
Fact 1 Suffix(i)Fact 2 一定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起来很神奇，但其实很自然：lcp(Suffix(i),Suffix(j))>1说明Suffix(i)和Suffix(j)的第一个字符是相同的，设它为α，则Suffix(i)相当于α后连接Suffix(i+1)，Suffix(j)相当于α后连接Suffix(j+1)。比较Suffix (i)和Suffix(j)时，第一个字符α是一定相等的，于是后面就等价于比较Suffix(i)和Suffix(j)，因此Fact 1成立。Fact 2可类似证明。

于是可以证明性质3：
当h[i-1]≤1时，结论显然成立，因h[i]≥0≥h[i-1]-1。
当h[i-1]>1时，也即height[Rank[i-1]]>1，可见Rank[i-1]>1，因height[1]=0。
令j=i-1,k=SA[Rank[j]-1]。显然有Suffix(k)根据h[i-1]=lcp(Suffix(k),Suffix(j))>1和Suffix(k)由Fact 2知lcp(Suffix(k+1),Suffix(i))=h[i-1]-1。
由Fact 1知Rank[k+1]于是根据LCP Corollary，有
LCP(Rank[i]-1,Rank[i])≥LCP(Rank[k+1],Rank[i])
=lcp(Suffix(k+1),Suffix(i))
=h[i-1]-1
由于h[i]=height[Rank[i]]=LCP(Rank[i]-1,Rank[i])，最终得到 h[i]≥h[i-1]-1。

根据性质3，可以令i从1循环到n按照如下方法依次算出h[i]：
若Rank[i]=1，则h[i]=0。字符比较次数为0。
若i=1或者h[i-1]≤1，则直接将Suffix(i)和Suffix(Rank[i]-1)从第一个字符开始依次比较直到有字符不相同，由此计算出h[i]。字符比较次数为h[i]+1，不超过h[i]-h[i-1]+2。
否则，说明i>1，Rank[i]>1，h[i-1]>1，根据性质3，Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1个字符是相同的，于是字符比较可以从h[i-1]开始，直到某个字符不相同，由此计算出h[i]。字符比较次数为h[i]-h[i- 1]+2。

设SA[1]=p，那么不难看出总的字符比较次数不超过

也就是说，整个算法的复杂度为O(n)。
求出了h数组，根据关系式height[i]=h[SA[i]]可以在O(n)时间内求出height数组，于是
可以在O(n)时间内求出height数组。

结合RMQ方法，在O(n)时间和空间进行预处理之后就能做到在常数时间内计算出对任意(i,j)计算出LCP(i,j)。
因为lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])，所以我们也就可以在常数时间内求出S的任何两个后缀之间的最长公共前缀。这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。
后缀数组的应用
下面结合两个例子谈谈如何运用后缀数组.

例一多模式串的模式匹配问题
给定一个固定待匹配串S,长度为n,然后每次输入一个模式串P,长度为m,要求返回P在S中的一个匹配或者返回匹配失败.所谓匹配指某个位置i满足1≤i≤n-m+1使得S[i..(i+m-1)]=P,也即Suffix(i)=mP.
我们知道,如果只有一个模式串,最好的算法就是KMP算法,时间复杂度为O(n+m),但是如果有多个模式串,我们就要考虑做适当的预处理使得对每个模式串进行匹配所花的时间小一些.最简单的预处理莫过于建立S的后缀数组(先在S的后面添加'$'),然后每次寻找匹配转化为用二分查找法在SA中找到和P的公共前缀最长的一个后缀,判断这个最长的公共前缀是否等于m.这样,每次比较P和一个后缀的复杂度为O(m),因为最坏情况下可能比较了m个字符.二分查找需要调用比较的次数为O(logn),因此总复杂度为O(mlogn),于是每次匹配的复杂度从O(n+m)变为O(mlogn),可以说改进了不少.可是这样仍然不能令我们满足.前面提到LCP可以增加后缀数组的威力,

我们来试试用在这个问题上.
我们分析原始的二分查找算法,大体有以下几步:
Step 1 令left=1,right=n,max_match=0.
Step 2 令mid=(left+right)/2(这里"/"表示取整除法).
Step 3 顺次比较Suffix(SA[mid])和P的对应字符,找到两者的最长公共
前缀r,并判断出它们的大小关系.若r>max_match则令max_match=r,ans=mid.
Step 4 若Suffix(SA[mid])P则令
right=mid-1,若Suffix(SA[mid])=P则转至Step 6.
Step 5 若left
Step 6 若max_match=m则输出ans,否则输出"无匹配".
注意力很快集中在Step 3,如果能够避免每次都从头开始比较Suffix(SA[mid])和P的对应字符,也许复杂度就可以进一步降低.类似于前面求height数组,我们考虑利用以前求得的最长公共前缀作为比较的"基础",避免冗余的字符比较.

在比较Suffix(SA[mid])和P之前,我们先用常数时间计算LCP(mid,ans),然后比较LCP(mid,ans)和max_match:情况一:LCP(mid,ans)k+1,T[i-r'..i-1]和T[i+1..i+r']也不可能关于T[i]对称了,所以r最大只能到k.我们把r递增的过程称为向两边扩展,扩展一次就可以把以T[i]为中心的奇回文子串的长度加2.最后r扩展到的最大值决定了以T[i]为中心的奇回文子串中的最长者的长度(为2r+1).设len(T)=m,如果用依次比较对应字符的方法来求向两边扩展的最大值,则最多可能比较m-1个字符.由于要枚举每个位置作为中心向两边扩展,所以最坏情况下总的复杂度可以达到O(m2),不很理想.
下面优化算法的核心部分
——以一个位置为中心求向两边扩展的最大值.
在T串的末尾添加一个特殊字符'#',规定它不等于T的任何一个字符,然后把T串颠倒,接在'#'后,在T'串后再添加特殊字符'$',规定它小于前面的任何一个字符,拼接后形成的串称为S串.不难看出T串中任何一个字符都可在T'中对称地找到一个相同的字符.如果都用S里的字符来表示,S[1..m]是T串,S[m+2..2m+1]是T'串,则每个S[i](1≤i≤m)关于'#'对称的字符是S[2m-i+2].这样原先T串里面的一个子串S[i..j](1≤i≤j≤m)关于'#'也可以对称地找到一个反射相等的子串S[2m-j+2..2m-i+2].
现在我们定下T串的某个位置S[i]为中心,假设向两边扩展到了i-r和i+r,那么S[i-r..i-1]和S[i+1..i+r]是反射相等的,S[i]可以在T'中找到对称的字符S[2m-i+2],设i'=2m-i+2,则S[i-r..i-1]也可以在T'中找到对称的子串S[i'+1..i'+r],
banana#ananab$
TT'
ii'=2m-i+2
那么S[i+1..i+r]和S[i'+1..i'+r]同时与S[i-r..i-1]反射相等,也就是说,S[i+1..i+r]=S[i'+1..i'+r].又因为S[i]=S[i'],故S[i..i+r]=S[i'..i'+r].也就是说,Suffix(i)=r+1Suffix(i').现在要求r尽量大,也就是求max{r|Suffix(i)=r+1Suffix(i')},不难看出,这里r=LCP(i,i')-1.上面的推理还存在一个问题,即求出的LCP(i,i')-1还只能看作r的一个上界,还不能当成r的最大值,因为还需要证明给出Suffix(i)和Suffix(i')的最长公共前缀,一定可以反过来在T串中找到相应的以i为中心的回文串,这个证明与前面的推理类似,只是需要注意一点:这里利用到了'#'这个特殊字符避免了潜在的LCP(i,i')超过实际的r最大值的危险.这个证明留给读者自行完成.总之,我们已经确定求以T[i]为中心向两边扩展的最大值等价于求LCP(i,i'),根据前面后缀数组和LCP的相关内容这一步操作可以在常数时间内完成,只要我们预先花费O(nlogn)的复杂度计算后缀数组,height数组和进行预处理.其中n=len(S)=2m+2.
现在每次求以一个位置T[i]为中心的回文子串中的最长者的长度可以在常数时间内完成,我们枚举i从1到m,依次求出所有的这些最长者,记录其中最大的一个的长度,就是所要求的最长奇回文子串的长度.由于对每个中心花费时间为常数,所以总的复杂度为O(m).因此整个算法的复杂度是O(nlogn+m)=O(2mlog(2m)+m)=O(mlogm),是非常优秀的算法,比之前的平方级算法大为改进.

后缀数组与后缀树的比较
通过上面的两个例子相信读者已经对后缀数组的强大功能有所了解,另一种数据结构——后缀树,也可以用在这些问题中,那么后缀数组和后缀树有什么区别和联系呢我们来比较一下:
首先,后缀数组比较容易理解,也易于编程实现,而且不像后缀树那样需要涉及到指针操作,所以调试起来比较方便.第二,后缀数组占用的空间比后缀树要小,刚才分析中我们并没有提到空间复杂度的问题,这里简单说一下:后缀数组SA和名词数组Rank都只需要n个整数的空间,而在由Rankk计算出SA2k的过程中需要用两个一维数组来辅助完成,各占n个整数的空间,滚动地进行操作,整个算法只需要这四个一维数组和常数个辅助变量,因此总的空间占用为4n个整数.而后缀树通常有2n个以上节点,通常每个节点要两个整数(即使采用一些技巧,至少还是要保存一个整数),每个节点要有两个指针(假设采用儿子-兄弟表示方法),因此总共的空间占用至少是4n个指针和2n个整数(至少是n个整数).如果采用其他方法表示树状结构,需要的空间更大.可以看出后缀数组的空间需求比后缀树小.
最后比较它们的复杂度:
首先按照字符总数|∑|把字符集∑分为三种类型:
若|∑|是一个常数,则称∑为Constant Alphabet,
若|∑|的大小是关于S的长度n的多项式函数,则称∑为Integer Alphabet,
若|∑|没有大小上的限制,则称∑为General Alphabet.

显然Constant Alphbet属于Integer Alphabet的一种,而Integer Alphabet是General Alphabet的一种.构造后缀数组的复杂度与字符集无关,因为它是直接针对General Alphabet的算法.对于普通方法构造后缀树,如果用儿子-兄弟方式表达树状结构,时间复杂度达到O(n*|∑|),显然对于Integer Alphabet 和 General Alphabet都很低效,对|∑|较大的Constant Alphabet也不适用.解决的方法是用平衡二叉树来保存指向儿子的指针,这样复杂度变为O(n*log|∑|).可见后缀树在某些情况下相对后缀数组有速度上的优势,但是并不明显.对于|∑|很小的字符串,后缀树相比后缀数组的速度优势还是比较可观的.尤其是对于很常见的0-1串.
后缀数组实际上可以看作后缀树的所有叶结点按照从左到右的次序排列放入数组中形成的,所以后缀数组的用途不可能超出后缀树的范围.甚至可以说,如果不配合LCP,后缀数组的应用范围是很狭窄的.但是LCP函数配合下的后缀数组就非常强大,可以完成大多数后缀树所能完成的任务,因为LCP函数实际上给出了任意两个叶子结点的最近公共祖先,这方面的内容大家可以自行研
究.后缀树和后缀数组都是字符串处理中非常优秀的数据结构,不能说一个肯定优于另一个,对于不同场合,不同条件的问题,我们应该灵活应用,精心选择地选择其中较为适合的一个.算法和数据结构都是死的,而运用它们的人,才是真正的主角,对经典的算法和数据结构熟练掌握并适当地运用以发挥它们最大的力量,这才是信息学研究和竞赛中最大的智慧,也是信息学竞赛的魅力
所在.

KNIGHT 2009-05-28 19:53 发表评论

刚做的TC

KNIGHT — Wed, 27 May 2009 16:25:00 GMT

开始的时候因为人多为患导致TC卡了一段时间。。。。第3次做可以说是第一次正式做
延时15分钟本来本子就没有电。。。。。现在还没比完就剩1000分的本子搞不住了。。写下日志就差不多over了
有点困。。。。。1000分题目都没心情看了 250的题晕了浪费了很多时间。。。。。500的倒是很快推出来了可惜少想了一种情况从新提交了一次。。。。。晕
睡觉了。。。。rating也没性情看了正式的第一次TC差不多能够绿了吧。。。。应该能够。。。
睡觉了

KNIGHT 2009-05-28 00:25 发表评论

省赛告一段落

KNIGHT — Tue, 26 May 2009 08:33:00 GMT

继续在北大刷题。。。
备战四省赛。。。一切都没有变。。。
就如xiaoz所说：AC才是王道。
just do it。no matter what happen。Go。！

KNIGHT 2009-05-26 16:33 发表评论

后天省赛了

KNIGHT — Fri, 22 May 2009 14:00:00 GMT

上午的时候打印了一些模板。。。。主要是一些类似大整数运算的常用算法，
由于昨天睡得晚了些今天早上6点就起来打扫寝室，说什么防止猪流感做寝室检查，中午想回宿舍睡一觉也没睡，就在实验室WS，
晚上的时候从头翻QQ日志，感觉有点悲伤的气氛就翻了一篇删一篇，结果194篇删完。。。从此在这个Blog写东西省赛做完之后尽快达到600，封号！之后完美的做TC。
后天省赛了，或者说要被工大的众神牛虐了，在这里Bless Every Hrbeu‘s Acmers取得好成绩！

KNIGHT 2009-05-22 22:00 发表评论