当前位置:网站首页>MUV LUV EXTRA 2019CCPC秦皇岛站J题 KMP

MUV LUV EXTRA 2019CCPC秦皇岛站J题 KMP

2022-08-09 07:01:00 swust_fang

题目链接

题意:意思给你俩数一个字符串,然后让你对字符串小数点后边的字符串进行处理,找个一个循环节以及对应出现的长度,

然后用a*p-b*l算得到一个最大值

那肯定循环节就想到了KMP了,然后循环长度根据样例他能从中间找一个循环节,但是都是循环到结尾的,

那一下发现他其实是从后往前找的循环节,那这个题就非常简单了

找出字符串反转一下,求KMP,从前到后枚举长度,next数组对应循环节长度,遍历一遍即可求出最大值

坑:1e7的字符出,我写的cin,意料之中的t了(t1发 

ans赋初值要赋成无穷小~(wa1发!

ac代码:

//#pragma comment (linker, "/STACK:102400000,102400000")
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
typedef unsigned long long ull;
typedef long long ll;
#define pii make_pair
#define pr pair<int,int>
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=998244353;
const int maxn=1e7+5;
const int maxm=1e6+5;
char s[maxn],str[maxn];
int nex[maxn];
void get_kmp(int m)
{
    int k=-1,j=0;
    nex[0]=-1;
    while(j<m)
    {
        if(k==-1||s[j]==s[k])
        {
            j++,k++;
            nex[j]=k;
        }
        else k=nex[k];
    }
}
int main()
{
    ll a,b;
    while(scanf("%lld %lld",&a,&b)!=EOF)
    {
        cin>>str;
        int len=strlen(str);
        ll ans=-inFF;
        int cnt=0;
        for(int i=0;i<len;i++)
        {
            if(str[i]=='.')
            {
                for(int j=len-1;j>i;j--) s[cnt++]=str[j];
                break;
            }
        }
        get_kmp(cnt);
        for(int i=1;i<=cnt;i++)
            ans=max(ans,a*i-b*(i-nex[i]));
        printf("%lld\n",ans);
    }
}

 

原网站

版权声明
本文为[swust_fang]所创,转载请带上原文链接,感谢
https://blog.csdn.net/swust5120171204/article/details/102478523