Codeforces Global Round 25 E

链接

其实还是很好写的。
其实很明显，手玩一下就可以发现只用1次或者两次就可以分完，否则就是以下3中情况。

1. aaaaaa
2. aaabaaa
3. abababa

这个证明很简单。难在怎么想。其实就是手玩以下，看看怎么样分不了，然后就可以了。样例具有一定的迷惑性，还是很好解决的。
然后马拉车数组清空要清到N+2，我的是这样，因为while找的时候会涉及到后面的数字，也可以加个特判。这个问题导致我赛时wa了8发做不出来。哎，也是因为马拉车是网上的板子的原因吧。

好吧其实后面的才是最大的原因。然后跑完马拉车是可以O（1）判断任意连续子串是否为回文串的，这个需要注意。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	char c=getchar();int a=0,b=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int dp[2000501];//注意数组大小
char str[2000501],s[2000501];
int odd[2000501],even[2000501];
int len,N;
bool cherk(int l,int r)
{
	int mid=l+r>>1;
	if((r-l+1)%2==0)
	{
		if(odd[mid]>=(r-l+1))return 1;
		else return 0;
	}
	else
	{
		if(even[mid]>=(r-l+1))return 1;
		else return 0;
	}
} 	
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=read();char c1;
	for(int t=1;t<=T;t++)
	{
		for(int i=0;i<=N;i++)
		{
//			str[i]=s[i]=0;
			dp[i]=0;
			odd[i]=even[i]=0;
		}
		for(int i=0;i<=N+2;i++)str[i]=0;
		N=0,len=0;
		scanf("%s",s+1);
		if(t==1)c1=s[1];
	    int N=0,len=strlen(s+1);
	    bool flag=0;dp[1]=dp[0]=0;
	    for(int i=2;i<=len;i++)
	    {
	    	if(len%2==1&&(i==(1+len>>1)))continue;
	    	if(s[i]!=s[1])flag=1;
		}
		if(s[1]!=s[len])flag=1;
		if(flag==0)
		{
			cout<<"No"<<endl;
			continue;
		}
	    for(int i=1;i<=len;i++)
	    {
	    	dp[i]=0;
		}
	    str[0]='$';//防止越界
	    for(int i=1;i<=len;i++)
		{
	        str[++N]='#';
	        str[++N]=s[i];
	    }
	    str[++N]='#',str[++N]='@';//最后再加一个@
	    int right=0,pos=0;
	    for(int i=1;i<=N;i++)dp[i]=0;
	    for(int i=1;i<=N;i++){
	        if(i<right)
	            dp[i]=min(dp[2*pos-i],right-i);
	        else
	            dp[right=i]=1;
	        while(str[i-dp[i]]==str[i+dp[i]])
	            dp[i]++;
	        if(i+dp[i]>right)
	            right=i+dp[i],pos=i;
	    }
	    int ret=0;
	    for(int i=1;i<=N;i++)
	        ret=max(ret,dp[i]-1);//找最长回文
	    for(int i=1;i<=N;i++)
	    {
	    	if(i%2==1)
	    	{
	    		odd[i/2]=dp[i]-1;
			}
			else
			{
				even[i/2]=dp[i]-1;
			}
		}
	    if(ret!=len)
	    {
	    	cout<<"Yes"<<endl;
	    	cout<<1<<endl;
	    	for(int i=1;i<=len;i++)
			{
				cout<<s[i];
			}
			cout<<endl;
	    	continue;
		}
		flag=0;
		for(int i=2;i<len;i++)
		{
			if(s[i+1]!=s[i-1])flag=1;
		}
		if(flag==0)
		{
			cout<<"No"<<endl;
			continue;
		}
		int mid=0;
		for(int i=2;i<len;i++)
		{
			if(cherk(1,i)==0&&cherk(i+1,len)==0)
			{
				mid=i;
				break;
			}
		}
		if(mid==0)
		{
			cout<<"No"<<endl;
			continue;
		}
		cout<<"Yes"<<endl;
		cout<<2<<endl;
//		}
		for(int i=1;i<=mid;i++)
		{
			cout<<s[i];
		}
		cout<<' ';
		for(int i=mid+1;i<=len;i++)
		{
			cout<<s[i];
		}
		cout<<endl;
	}
	return 0;
}
/*
1
aabaaabaa

aababaa

1
aaabaaa
*/