SCOI2013 密码

题目描述：

Fish是一条生活在海里的鱼。有一天他很无聊，就到处去寻宝。他找到了位于海底深处的宫殿，但是一扇带有密码锁的大门却阻止了他的前进。

通过翻阅古籍，Fish 得知了这个密码的相关信息：

该密码的长度为N。
密码仅含小写字母。
以每一个字符为中心的最长回文串长度。
以每两个相邻字符的间隙为中心的最长回文串长度。

很快Fish 发现可能有无数种满足条件的密码。经过分析，他觉得这些密码中字典序最小的一个最有可能是答案，你能帮他找到这个密码么？

注意：对于两个串A和B，如果它们的前i个字符都相同，而A的第i+1个字符比B的第i+1个字符小，那么认为是则称密码A 的字典序小于密码B 的字典序，例如字符串abc 字典序小于字符串acb。如果密码A的字典序比其他所有满足条件的密码的字典序都小，则密码A是这些密码中字典序最小的一个。

题解：
manacher反演？

贪心+并查集，判断这一位上字符的时候只需要与前边的1个点制造联系。

和manacher好像啊。

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 100050

inline int rd()

{

    int f=,c=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=*c+ch-'';ch=getchar();}

    return f*c;

}

int n,p[*N];

int hed[*N],cnt;

struct EG

{

    int to,nxt;

}e[*N];

void ae(int f,int t)

{

    e[++cnt].to = t;

    e[cnt].nxt = hed[f];

    hed[f] = cnt;

}

int col[*N],fa[*N];

bool vis[];

int findfa(int x)

{

    if(x==fa[x])return x;

    return fa[x]=findfa(fa[x]);

}

int main()

{

    n=rd();

    for(int i=;i<=*n;i+=)

        p[i]=rd();

    for(int i=;i<=*n-;i+=)

        p[i]=rd();

    for(int i=;i<=*n;i++)

        fa[i]=i;

    int mx = ;

    for(int i=;i<=*n;i++)

    {

        for(int j=max(i&,mx-i+(i&));j<=p[i];j+=)

        {

            int f1 = findfa(i-j),f2 = findfa(i+j);

            if(f1!=f2)fa[f2]=f1;

        }

        mx = max(mx,i+p[i]-(i&));

    }

    for(int i=;i<=*n;i++)

    {

        int f1 = findfa(i-p[i]-);

        int f2 = findfa(i+p[i]+);

        ae(f2,f1);ae(f1,f2);

    }

    mx=;

    for(int i=;i<=*n;i+=)

    {

        int ff = findfa(i);

        if(!col[ff])

        {

            for(int j=;j<=;j++)vis[j]=;

            for(int j=hed[ff];j;j=e[j].nxt)

                vis[col[e[j].to]]=;

            for(int j=;j<=&&!col[ff];j++)

                if(!vis[j])col[ff]=j;

        }

        printf("%c",col[ff]+'a'-);

        if(i+p[i]->mx)

        {

            for(int j=mx+;j<=i+p[i]-;j+=)

                col[j]=col[i*-j];

            mx=i+p[i]-;

        }

    }

    printf("\n");

    return ;

}

巴特西

SCOI2013 密码

最新文章

热门文章