题目传送门(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);}