BZOJ4974(给Next求最小字典序原串)
2024-10-21 09:48:36
输入给出了最小循环节长度,暗示next数组。
然后自己按照自己的kmp板子逆着来一遍就好。
const int maxn = 1e5 + ;
int n, a, Next[maxn];
char str[maxn];
bool mark[]; int main() {
read(n);
rep(i, , n) {
read(a);
Next[i] = i - a;
}
str[] = 'a';
for (int i = , j = ; i <= n; j = Next[i++]) {
if (Next[i] == j + ) {
str[i] = str[j + ];
} else {
init(mark, );
do {
mark[str[j + ] - 'a'] = true;
if (!j) break;
j = Next[j];
} while (Next[i] != j + );
rep(k, , ) if (!mark[k]) {
str[i] = 'a' + k;
break;
}
}
}
printf("%s\n", str + );
return ;
}
最新文章
- c#向数据库插入较大数据(SqlBulkCopy)
- dynamic与匿名对象
- EX14 彩票中奖 (lottery.pas/c/cpp)
- uva 1572 self-assembly ——yhx
- HTML5特性检測
- java.util.List 的大小
- Unity属性(Attributes)
- Got permission denied while trying to connect to the Docker daemon socket at
- 解决python logging重复写日志问题
- vue中使用localstorage
- (转)yuicompressor 与 maven结合,打包,压缩js,css (一)
- 关于Base64编码的理解
- ACM-ICPC 2018 焦作赛区网络预赛G Give Candies(隔板定理 + 小费马定理 + 大数取模,组合数求和)题解
- 【Oracle 12c】最新CUUG OCP-071考试题库(54题)
- (一)Quartz2.2.1 简单例子
- Delphi XE8 TStyleBook的使用
- CC3200在sl_Start函数处不断重启复位的原因解析
- lua调试小技巧
- PAT 乙级 1013
- iOS开发工具篇-AppStore统计工具