[C++知识库]# CF1572B Xor of 3（构造）

解析

你CF还是你CF

省选刷到2017再往前不是很想做了，就来CF玩一玩。
再次感受到被CF浅颜色构造虐的快感。
本题靠着各种乱搞特判在WA了无数次之后艹过去了。
根本没有什么正确性的玄学做法，但是看CF数据似乎把 $n$ 较小的所有情况全都pia到数据里了，小数据全都能正确，这题大数据也没有什么hack的优势，那它可能真的是对的…

还是来看看优美简洁的正解吧。
不难发现操作前后异或和不变，因此如果整体异或和为1必然无解。
考虑奇数怎么做。
分别对 $(n?2,n),(n?4,n?2),(n?6,n?4)...(1,3)$ 操作一次，这样序列就变成了 $0aabbcc...$ 的样子。
然后再对 $(1,3)(3,5)...(n?2,n)$ 做一次即可。

如果是偶数，就找到一段异或和为0的前缀，然后前后分别做即可。
如果找不到，序列就一定长成 $10000...0001$ 的样子，这个时候是无解的（样例也已经给出）。

代码

尽管正解非常好写，但还是懒得写了…
贴上我艰苦奋战出的乱搞代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
using namespace std;

const int N=3e5+100;
const int M=2e5+100;
const int inf=2e9+100;

inline ll read(){
    ll x(0),f(1);char c=getchar();
    while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}

int n,m;
int a[N],ans[N],num;
int s[N];
bool flag;
inline int calc(int l,int r){
	assert(r-l+1==3);
	return a[l]^a[l+1]^a[r];
}
inline void rev(int l,int r){
	int o=calc(l,r);
	for(int i=l;i<=r;i++) a[i]=o;
	ans[++num]=l;	
}

void workl(int p){
	if(p==0) return;
	if(a[p]){
		if(a[p-1]) rev(p-1,p+1);
		else if(a[p-2]) rev(p-2,p);
		else{
			rev(p-2,p);
			rev(p-1,p+1);
		}
	}
	workl(p-1);	
}
void workr(int p){
	if(p==n+1) return;
	if(a[p]){
		if(a[p+1]) rev(p-1,p+1);
		else if(a[p+2]) rev(p,p+2);
		else{
			rev(p,p+2);rev(p-1,p+1);
		}
	}
	workr(p+1);
}

bool find(int l,int r){
	if(calc(l,r)) return false;
	//debug("%d %d\n",l,r);
	if(s[l-1]%2==0){
		rev(l,r);
		workl(l-1);
		workr(r+1);
		return true;
	}
	int x=l,y=r;
	while(l>1&&a[l-1]==0) l--;
	while(r<n&&a[r+1]==0) r++;
	if((r-l+1)%2==1){
		rev(x,y);
		while(l<=r){
			rev(l-1,l+1);
			l+=2;
		}
		workl(r-2);
		workr(r+2);
		return true;
	}
	//debug("1");
	if((r-l+1)%2==0&&l-2>=1){
		if(a[l-2]==0){
			rev(l-2,l);
			l++;
		}
	}
	if((r-l+1)%2==0&&r+2<=n){
		if(a[r+2]==0){
			rev(r,r+2);
			r--;
		}
	}
	if((r-l+1)%2==1){
		while(l<=r){
			rev(l-1,l+1);
			l+=2;
		}
		workl(r-2);
		workr(r+2);
		return true;
	}
	//debug("2");
	return false;
}
void work(){
	num=0;
	flag=0;
	int cnt(0);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read(),cnt+=a[i];
		//s[i]=s[i-1]+a[i];
		//debug("%d ",a[i]);
	}
	//debug("\n");
	if(cnt&1){
		puts("NO");return;
	}
	for(int i=1;i+2<=n;i++){
		if(find(i,i+2)){
			flag=1;break;
		}
		else if(a[i]&&!a[i+1])rev(i,i+2);
		s[i]=s[i-1]+a[i];
	}
	if(!flag){
		for(int i=1;i+2<=n;i++){
			if(find(i,i+2)){
				flag=1;break;
			}
			s[i]=s[i-1]+a[i];
		}
	}
	if(flag){
		puts("YES");
		printf("%d\n",num);
		//assert(num<=n);
		for(int i=1;i<=num;i++) printf("%d ",ans[i]);
		puts("");
	}
	else puts("NO");
}
int clo;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    int T=read();
    while(T--){
    	//debug("%d\n",++clo);
    	work();
	}
    return 0;
}
/*
*/