MUV LUV EXTRA
（本篇主要內容，kmp求最短回圈節）
題目傳送門：
MUV LUV EXTRA
題意：
給你一個字串和兩個整數a和b，在小數點后，找到一個回圈節 l，回圈長度為p，求 a * p - b * l 的最大值，
思路：
我們容易想到的是，當回圈長度( p )確定時，我們要找到最小的回圈節（l），那么這時a * p - b * l 的值在該回圈長度下肯定是最大的，因為題目要求是要至少回圈一次且字串的末尾正在回圈中，所以我們列舉回圈長度p時，要先把字串倒置過來，然后接下去很好處理啦，kmp求最小回圈節即可，
AC Code
//kmp從后往前找最短回圈節
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e7+10;
char str[N],cpy[N];
int F[N];
int main()
{
LL a,b;
while(scanf("%lld%lld%s",&a,&b,str)!=EOF)
{
int len=strlen(str);
int ans=0;
for(int i=len-1;i>=0;i--)
{
if(str[i]=='.') break;
cpy[ans++]=str[i];
}
F[0]=-1;
for(int i=1;i<ans;i++)
{
int j=F[i-1];
while(j>=0&&cpy[j+1]!=cpy[i])
j=F[j];
if(cpy[j+1]==cpy[i])
F[i]=j+1;
else F[i]=-1;
}
LL maxn=-1e12;
for(int i=0;i<ans;i++)
{
LL k=i-F[i];
maxn=max((i+1)*a-b*k,maxn);
}
printf("%lld\n",maxn);
}
//system("pause");
return 0;
}
（目前正在做一些CCPC的題，希望一個月之后不會打鐵QAQ）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/227859.html
標籤：其他