Codeforces Round 938 (Div. 3) E

链接

有点意思的题目。
首先可以得到的一个结论就是，如果k能够完成，那唯一的操作方法就是从前往后，遇到0就使用，把这个点变成1。

那么我们就能够做到O(n)验证了，然后发现O(n^2)可以接受，就过了。

但是我因为滥用数据结构，导致我认为验证需要O(nlogn)然后5000又刚刚好跑不过去。
所以觉得做法假了，尝试从减少验证的次数上下手。
首先可以发现一个性质，就是如果k=m的时候是可以分解完成的，那么m的所有因子作为k也是可以的，
那假如能够证明，所有合法的k都是一个数字的因子的话，那这题就可以通过质因数分解的方法来做到两个log
很明显，不可以。反例：011110 k=5和2都可以。
然后就做法假了。

死因：没有发现滑动窗口是不需要动态维护前缀和的，只需要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
*/