bzoj 4319 Suffix reconstruction —

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4319

思维还是不行...这样的构造都没思路...

首先，我们可以按 rank 的顺序从小到大填字母，不能填了就是无解；

为了能让后面有字母可填，现在填的字母就要尽可能小；

考虑排名为 i 的后缀首字母能否和排名 i-1 的后缀首字母一样，发现只要判断去掉这个字母后能否满足即可，因为我们先保证后面都可以填成满足排名的形式；

所以，如果下一个位置大小关系是 rk[sa[i]+1] < rk[sa[i-1]+1]，那么 sa[i] 位置就不能和 sa[i-1] 填一样的字母，只能填更大的；

这样填到不能填了，就是无解，否则就构造出来答案了；

关键在于一个一个考虑位置！

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const xn=5e5+;

int n,sa[xn],rk[xn],ans[xn];

int rd()

{

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

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

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

int main()

{

  n=rd();

  for(int i=,x;i<=n;i++)sa[i]=rd(),rk[sa[i]]=i;

  ans[sa[]]=;

  for(int i=,p=;i<=n;i++)

    {

      if(rk[sa[i]+]<rk[sa[i-]+])ans[sa[i]]=++p;

      else ans[sa[i]]=p;

      if(p>){puts("-1"); return ;}

    }

  for(int i=;i<=n;i++)printf("%c",ans[i]+'a'); puts("");

  return ;

}

巴特西

bzoj 4319 Suffix reconstruction —— 贪心构造

最新文章

热门文章