显然最短循环节长度=i-next[i]，则相当于给定next数组构造字符串。然后按照kmp的过程模拟即可。虽然这看起来是一个染色问题，但是由图的特殊性，如果next=0只要贪心地选最小的就可以了，然而并不会证。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<cassert> using namespace std; #define ll long long #define N 100010 char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,nxt[N]; bool flag[26]; char s[N]; int main() { #ifndef ONLINE_JUDGE freopen("bzoj4974.in","r",stdin); freopen("bzoj4974.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read(); for (int i=1;i<=n;i++) nxt[i]=i-read(); nxt[0]=-1; for (int i=1;i<=n;i++) { int j=nxt[i-1];memset(flag,0,sizeof(flag)); while (~j&&j+1!=nxt[i]) flag[s[j+1]-‘a‘]=1,j=nxt[j]; if (j==-1) {for (int j=0;j<26;j++) if (!flag[j]) {s[i]=j+‘a‘;break;}} else s[i]=s[j+1]; } printf("%s",s+1); return 0; }
原文：https://www.cnblogs.com/Gloid/p/10054430.html