bzoj 4974: [Lydsy八月月赛]字符串大师
2024-10-19 14:42:56
4974: [Lydsy八月月赛]字符串大师
Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 371 Solved: 190
[Submit][Status][Discuss]
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。
Input
第一行包含一个正整数n(1<=n<=100000),表示字符串的长度。
第二行包含n个正整数per_1,per_2,...per_n(1<=per_i<=i),表示每个前缀的最短循环节长度。
输入数据保证至少存在一组可行解。
Output
输出一行一个长度为n的小写字符串S,即某个满足条件的S。
若有多个可行的S,输出字典序最小的那一个。
Sample Input
5
1 2 2 2 5
1 2 2 2 5
Sample Output
ababb
/*
如果当前的i!=pre_i,就相当于已知循环节和循环的串求后面的某个位置,xjb取个模就可以知道了
如果当前是i==pre_i,可以考虑KMP的next数组构造,记录下哪些可以可以与前面的匹配从而构成循环节,删去这些字母找个最小的就可以了。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int n,a[maxn];
char s[maxn];
bool vis[maxn];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
s[]='a';
for(int i=;i<=n;i++){
if(i!=a[i])s[i]=s[(i-)%a[i]+];
else{
int tmp=i-;
memset(vis,,sizeof(vis));
while(tmp!=a[tmp]){
tmp=(tmp-)%a[tmp]+;
vis[s[tmp+]-'a']=;
}
for(int j=;j<;j++)
if(!vis[j]){s[i]=j+'a';break;}
}
}
for(int i=;i<=n;i++)printf("%c",s[i]);
}
最新文章
- 【Excel】宏之初认识
- 新浪微博SDK开发(2):上传图片的技术难点
- scala 连接 mysql
- iOS页面间传值的六种方式
- GDB: advanced usages
- 开涛spring3(9.4) - Spring的事务 之 9.4 声明式事务
- sql server中的分页数据查询
- HUST 1585 排队
- 前端 jQuery
- 六星经典CSAPP-笔记(12)并发编程(上)
- Spring 进入Controller前参数校验
- vuex最简单、最直白、最全的入门文档
- 在vultr安装和使用golang
- Django与Ajax
- 基于Senparc.CO2NET 缓存策略扩展的缓存使用方法
- eclipse将javaSE项目导出成可执行jar包
- vi常用指令
- #WEB安全基础 : HTTP协议 | 0x0 TCP/IP四层结构
- codeforces 873C - Strange Game On Matrix
- (转) The Incredible PyTorch
热门文章
- define的用法与注意事项
- Linux下system函数
- Java微信开发_Exception_03_非微信官方网页-invalid signature
- Struts2 - 值栈(ValueStack)
- Execl to HTML
- 【Tensorflow】Ubuntu 安装 Tensorflow gpu
- 【LeetCode】137. Single Number II
- windows下,CSV文件Excel打开乱码
- 洛谷【P1142】轰炸
- 【转】 Pro Android学习笔记(三七):Fragment(2):基础小例子