1 条题解
-
0XzyStudio (admin) LV 8 MOD 机房蒟蒻 tayz @ 2024-10-20 20:01:46
这个问题的解法很多,这里介绍处理起来最简单的一种。
想判断一个字符串是否是由某个子串循环得到的,只需利用kmp求出其next后判断n-next[n]能否整除n即可,若能则说明最小的循环节长度即为n-next[n],枚举循环次数 \(\frac{n}{n-next[n]}\) 的约数即可得到所有的循环节,再计算优美度的最大值即可。
对于原问题,从每个位置开始单独计算一次next数组就可以得到
所有子串的循环节了,直接枚举约数总复杂度是\(O(n^2\sqrt{n})\)、这里可以
预处理所有数的倍数,将复杂度优化为\(O(n^2logn)\)。std
#include<bits/stdc++.h> #define MAXN 3000 using namespace std; int n,m,a,b,x,y; int nxt[MAXN+5],ans; char s[MAXN+5],t[MAXN+5]; vector<int>d[MAXN+5]; void init() { for (int i=2;i<=n;i++) for (int j=i;j<=n;j+=i) d[j].push_back(i); } int main() { scanf("%d%d%s",&a,&b,s+1); n=strlen(s+1); init(); for (int st=1;st<=n;st++) { m=n-st+1; for (int i=1;i<=m;i++) t[i]=s[st+i-1]; memset(nxt,0,sizeof(nxt)); for (int i=1;i<m;i++) { int j=nxt[i]; while (j&&(t[j+1]!=t[i+1]))j=nxt[j]; nxt[i+1]=(t[j+1]==t[i+1])?(j+1):0; } for (int i=1;i<=m;i++) { x=i-nxt[i];y=i/x; if ((i%x)||(y==1))continue; for (int j=0;j<d[y].size();j++) { int k=i/d[y][j]; ans=max(ans,a*k+b*d[y][j]); } } } printf("%d\n",ans); return 0; }
- 1
信息
- ID
- 1032
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者