狠狠色丁香婷婷综合,国内久久婷婷综合,国产精品视频

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
。。。。。。。。。。。。。。。。。。。�?br />郁闷。。。。。。。。。。。。。。。。。�?br />搞的一下午。。。。。。。。。。。。。。。错了N�ơ。。。�?br />题目很WS最后从��M��遍。。。。。。。。。终于读懂。。。。�?br />饿死我了。。。。。。。。。。。。。。还不会构图。。。。。�?br />先吃饭，回来在搞。。。。。。。，今天��p��5道题�q�困难了。。。郁闗��?br />--------------------------------------------------------------------------------------------------------------------------------------------------------------
2009.6.8 22:34
代码很丑不脓了，再有6分钟��q��灯了。。。。。�h下想了一会感觉一��h��\是对的就是没有考虑0w-�?h的这条边。。。�?br />�l�果一改之。。。。。。。。。。AC

5281113

xujiaming

3648

Accepted

364K

0MS

C++

2635B

2009-06-08 22:33:58

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

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

poj 3678 Priest John's Busiest Day

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

�W�一�ơ考虑到输��\径点。。。。�?br />开始的时候本以�ؓ不用拓扑�Q�而在见图的时候全部徏成无向图。。。。结果不�a�而喻
部分代码如下�Q?br />

#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了一��?br />�l�果从读之后又因为界限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�Q?/strong>

1 2 - SAT��是2判定性问题，是一�U�特�D�的逻辑判定问题�?br /> 2 2 - SAT问题有何�Ҏ��性？该如何求解？
3 我们从一道例题来认识2 - SAT问题�Q��ƈ提出对一�c? - SAT问题通用的解法�?br /> 4

Poi 0106 Peaceful Commission [和��^委员会]�Q?br />
某国有n个党�z�，每个党派在议会中恰有2个代表�?br />现在要成立和�q�_��员会 �Q�该会满��I��
每个党派在和�q�_��员会中有且只有一个代表�?br />如果某两个代表不和，则他们不能都属于委员会�?br />代表的编号从1�?n�Q�编号�ؓ2a - 1 �?a的代表属于第a个党�z?br />

输入n�Q�党�z�数�Q�，m�Q�不友好�Ҏ��Q�及m对两两不和的代表�~�号
其中1≤n�?/span> 8000 �Q?/span> 0 ≤m �?/span> 20000

求和�q�_��员会是否能创立。若能，求一�U�构成方式。�?br />输入�Q�     输出：
3 2         1
1 3         4
2 4         5

原题可描�q�Cؓ�Q?br />
有n个组�Q�第i个组里有两个节点Ai, Ai ' 。需要从每个�l�中选出一个。而某些点不可以同旉��出�Q�称之�ؓ不相容）。�Q务是保证选出的n个点都能两两相容�?/span>

�Q�在�q�里把Ai, Ai ' 的定义稍�E�放宽一些，它们同时表示属于同一个组的两个节炏V��也��是��_��如果我们描述Ai�Q�那么描�q�这个组的另一个节点就可以用Ai ' �Q?br />

初步构图
如果Ai与Aj不相容，那么如果选择了Ai�Q�必��选择Aj‘ ；同样�Q�如果选择了Aj�Q�就必须选择Ai’ �?br />   Ai             Aj '
   Aj             Ai‘                       �?br />�q�样的两条边对称

我们从一个例子来看：
假设4个组�Q�不和的代表为：1�?�Q?�?�Q?�?�Q�那么构图：
假设�Q�首先�? 3必须选，2不可选�?必须选， 4 �?不可选�?/span> 5 �?可以任选一�?br />

