MUV LUV EXTRA 2019CCPC秦皇岛站J 2019-09-28 算法竞赛 暂无评论 54 次阅读 # MUV LUV EXTRA 2019CCPC秦皇岛站J （hdu重现赛） 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6740](http://acm.hdu.edu.cn/showproblem.php?pid=6740)   ## 思路 kmp求循环节 设la 表示循环节已经出现的长度，lb表示循环节长度 所求为 max( ans = ( a\* la - b \* lb ) ) 显然 lb <= la, 当la固定时，lb越小 ans越大，这就可以转化求一个字符串的最小循环节长度 先把' . ' 后的字符串反转，这样可以转化成求前缀子串的最小循环节长度 然后自匹配求next数组 i——————————————前缀子串的长度( la ) i - next [ i ] ——————————最小循环节长度 ( lb ) i / (i- next [ i ] )———————— 最小循环节个数 i %(i- next [ i ] )————————不是完整循环节但匹配的部分的长度 ans = max( a\*i - b\* ( i - next[ i ] ) ) (1<=i<=n) 注：ans 可能为负，初始值要赋一个小负数 ## 代码 ```c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e7+10; char a[N],b[N]; int Next[N],n; void calc_Next() { Next[1]=0; for(int i=2,j=0; i<=n; i++) { while(j>0&&a[i]!=a[j+1]) j=Next[j]; if(a[i]==a[j+1]) j++; Next[i]=j; } } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll x,y; while( cin>>x>>y) { cin>>b; int len=strlen(b)-1; n=0; while(b[len]!='.') { a[++n]=b[len--]; } calc_Next(); ll ans=-(1LL<<60); for(int i=1; i<=n; i++) { ans=max(ans,x*i-(i-Next[i])*y); } cout<<ans<<endl; } } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