WA on #5玄学改过?
查看原帖
WA on #5玄学改过?
537998
lpx2024楼主2024/5/5 13:46
#include<bits/stdc++.h>
using namespace std;
const int maxN=200010;
char s[maxN];
int p[maxN],fr[maxN],bk[maxN];
int main(){
	string str;
	cin>>str;
	int n=str.size()*2-1;
	s[0]=s[1]=' ';
	for(int i=0;i<n;i+=2){
		s[i+2]=str[i/2];
		s[i+3]=' ';
	}
	int ans=2,r=0,mid=0;
	for(int i=1;i<=n+2;i++){
		if(i<r) p[i]=min(p[2*mid-i],r-i);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]]) p[i]++;
		if(p[i]+i>=r){
			r=p[i]+i;
			mid=i;
			fr[i-p[i]+1]=max(fr[i-p[i]+1],p[i]-1);
			bk[i+p[i]-1]=max(bk[i+p[i]-1],p[i]-1);
		}
	}
	for(int i=1;i<=n;i+=2) fr[i]=max(fr[i],fr[i-2]-2);
	for(int i=n;i>=1;i-=2) bk[i]=max(bk[i],bk[i+2]-2);
	for(int i=1;i<=n;i+=2) if(fr[i] && bk[i]) ans=max(ans,fr[i]+bk[i]);
	cout<<ans;
	return 0;
}#include<bits/stdc++.h>
using namespace std;
const int maxN=200010;
char s[maxN];
int p[maxN],fr[maxN],bk[maxN];
int main(){
	string str;
	cin>>str;
	int n=str.size()*2-1;
	s[0]=s[1]=' ';
	for(int i=0;i<n;i+=2){
		s[i+2]=str[i/2];
		s[i+3]=' ';
	}
	int ans=2,r=0,mid=0;
	for(int i=1;i<=n+2;i++){
		if(i<r) p[i]=min(p[2*mid-i],r-i);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]]) p[i]++;
		if(p[i]+i>r){
			r=p[i]+i;
			mid=i;
			fr[i-p[i]+1]=max(fr[i-p[i]+1],p[i]-1);
			bk[i+p[i]-1]=max(bk[i+p[i]-1],p[i]-1);
		}
	}
	for(int i=1;i<=n;i+=2) fr[i]=max(fr[i],fr[i-2]-2);
	for(int i=n;i>=1;i-=2) bk[i]=max(bk[i],bk[i+2]-2);
	for(int i=1;i<=n;i+=2) if(fr[i] && bk[i]) ans=max(ans,fr[i]+bk[i]);
	cout<<ans;
	return 0;
}

第五个点caaaacaa,最后那个aa不知道为什么没计上,第51行改成p[i]+i>=r就过了

2024/5/5 13:46
加载中...