矛盾的情况�ؓ�Q?br />存在Ai�Q��得Ai既必��被选又不可选�?br />
得到��法1�Q?br />枚�D每一对尚未确定的Ai, Ai‘ ，任�?个，推导出相关的�l�，若不矛盾�Q�则可选择�Q�否则选另1个，同样推导。若矛盾�Q�问题必定无解�?br />此算法正��性简要说明：
�׃��Ai,Ai ' 都是��未��定的，它们不与之前的组相关联，前面的选择不会影响Ai, Ai ' �?br />
��法的时间复杂度在最坏的情况下�ؓO(nm)�?br />在这个算法中�Q��ƈ没有很好的利用图中边的对�U��?br />

更一般的��_��
在每个一个环里，��L��一个点的选择代表��要选择此环里的每一个点。不妨把环收�~�成一个子节点�Q�规定这��L��环是极大��通子图）。新节点的选择表示选择�q�个节点所对应的环中的每一个节�?
对于原图中的每条边Ai -> Aj�Q�设Ai属于环Si�Q�Aj属于环Sj�Q�如果Si≠Sj�Q�则在新图中�q�边:Si -> Sj

�q�样构造出一个新的有向无环图�?br />此图与原囄��仗��?br />

通过求强�q�通分量，可以把图转换成新的有向无环图�Q�在�q�个基础上，介绍一个新的算法�?br />
新算法中�Q�如果存在一对Ai, Ai ' 属于同一个环�Q�则判无解，否则��采用拓扑排序，以自底向上的��序�q�行推导�Q�一定能扑ֈ�可行解�?/span>

