[ZOJ 3296 Connecting the Segments]后缀数组、RMQ、贪心

【题目大意】

给一个串，让你求他最少由多少个可重叠的回文串所组成。输出ans-1（要拼接几次）

【算法分析】

令读入的串为s，s’为s翻转以后的字符串，然后再令S=s+’$’+s’。

对S建立后缀数组，height和lcp

然后枚举对称中心（注意，对称中心可能在字符上，也可能在字符之间,即回文串长度为偶数）

然后利用lcp求出最长覆盖区间。

然后问题变为用最少的区间去覆盖1~n这一段。

直接贪心：先将区间按L排序，然后枚举答案，看答案为ans时最多能覆盖到多远。

如果覆盖完整个1~n，那就可以输出了。

【其它】

TLE,WA了无限遍。。。

一个原因是因为一开始倍增算法里面用的C++的sort，后面改成基数排序就不超时了。

然后另一个原因是因为没有考虑到回文串为偶数长度时，对称轴不在字符上。

另外很不幸。。。我垫底了

果然大家用的都是DC3。。。只有我不会。。。

Submit Time Language Run Time(ms) Run Memory(KB) User Name 2010-02-21 17:03:31 C++ 70 1456 ConanKudo 2010-02-22 10:38:50 C++ 250 11148 lccycc 2010-02-21 19:42:45 C++ 400 20692 ILJ 2010-02-21 17:12:23 C++ 430 12416 zgmf_x20a 2010-02-22 17:53:00 C++ 510 21368 my icpc is going on,有要事先闪了 2010-02-22 17:56:12 C++ 510 21368 my icpc is going on,有要事先闪了 2010-02-22 17:50:59 C++ 520 22152 my icpc is going on,有要事先闪了 2010-02-22 17:48:57 C++ 540 26536 my icpc is going on,有要事先闪了 2010-02-22 18:22:56 C++ 550 23324 my icpc is going on,有要事先闪了 2010-02-22 18:21:04 C++ 600 23324 my icpc is going on,有要事先闪了 2010-02-22 22:52:08 C++ 720 13856 edward

【CODE】

#include #include #include #include #include using namespace std;
const int N=55555*2;
int n,e;
char S[N],lg[N];
int rank[N],sa[N],height[N],ls[N];
int lcp[N][18],TOT;
struct qj{int l,r;}d[N];
struct satmp{int a,b,pos;}a[N];
struct gtp{int next;satmp y;}g[N];

void init(){
    int i,j;
    n=strlen(S+1);
    S[n+1]=’$’;
    j=n+1;
    for (i=n;i>=1;i–){
        j++;
        S[j]=S[i];
    }
    n=j;
    lg[1]=0;
    for (int i=2;i<=n;i++)
      if (i==1<                      else lg[i]=lg[i-1];
}

void Jsort(){
    int i,t,tot;
    e=0; tot=0; memset(ls,0,sizeof(int)*(n+1));
    for (i=1;i<=n;i++){
        e++;
        g[e].y=a[i];
        g[e].next=ls[a[i].b];
        ls[a[i].b]=e;
    }
    for (i=1;i<=n;i++)
      for (t=ls[i];t;t=g[t].next)
        a[++tot]=g[t].y;
       
    e=0; tot=0; memset(ls,0,sizeof(int)*(n+1));
    for (i=n;i>=1;i–){
        e++;
        g[e].y=a[i];
        g[e].next=ls[a[i].a];
        ls[a[i].a]=e;
    }   
    for (i=1;i<=n;i++)
      for (t=ls[i];t;t=g[t].next)
        a[++tot]=g[t].y;
}   

inline bool cmp(satmp X,satmp Y){
    return X.a}

void GetRank(){
    int R=0;
    for (int i=1;i<=n;i++){
      if (!R || a[i].a!=a[i-1].a || a[i].b!=a[i-1].b) R++;
      rank[a[i].pos]=R;
    }   
}   
void build(){
    for (int i=1;i<=n;i++){a[i].a=S[i];a[i].b=0;a[i].pos=i;}
    sort(a+1,a+n+1,cmp);
    GetRank();
    for (int K=0;1<        int k=1<        for (int i=1;i<=n;i++){
            a[i].a=rank[i]; a[i].b=0;
            if (i+k<=n) a[i].b=rank[i+k];
            a[i].pos=i;
        }
        Jsort();
        GetRank();
    }
    for (int i=1;i<=n;i++) sa[rank[i]]=i;
}   

void makeheight(){
    height[1]=0;
    int i,j,k,st;
    for (i=1;i<=n;i++){
        if (rank[i]==1) continue;
        st=max(height[rank[i-1]]-1,0); j=i+st; k=sa[rank[i]-1]+st;
        while (j<=n && k<=n && S[j]==S[k]){j++;k++;st++;}
        height[rank[i]]=st;
    }
}

void initlcp(){
    for (int i=1;i<=n;i++) lcp[i][0]=height[i];
    for (int k=1;1<      for (int i=1;i+(1<        lcp[i][k]=min(lcp[i][k-1],lcp[i+(1<}

inline int Lcp(int l,int r){
    if (l>r) swap(l,r);
    l++;
    int k=lg[r-l+1];
    return min(lcp[l][k],lcp[r-(1<}   

void Ml(){
    int i,j=n+1,LCP;
    TOT=0;
    for (i=1;i<=n/2;i++){
        j–;
        LCP=Lcp(rank[i],rank[j]);
        TOT++;
        d[TOT].l=i-LCP+1;
        d[TOT].r=i+LCP-1;
    }
    j=n+1;   
    for (int i=1;i        j–;
        LCP=Lcp(rank[i+1],rank[j]);
        TOT++;
        d[TOT].l=i-LCP+1;
        d[TOT].r=i+LCP;
    }   
    n/=2;
}   

inline bool TXcmp(qj X,qj Y){
    return X.l}   

void TanXin(){
    sort(d+1,d+1+TOT,TXcmp);
    int now=0,ans,i=0,expand;
    for (ans=1;;ans++){
        expand=0;
        while (i<=TOT && d[i+1].l<=now+1){
            i++;
            if (d[i].r>expand) expand=d[i].r;
        }
        now=expand;
        if (now>=n){
            printf("%dn",ans-1);
            return;
        }   
    }   
}   

int main(){
    while (scanf("%s",S+1)!=EOF){
        init();
        build();
        makeheight();
        initlcp();
        Ml();
        TanXin();
        memset(S,0,sizeof(S));
    }   
}