bzoj 4319: cerc2008 Suffix reconstruction 贪心

如果字符集无限大的话直接按照 $sa$ 的顺序依次填即可.

由于字符集非常小，所以要尽量填相同的字符.

我们知道 $sa$ 数组，也就知道了 $rank$ 数组.

那么考虑添加排名为 $i$ 的字符：

如果 $rank[sa[i-1]+1]>rank[sa[i]+1]$，说明 $sa[i]$ 的字典序必须比 $sa[i-1]$ 的字典序大，新建字符.

否则，就不用新建字符.

这么做下去即可.

code:

#include <bits/stdc++.h>

#define N 503000

#define LL long long

using namespace std;

void setIO(string s)

{

    string in=s+".in";

    freopen(in.c_str(),"r",stdin);

}

char str[N];

int sa[N],rk[N];

int main()

{

    // setIO("input");

    int i,j,n;

    scanf("%d",&n);

    for(i=1;i<=n;++i)

    {

        scanf("%d",&sa[i]);

        rk[sa[i]]=i;

    }

    int ch=0;

    str[sa[1]]=ch+'a';

    for(i=2;i<=n;++i)

    {

        if(rk[sa[i]+1]<rk[sa[i-1]+1]) ++ch;

        if(ch>=27)

        {

            printf("-1\n");

            return 0;

        }

        str[sa[i]]=ch+'a';

    }

    printf("%s",str+1);

    return 0;

}

巴特西

bzoj 4319: cerc2008 Suffix reconstruction 贪心

最新文章

热门文章