至于�q�个��法的得来及正确性，��在下一�D�|��字中�q�行详细分析�?br />
回忆构图的过�E�：
对于两个不相容的点 Ai, Aj�Q�构图方式�ؓ�Q�Ai -> Aj ' ,Aj->Ai ' ,前面提到�q�，�q�样的两条边对称�Q�也��是��_��
如果存在Ai -> Aj�Q�必定存在Aj ' ->Ai ' �?br />
�{��h于：Ai -> Ak,Ak ' ->Ai ' 方便赯��Q�之后�?/span> -> ”代表这样一�U�传递关�p?

猜测1�Q�图中的环分别对�U?br />如果存在Ai,Aj�Q�Ai,Aj属于同一个环(��C��Si),那么Ai ' , Aj ' 也必定属于一个环(��C��Si ' ).
再根据前面的引理�Q�不难推断出每个环分别对�U�。�?br />
证明方式与引理相�c�M��
一个稍�E�复杂点的结�?其中�U�、蓝色部分分别�ؓ两组对称的链�l�构
推广2�Q�对于�Q意一对Si, Si ' �Q�Si的后代节点与Si ' 的前代节点相互对�U�。�?br />�l�而提�?
猜测2�Q�若问题无解�Q�则必然存在Ai, Ai ' �Q��得Ai,Ai ' 属于同一个环。也��是�Q�如果每一对Ai,Ai ' 都不属于同一个环�Q�问题必定有解。下面给出简略证明：

先提��Z��个跟��法1�怼�的步骤：
如果选择Si�Q�那么对于所有Si -> Sj�Q�Sj都必��被选择。�?br />而Si ' 必定不可选，�q�样Si’的所有前代节点也必定不可选（��这一�q�程�U�C��为删除）�?/span>
由推�q?可以得到�Q�这��L��删除不会��D��矛盾�?br />
假设选择S3 '
选择S3 ' 的后代节�? S1 '
删除S3
删除S3的前代节点S1
S1与S1 ' 是对�U�的

每次扑ֈ�一个未被确定的Si�Q��得不存在Si -> Si ' 选择Si及其后代节点而删除Si’及Si‘的前代节点。一定可以构造出一�l�可行解�?/span>
因此猜测2成立�?br />
另外�Q�若每次盲目的去找一个未被确定的Si�Q�时间复杂度相当高�?br />以自底向上的��序�q�行选择、删除，�q�样�q�可以免厠Z��选择Si的后代节点”这一步�?br />用拓扑排序实现自底向上的��序�?br />
一�l�可能的拓扑序列(自底向上�Q?S1 ' ,S2,S2 ' ,S3 ' ,S3,S1

��法2的流�E�：

1 �Q�构�?br /> 2 �Q�求囄��极大��通子�?br /> 3 �Q�把每个子图收羃成单个节点，�Ҏ��原图关系构造一个有向无环图
4 �Q�判断是否有解，无解则输出（退出）
5 �Q�对新图�q�行拓扑排序
6 �Q�自底向上进行选择、删�?br /> 7 �Q�输�?br />
��结�Q?br />整个��法的时间复杂度大概是O(m)�Q�解��x��问题可以说是相当有效了�?br />在整个算法的构造、证明中反复提到了一个词�Q�对�U�。发现、利用了�q�个囄��Ҏ��性质�Q�我们才能够很好的解决问题�?br />�q�且�Q�由2 - SAT问题模型变换出的�c�M��的题目都可以用上�q�方法解冟뀂�?br />
全文�ȝ��Q?br />充分挖掘囄��性质�Q�能够更好的解决问题�?br />不仅仅是对于图论�Q�这�U�思想可以在很多问题中得到很好的应用�?br />希望我们能掌握此�U�解题的思想�Q�在熟练基础��法的同时深入分析、灵�z�运用、大胆创斎ͼ�从而解��x��多更新的��N��?br />

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

KNIGHT — Sun, 31 May 2009 13:44:00 GMT
开始习惯自习室生活。尽量少Coding�?br />从此一节课不逃。。。。。周六，周日�?73.或者看资料。。�?br />Bless pip!

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

KNIGHT — Fri, 29 May 2009 14:14:00 GMT
也做个小��的应用�Q�做TC的时候省了许多代码时�?br />
#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
在字�W�串处理当中�Q�后�~�树和后缀数组都是非常有力的工��P��其中后缀树大家了解得比较多，关于后缀数组则很��见于国内的资料。其实后�~�数组是后�~�树的一个非常精巧的替代品，它比后缀树容易编�E�实玎ͼ�能够实现后缀树的很多功能而时间复杂度也不太逊色�Q��ƈ且，它比后缀树所占用的空间小很多。可以说�Q�在信息学竞赛中后缀数组比后�~�树要更�ؓ实用。因此在本文中笔者想介绍一下后�~�数组的基本概��c��构造方法，以及配合后缀数组的最长公共前�~�数组的构造方法，最后结合一些例子谈谈后�~�数组的应用�?

基本概念

首先明确一些必要的定义�Q?

字符�?一个字�W�集∑是一个徏立了全序关系的集合，也就是说�Q�∑中的��L��两个不同的元素α和β都可以比较大��，要么��<β�Q�要么�?lt;��Q�也��是��>β�Q�。字�W�集∑中的元素称为字�W��?
字符�?一个字�W�串S是将n个字�W�顺�ơ排列�Ş成的数组�Q�n�U�CؓS的长度，表示为len(S)。S的第i个字�W�表�C�ZؓS[i]�?
子串字符串S的子串S[i..j]�Q�i≤j�Q�表�C�S串中从i到j�q�一�D�，也就是顺�ơ排列S[i],S[i+1],...,S[j]形成的字�W�串�?
后缀后缀是指从某个位�|�i开始到整个串末��束的一个特�D�子丌Ӏ�字�W�串S的从i开头的后缀表示为Suffix(S,i)�Q�也��是Suffix(S,i)=S[i..len(S)]�?

关于字符串的大小比较�Q�是指通常所说的“字兔R��序”比较，也就是对于两个字�W�串u、v�Q��oi�?开始顺�ơ比较u[i]和v[i]�Q�如果相�{�则令i�?�Q�否则若u[i]v[i]则认为u>v�Q�也��是vlen (u)或者i>len(v)仍未比较出结果，那么若len(u)len(v)则u>v�?
从字�W�串的大��比较的定义来看�Q�S的两个开头位�|�不同的后缀u和v�q�行比较的结果不可能是相�{�，因�ؓu=v的必要条件len(u)=len(v)在这里不可能满��?

下面我们�U�定一个字�W�集∑和一个字�W�串S�Q�设len(S)=n�Q�且S[n]='$'�Q�也��是说S以一个特�D�字�W?$'�l�尾�Q��ƈ�?$'��于∑中的�Q何一个字�W�。除了S[n]之外�Q�S中的其他字符都属于∑。对于约定的字符串S�Q�从位置i开头的后缀直接写成Suffix(i)�Q�省��d��数S�?

后缀数组后缀数组SA是一个一�l�数�l�，它保�?..n的某个排列SA[1],SA[2],...SA[n]�Q��ƈ且保�?Suffix(SA[i])名次数组名次数组Rank=SA-1�Q�也��是说若SA[i]=j�Q�则Rank[j]=i�Q�不隄��出Rank[i]保存的是Suffix(i)在所有后�~�中从��到大排列的“名�ơ”�?

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

对一个字�W�串u�Q�我们定义u的k-前缀

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

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

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

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

直接�Ҏ��定义�Q�用��次比较对应字符的方法来计算LCP(i,j)昄��是很低效的，旉��复杂度�ؓO(n)�Q�所以我们必��进行适当的预处理以降低每�ơ计��LCP的复杂度�?
�l�过仔细分析�Q�我们发现LCP函数有一个非常好的性质�Q?
设i
要证明LCP Theorem�Q�首先证明LCP Lemma:
对�Q�?≤i证明�Q�设p=min{LCP(i,j),LCP(j,k)}�Q�则有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�Q�同理v=pw�?
于是Suffix(SA[i])=pSuffix(SA[k])�Q�即LCP(i,k)≥p�?(1)

又设LCP(i,k)=q>p�Q�则
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]�Q?
设u[p+1]=x,v[p+1]=y,w[p+1]=z�Q�显然有x≤y≤z�Q�又由p于是�Q�q>p不成立，即LCP(i,k)≤p�?(2)
�l�合(1),(2)�?LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}�Q�LCP Lemma得证�?

于是LCP Theorem可以证明如下�Q?
当j-i=1和j-i=2�Ӟ��昄��成立�?
设j-i=m时LCP Theorem成立�Q�当j-i=m+1�Ӟ��
由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)}�Q?
因j-(i+1)≤m�Q�LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j}�Q�故当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
定义一�l�数�l�height�Q��oheight[i]=LCP(i-1,i)�Q?由LCP Theorem�Q�LCP(i,j)=min{height[k]|i+1≤k≤j}�Q�也��是��_��计算LCP(i,j)�{�同于询问一�l�数�l�height中下标在i+1到j范围内的所有元素的最��倹{��如果height数组是固定的�Q�这��是非常�l�典的RMQ�Q�Range Minimum Query�Q�问题�?
RMQ问题可以用线�D�|��或静态排序树在O(nlogn)旉��内进行预处理�Q�之后每�ơ询问花�Ҏ��间O(logn)�Q�更好的�Ҏ��是RMQ标准��法�Q�可以在O(n)旉��内进行预处理�Q�每�ơ询问可以在常数旉��内完成�?
对于一个固定的字符串S�Q�其height数组昄��是固定的�Q�只要我们能高效地求出height数组�Q�那么运用RMQ�Ҏ��q�行预处理之后，每次计算LCP(i,j)的时间复杂度��是常数�U�了。于是只有一个问题——如何尽量高效地��出height数组�?
�Ҏ��计算后缀数组的经验，我们不应该把n个后�~�看作互不相关的普通字�W�串�Q�而应该尽量利用它们之间的联系�Q�下面证明一个非常有用的性质�Q?
��Z��描述方便�Q�设h[i]=height[Rank[i]]�Q�即height[i]=h[SA[i]]。h数组满��一个性质�Q?
性质3 对于i>1且Rank[i]>1�Q�一定有h[i]≥h[i-1]-1�?
��Z��证明性质3�Q�我们有必要明确两个事实�Q?

设i1�Q�则成立以下两点�Q?
Fact 1 Suffix(i)Fact 2 一定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1�?
看�v来很��奇�Q�但其实很自�Ӟ��lcp(Suffix(i),Suffix(j))>1说明Suffix(i)和Suffix(j)的第一个字�W�是相同的，讑֮�为α，则Suffix(i)相当于α后�q�接Suffix(i+1)�Q�Suffix(j)相当于α后�q�接Suffix(j+1)。比较Suffix (i)和Suffix(j)�Ӟ��W�一个字�W�α是一定相�{�的�Q�于是后面就�{��h于比较Suffix(i)和Suffix(j)�Q�因此Fact 1成立。Fact 2可类��D��明�?

于是可以证明性质3�Q?
当h[i-1]�?�Ӟ��l�论昄��成立�Q�因h[i]�?≥h[i-1]-1�?
当h[i-1]>1�Ӟ��也即height[Rank[i-1]]>1�Q�可见Rank[i-1]>1�Q�因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�Q�有
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])�Q�最�l�得�?h[i]≥h[i-1]-1�?

�Ҏ��性质3�Q�可以��oi�?循环到n按照如下�Ҏ��依次��出h[i]�Q?
若Rank[i]=1�Q�则h[i]=0。字�W�比较次��Cؓ0�?
若i=1或者h[i-1]�?�Q�则直接��Suffix(i)和Suffix(Rank[i]-1)从第一个字�W�开始依�ơ比较直到有字符不相同，由此计算出h[i]。字�W�比较次��Cؓh[i]+1�Q�不��过h[i]-h[i-1]+2�?
否则�Q�说明i>1�Q�Rank[i]>1�Q�h[i-1]>1�Q�根据性质3�Q�Suffix(i)和Suffix(Rank[i]-1)臛_��有前h[i-1]-1个字�W�是相同的，于是字符比较可以从h[i-1]开始，直到某个字符不相同，由此计算出h[i]。字�W�比较次��Cؓh[i]-h[i- 1]+2�?

设SA[1]=p�Q�那么不隄��出�ȝ��字符比较�ơ数不超�q?

也就是说�Q�整个算法的复杂度�ؓO(n)�?
求出了h数组�Q�根据关�p�d��height[i]=h[SA[i]]可以在O(n)旉��内求出height数组�Q�于�?
可以在O(n)旉��内求出height数组�?

�l�合RMQ�Ҏ��Q�在O(n)旉��和空间进行预处理之后��p��做到在常数时间内计算出对��L��(i,j)计算出LCP(i,j)�?
因�ؓlcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])�Q�所以我们也��可以在常数旉��内求出S的�Q何两个后�~�之间的最长公共前�~�。这正是后缀数组能强有力地处理很多字�W�串问题的重要原因之一�?br />后缀数组的应�?br />下面�l�合两个例子谈谈如何�q�用后缀数组.

