当前位置：网站首页>MUV LUV EXTRA 2019CCPC Qinhuangdao Station J Question KMP

MUV LUV EXTRA 2019CCPC Qinhuangdao Station J Question KMP

2022-08-09 07:04:00 【swust_fang】

topic link

The meaning of the question: It means to count a string for you two, and then let you process the string after the decimal point of the string, find a loop section and the length of the corresponding occurrence,

Then use a*p-b*l to get a maximum value

Then the loop section must be thought of KMP, and then the loop length According to the example, he can find a loop section from the middle, but it all loops to the end,

Then I found out that he was actually looking for a loop section from the back to the front, then this question is very simple

Find the string and reverse it, find KMP, enumerate the length from front to back, the next array corresponds to the length of the loop section, and traverse it once to find the maximum value

Pit: The character of 1e7 came out, and I wrote cin, which was unexpectedly t (t1 sent

The initial value of ans should be assigned as infinitesimal~(wa1 hair!

ac code:

//#pragma comment (linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include#include#include#include#include#include#include#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 pairconst 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>str;int len=strlen(str);ll ans=-inFF;int cnt=0;for(int i=0;ii;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://yzsam.com/2022/221/202208090700344167.html

边栏推荐

猜你喜欢

随机推荐