Description
一个串T是S的循环节,当且仅当存在正整数k,使得S是T^k(即T重复k次)的前缀,比如abcd是abcdabcdab的循环节 。给定一个长度为n的仅由小写字符构成的字符串S,请对于每个k(1<=k<=n),求出S长度为k的前缀的最短循环节的 长度per_i。字符串大师小Q觉得这个问题过于简单,于是花了一分钟将其AC了,他想检验你是否也是字符串大师。 小Q告诉你n以及per_1,per_2,...,per_n,请找到一个长度为n的小写字符串S,使得S能对应上per。解题报告: 用时:1h20min,2WA 一开始不敢相信直接取模就行,仔细一想发现只有这样才能合法,然后发现如果\(per_i=i\)那么又是一种情况,因为\(i-1\)已经是一个最小循环节,所以只要保证不和上一个位置的循环节重叠就行,所以我们就沿着上一个循环节往回走,把所有经过的都标记一遍,然后最后\(s[i]\)取最小合法即可,注意'a'在\(per_i=i\)时是什么时候都取不到的
#include#include #include #include #include #include #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;const int N=1e5+5;int n,a[N];char s[N];bool v[30];void work(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); int x; s[1]='a'; if(a[2]==2)s[2]='b'; else s[2]='a'; for(int i=3;i<=n;i++){ if(i!=a[i]){ if(i%a[i])s[i]=s[i%a[i]]; else s[i]=s[a[i]]; } else{ x=i-1; while(x!=a[x]){ if(x%a[x])x%=a[x]; else x=a[x]; v[s[x+1]-'a']=true; } v[0]=true; for(int j=0;j<=25;j++){ if(!v[j]){ s[i]=j+'a';break; } } memset(v,0,sizeof(v)); } } for(int i=1;i<=n;i++)printf("%c",s[i]); puts("");}int main(){ work(); return 0;}