博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj 4974: 字符串大师
阅读量:4914 次
发布时间:2019-06-11

本文共 1308 字,大约阅读时间需要 4 分钟。

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;}

转载于:https://www.cnblogs.com/Yuzao/p/7581415.html

你可能感兴趣的文章
POJ 3278 Catch That Cow
查看>>
mac 安装wget
查看>>
Linux用户态程序计时方式详解
查看>>
[转]iPhone 多媒体遥控(iPhone Remote Control of Multimedia)后台音乐播放
查看>>
Xcode 5.1 编译模拟器以及真机都能使用的静态库
查看>>
javaScript递归浅析
查看>>
基于MATLAB的多功能语音处理器
查看>>
如何下载国内外专利
查看>>
Linux和其他机器共享文件
查看>>
encodeURIComponent() 函数的使用
查看>>
目标型长尾如何优化
查看>>
怎么看时序图--nand flash的读操作详解
查看>>
插入排序的实现
查看>>
html模拟手机页面
查看>>
#ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE
查看>>
与属性的深入交流
查看>>
事务与分布式事务
查看>>
SQL替换语句之批量修改、增加、删除字段内容
查看>>
win32汇编窗口流程
查看>>
[转] -- html5手机网站自适应需要加的meta标签
查看>>