链接
http://acm.hdu.edu.cn/showproblem.php?pid=6740
题意
已知一个小数，定义它的可靠值为：$ap-bl$（ $p$ 为已经出现的循环部分总长度，$l$ 为循环节长度）
求最大的可靠值
思路
倒着 KMP
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+5;
char s[N];
ll nxt[N];
int len;
void getNext() {
int i=0;
int j=-1;
nxt[0]=-1;
while(i<len) {
if(j==-1||s[i]==s[j]) {
i++,j++;
nxt[i]=j;
}
else j=nxt[j];
}
}
int main() {
int a,b;
while(~scanf("%lld%lld",&a,&b)) {
scanf("%s",s);
sscanf(s,"%*[^.].%s",s);
len=strlen(s);
reverse(s,s+len);
getNext();
ll ans=0xc0c0c0c0c0c0c0c0;
for(ll i=1;i<=len;i++) ans=max(ans,a*i-b*(i-nxt[i]));
printf("%lld\n",ans);
}
return 0;
}
|