传送门

题目大意

给定一个字符串的每一个前缀的最短循环节长度,求符合要求的字典序最小的字符串。

题解

给定循环节最短长度就是给定了这个字符串$kmp$的$next$数组,即$X_i=i-next_i$,$X_i$表示给定的循环节长度。

由于答案一定有解,考虑模拟构造一个这样的字符串,并模拟求它的$next$数组的过程。如果匹配到发现$i$从$j$处转移,那么就用$j$处的字母赋给$i$,否则就得到了$i,j$互不相同的条件,我们就得到了一个$i$不能取得字符集$S$,对$S$取$mex$即可。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define M 100020
using namespace std;
namespace IO{
const int BS=(1<<20); int Top=0;
char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1;
char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}
void flush(){fwrite(OT,1,OS-OT,stdout);}
void Putchar(char c){*OS++ =c;if(OS==fin)flush(),OS=OT;}
void write(int x){
if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-');
while(x) SS[++Top]=x%10,x/=10;
while(Top) Putchar(SS[Top]+'0'),--Top;
}
int read(){
int nm=0,fh=1; char cw=Getchar();
for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh;
for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0');
return nm*fh;
}
}
using namespace IO;
int n,m,p[M],nxt[M]; char s[M]; bool G[M][26];
int main(){
n=read(),s[1]='a',nxt[0]=-1,memset(G,true,sizeof(G));
for(int i=1;i<=n;i++) p[i]=read(),nxt[i]=i-p[i]; Putchar('a');
for(int i=2;i<=n;i++){
for(int j=nxt[i-1]+1;j>=0;j=nxt[j-1]+1){
if(!j){for(int k=0;k<26;k++) if(G[i][k]){s[i]=k+'a';break;}}
else if(nxt[i]==j) s[i]=s[j];
else{G[i][s[j]-'a']=false;continue;}break;
} Putchar(s[i]);
}Putchar('\n'),flush(); return 0;
}

最新文章

  1. Core Java 总结(异常类问题)
  2. POJ 1163 The Triangle(简单动态规划)
  3. 微信小程序-视图视图引用
  4. 怎么把多个GridView和Repeater导入到word或者excel中
  5. 【leetcode】Remove Duplicates from Sorted List (easy)
  6. Code First 数据注释--InverseProperty 和 ForeignKey
  7. POJ_Fibonacci POJ_3070(矩阵快速幂入门题,附上自己写的矩阵模板)
  8. Log4Net 的简要配置
  9. php接口数据加密、解密、验证签名代码实例
  10. 专题开发十三:JEECG微云高速开发平台-附录
  11. Netfilter-packet-flow.svg
  12. 在http请求中的Content-Type
  13. 从源码角度看LinkedList一些基本操作(jdk1.7)
  14. 【SpringBoot笔记】SpringBoot整合Druid数据连接池
  15. Power BI 关注博客更新
  16. 利用Python+163邮箱授权码发送邮件
  17. HTML学习笔记Day15
  18. ubuntud安装Adobe Flash Player / Plugin
  19. Python基础教程(第3版) 笔记(二)
  20. springboot 中事件监听模型的一种实现

热门文章

  1. ios推送服务,php服务端
  2. IntelliJ IDEA集成JProfiler,入门教程
  3. cocoapods最新使用
  4. springboot带分页的条件查询
  5. 我的Android进阶之旅------>对Android开发者有益的40条优化建议
  6. Failed to decode response: zlib_decode(): data error Retrying with degraded;
  7. centos7 使用 maven
  8. bug-5——(js)indexOf()
  9. 从 零开始 无差错 装好nginx+PHP
  10. linux 5-sort,uniq,tar,split