题目传送门(BZOJ)
>原文链接<

题解 :

为了满足后缀数组, 肯定是SA靠前的字典序要小, 而为了尽可能有解, 要从'a'从小到大开始满足SA

考虑做到$sa[i]$的时候,当前的字符还能否用.

我们可以通过$sa$先求出$rank$

当两个后缀$(i, j)$的第一个字符一样时, 我们要比较下一个字符, 其实就是在比较$rank[i+1], rank[j+1]$

如果新加的位置的下一位字符串$rank$比前一次加的下一位$rank$小, 就需要新加一个大一点的字符, 否则当前字符也能满足这个位置的后缀大于前一次位置的后缀, 直接把$s[sa[i]]$置成$ch$即可.

若最后$ch>$'z', 则代表无解

看代码似乎能更明白一点.

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 510000;int sa[N], rnk[N];char s[N], ch;int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i ++ ) scanf("%d", &sa[i]), rnk[sa[i]] = i; s[0] = ch = 'a'; for(int i = 2; i <= n; i ++ ) { if(rnk[sa[i]+1] < rnk[sa[i-1]+1]) ch ++ ; s[sa[i]] = ch; } printf("%s\n", ch > 'z' ? "-1" : s);}