例一多模式串的模式匹配问�?br />�l�定一个固定待匚w��串S,长度为n,然后每次输入一个模式串P,长度为m,要求�q�回P在S中的一个匹配或者返回匹配失�?所谓匹配指某个位置i满��1≤i≤n-m+1使得S[i..(i+m-1)]=P,也即Suffix(i)=mP.
我们知道,如果只有一个模式串,最好的��法��是KMP��法,旉��复杂度�ؓO(n+m),但是如果有多个模式串,我们��p��考虑做适当的预处理使得�Ҏ��个模式串�q�行匚w��所��q��旉��一�?最��单的预处理莫�q�于建立S的后�~�数组(先在S的后面添�?$'),然后每次��L��匚w��转化为用二分查找法在SA中找到和P的公共前�~�最长的一个后�~�,判断�q�个最长的公共前缀是否�{�于m.�q�样,每次比较P和一个后�~�的复杂度为O(m),因�ؓ最坏情况下可能比较了m个字�W?二分查找需要调用比较的�ơ数为O(logn),因此��d��杂度为O(mlogn),于是每次匚w��的复杂度从O(n+m)变�ؓO(mlogn),可以说改�q�了不少.可是�q�样仍然不能令我们满��?前面提到LCP可以增加后缀数组的威�?

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

在比较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递增的过�E�称为向两边扩展,扩展一�ơ就可以把以T[i]��Z��心的奇回文子串的长度�?.最后r扩展到的最大值决定了以T[i]��Z��心的奇回文子串中的最长者的长度(�?r+1).设len(T)=m,如果用依�ơ比较对应字�W�的�Ҏ��来求向两�Ҏ��展的最大�?则最多可能比较m-1个字�W?�׃��要枚举每个位�|�作��Z��心向两边扩展,所以最坏情况下�ȝ��复杂度可以达到O(m2),不很理想.
下面优化��法的核心部�?br />——以一个位�|��ؓ中心求向两边扩展的最大�?
在T串的末尾��d��一个特�D�字�W?#',规定它不�{�于T的�Q何一个字�W?然后把T串颠�?接在'#'�?在T'串后再添加特�D�字�W?$',规定它小于前面的��M��一个字�W?拼接后�Ş成的串称为S�?不难看出T串中��M��一个字�W�都可在T'中对�U�地扑ֈ�一个相同的字符.如果都用S里的字符来表�C?S[1..m]是T�?S[m+2..2m+1]是T'�?则每个S[i](1≤i≤m)关于'#'对称的字�W�是S[2m-i+2].�q�样原先T串里面的一个子串S[i..j](1≤i≤j≤m)关于'#'也可以对�U�地扑ֈ�一个反��相�{�的子串S[2m-j+2..2m-i+2].
现在我们定下T串的某个位置S[i]��Z��?假设向两�Ҏ��展到了i-r和i+r,那么S[i-r..i-1]和S[i+1..i+r]是反��相�{�的,S[i]可以在T'中找到对�U�的字符S[2m-i+2],设i'=2m-i+2,则S[i-r..i-1]也可以在T'中找到对�U�的子串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')},不难看出,�q�里r=LCP(i,i')-1.上面的推理还存在一个问�?��x��出的LCP(i,i')-1�q�只能看作r的一个上�?�q�不能当成r的最大�?因�ؓ�q�需要证明给出Suffix(i)和Suffix(i')的最长公共前�~�,一定可以反�q�来在T串中扑ֈ�相应的以i��Z��心的回文�?�q�个证明与前面的推理�c�M��,只是需要注意一�?�q�里利用��C��'#'�q�个�Ҏ��字符避免了潜在的LCP(i,i')��过实际的r最大值的危险.�q�个证明留给读者自行完�?��M��,我们已经��定求以T[i]��Z��心向两边扩展的最大值等价于求LCP(i,i'),�Ҏ��前面后缀数组和LCP的相兛_��容这一步操作可以在常数旉��内完�?只要我们预先��p��O(nlogn)的复杂度计算后缀数组,height数组和进行预处理.其中n=len(S)=2m+2.
现在每次求以一个位�|�T[i]��Z��心的回文子串中的最长者的长度可以在常数时间内完成,我们枚�Di�?到m,依次求出所有的�q�些最长�?记录其中最大的一个的长度,��是所要求的最长奇回文子串的长�?�׃��Ҏ��个中心花�Ҏ��间�ؓ常数,所以�ȝ��复杂度�ؓO(m).因此整个��法的复杂度是O(nlogn+m)=O(2mlog(2m)+m)=O(mlogm),是非�怼��U�的算�?比之前的�q�x��U�算法大为改�q?

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

昄��Constant Alphbet属于Integer Alphabet的一�U?而Integer Alphabet是General Alphabet的一�U?构造后�~�数组的复杂度与字�W�集无关,因�ؓ它是直接针对General Alphabet的算�?对于普通方法构造后�~��?如果用儿�?兄弟方式表达树状�l�构,旉��复杂度达到O(n*|∑|),昄��对于Integer Alphabet �?General Alphabet都很低效,对|∑|较大的Constant Alphabet也不适用.解决的方法是用��^衡二叉树来保存指向儿子的指针,�q�样复杂度变为O(n*log|∑|).可见后缀树在某些情况下相对后�~�数组有速度上的优势,但是�q�不明显.对于|∑|很小的字�W�串,后缀树相比后�~�数组的速度优势�q�是比较可观�?��其是对于很常见�?-1�?
后缀数组实际上可以看作后�~�树的所有叶�l�点按照从左到右的次序排列放入数�l�中形成�?所以后�~�数组的用途不可能��出后缀树的范围.甚至可以�?如果不配合LCP,后缀数组的应用范围是很狭�H�的.但是LCP函数配合下的后缀数组��非常强�?可以完成大多数后�~�树所能完成的��d��,因�ؓLCP函数实际上给��Z��L��两个叶子�l�点的最�q�公��q��?�q�方面的内容大家可以自行�?br />�I?后缀树和后缀数组都是字符串处理中非常优秀的数据结�?不能说一个肯定优于另一�?对于不同场合,不同条�g的问�?我们应该灉|��应用,�_�ֿ�选择地选择其中较�ؓ适合的一�?��法和数据结构都是死�?而运用它们的�?才是真正的主�?对经典的��法和数据结构熟�l�掌握�ƈ适当地运用以发挥它们最大的力量,�q�才是信息学研究和竞赛中最大的智慧,也是信息学竞赛的��力
所�?

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

刚做的TC

KNIGHT — Wed, 27 May 2009 16:25:00 GMT
开始的时候因��Z�h多�ؓ患导致TC卡了一�D�|��间。。。。第3�ơ做可以说是�W�一�ơ正式做
延时15分钟本来本子��没有电。。。。。现在还没比完就�?000分的本子搞不住了。。写下日志就差不多over�?br />有点困。。。。�?000分题目都没心情看�?250的题晕了 ��费了很多时间。。。。�?00的倒是很快推出来了可惜 ��想了一�U�情况从新提交了一�ơ。。。。。晕
睡觉了。。。。rating也没性情看了正式的第一�ơTC差不多能够绿了吧。。。。应该能够。。�?br />睡觉�?img src ="http://www.shnenglu.com/ACflying/aggbug/85956.html" width = "1" height = "1" />

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

省赛告一�D�落

KNIGHT — Tue, 26 May 2009 08:33:00 GMT
�l�箋在北大刷题。。�?br />备战四省赛。。。一切都没有变。。�?br />��如xiaoz所��_��AC才是王道�?br />just do it。no matter what happen。Go。！

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

KNIGHT — Fri, 22 May 2009 14:00:00 GMT
上午的时候打��C��一些模�ѝ��。。。主要是一些类似大整数�q�算的常用算法，
�׃��昨天睡得晚了些今天早�?点就��h��打扫寝室�Q�说什么防止猪��感做寝室检查，中午惛_��宿舍睡一觉也没睡�Q�就在实验室WS�Q?br />晚上的时候从头翻QQ日志�Q�感觉有�Ҏ��伤的气氛��q��了一��删一��，�l�果194��删完。。。从此在�q�个Blog写东西省赛做完之后尽快达�?00�Q�封��P��之后完美的做TC�?br /> 后天省赛了，或者说要被工大的众��牛虐了�Q�在�q�里Bless Every Hrbeu‘s Acmers取得好成�l�！

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

狠狠色丁香婷婷综合,国内久久婷婷综合,国产精品视频

poj 3648 Wedding

poj 3678 Priest John's Busiest Day

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

���谈2—SAT问题

[ZZ]后缀数组

刚做的TC

省赛告一�D�落

��谈2—SAT问题