分类目录归档:未分类

hdu6223

广义后缀数组!

const int XN=150000+11,XLOGN=18;

int par[XN][XLOGN];
char v[XN];
void Work() {
    int n;fin>>n>>(v+1);
    for(int i=1;i<=n;++i)
        par[i][0]=((long long)(i-1)*(i-1)+1)%n+1;
    for(int b=1;(1<<b)<=n;++b)
        for(int i=1;i<=n;++i)
            par[i][b]=par[par[i][b-1]][b-1];
    static int temp[2][XN],cnt[XN],*x=temp[0],*y=temp[1],sa[XN];
    int m=256;
    std::fill(cnt+1,cnt+1+m,0);
    for(int i=1;i<=n;++i)
        cnt[x[i]=v[i]]++;
    std::partial_sum(cnt+1,cnt+1+m,cnt+1);
    for(int i=1;i<=n;++i)
        sa[cnt[x[i]]--]=i;
    for(int b=0;(1<<b)<n;++b) {
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[par[i][b]]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=1;i<=n;++i)
            y[cnt[x[par[i][b]]]--]=i;
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[i]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=n;i>=1;--i)
            sa[cnt[x[y[i]]]--]=y[i];
        std::swap(x,y);
        int p=x[sa[1]]=1;
        for(int i=2;i<=n;++i)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[par[sa[i-1]][b]]==y[par[sa[i]][b]]?p:++p;
        if((m=p)==n)
            break;
    }

    for(int i=1,p=sa[n];i<=n;++i,p=par[p][0])
        fout<<v[p];
    fout<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}

hdu6223



广义后缀数组!

const int XN=150000+11,XLOGN=18;

int par[XN][XLOGN];
char v[XN];
void Work() {
    int n;fin>>n>>(v+1);
    for(int i=1;i<=n;++i)
        par[i][0]=((long long)(i-1)*(i-1)+1)%n+1;
    for(int b=1;(1<<b)<=n;++b)
        for(int i=1;i<=n;++i)
            par[i][b]=par[par[i][b-1]][b-1];
    static int temp[2][XN],cnt[XN],*x=temp[0],*y=temp[1],sa[XN];
    int m=256;
    std::fill(cnt+1,cnt+1+m,0);
    for(int i=1;i<=n;++i)
        cnt[x[i]=v[i]]++;
    std::partial_sum(cnt+1,cnt+1+m,cnt+1);
    for(int i=1;i<=n;++i)
        sa[cnt[x[i]]--]=i;
    for(int b=0;(1<<b)<n;++b) {
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[par[i][b]]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=1;i<=n;++i)
            y[cnt[x[par[i][b]]]--]=i;
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[i]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=n;i>=1;--i)
            sa[cnt[x[y[i]]]--]=y[i];
        std::swap(x,y);
        int p=x[sa[1]]=1;
        for(int i=2;i<=n;++i)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[par[sa[i-1]][b]]==y[par[sa[i]][b]]?p:++p;
        if((m=p)==n)
            break;
    }

    for(int i=1,p=sa[n];i<=n;++i,p=par[p][0])
        fout<<v[p];
    fout<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}

一个简单的博弈题

Problem

m*n的棋盘,n,m都是奇数,A和B轮流执行选格子操作,要求所有被选中的格子不能相邻。最后谁不能选了,谁就输了。谁会取得胜利。

Solution

先手必胜。先手只需第一步放在整个棋盘的正中央,然后接着一直在后手放的中心对称位置放就好了。

O(n)求字符串的最小表示

Problem

求一个字符串的循环移位中字典序最小的那个。

Solution

两个指针指向两个同构串的开头,比较它们的大小,较大的那个串的与另一个串相等的那一部分及其第一个不同的字符不可能是最小同构串开头,可以直接跳过。

Code

int MinimumRepresentation(int *a,int n) {
    ++a;
    int p1=0,p2=1,len=0;
    while(p1<n && p2<n && len<n) {
        if(a[(p1+len)%n]==a[(p2+len)%n])
            len++;
        else {
            (a[(p1+len)%n]>a[(p2+len)%n]?p1:p2)+=len+1;
            if(p1==p2)
                p2++;
            len=0;
        }
    }
    return std::min(p1,p2)+1;
}