原文链接 https://www.cnblogs.com/zhouzhendong/p/CF1071C.html
题目传送门 - CF1071C
题意
给定一个长度为 n 的 01 数列，限定你在 $left lfloor frac n 3 ight floor +12$ 次操作内将所有的数字都变成 0 。
操作定义为：选择三个数 $x,y,z(x<y<z, y-x=z-y)$ ，使得 a[x],a[y],a[z] 翻转 （0 变 1 ，1 变 0）
如果不能完成，那么输出 NO ，否则输出 YES 并输出方案。
$nleq 10^5$
题解
首先我们很容易找到一个可以将一个 1 变成 0 的操作：
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
然后考虑如何高效简化局面。
假设当前局面中只有区间 [L,R] 中有 1 。我们需要以平均每次将区间压缩 3 单位长度的效率来操作。
接下来就是分类讨论：
1. a[L]=0 直接 L++
2. a[R]=0 直接 R--
3. a[L]=a[L+1]=a[L+2]=1 直接翻转他们，消耗一次操作，效率为 3 。
4. a[R]=a[R-1]=a[R-2]=1 同理，效率为 3 。
5. a[L]=1,a[L+1]=0 找到 a[L] 之后的第一个 1 ，假设位置为 p ，并使得 x=L,y=p,z=2p-L，消耗一次操作，效率 至少为 3 。
6. a[R]=1,a[R-1]=0 类似于第 5 种。
（后面那个是没用的，因为数据水，所以比赛的时候直接可以过，为了想这个续了我好久qaq）
7. a[L]=a[L+1]=a[R]=a[R-1]=1,a[L+2]=0,a[R-2]=0 这个是最难想到的。
如果 (L+R) mod 2 = 0 ，设 m = (L+R)/2 ，那么消耗两次操作：(L,m,R) 和 (L+1,m,R-1)
如果 (L+R) mod 2 = 1 ，设 m = (L+R-1)/2 ，那么消耗两次操作：(L,m,R-1) 和 (L+1,m+1,R)
这样做两步，由于 a[L+2]=a[R-2]=0，所以至少效率为 3 。
保证效率为 3 之后。最终我们要面对的是小范围情况。
我们现在只有 2 个 1 了。我们首先要把他们移到一起。这个很容易。
然后将他们转化成一个 1 然后变成 0 就好了。
我们还要注意一种特殊情况：
0 0 0 0 0 0 1 1
我们不能鲁莽地把后面两个 1 变成一个 1 放到第 6 个位置上，这样显然不行，应该直接做两次 1 变成 0 的操作。
当然具体实现的时候还需要注意许多细节问题。我的代码写的比较丑。
另外，这里再提供 1 组 hack 数据。这是我对着某分十分短的AC代码学习之后马上造出来的hack数据。
125 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
LL read(){
LL x=0,f=1;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=-1,ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x*f;
}
int n;
int a[N];
int m=0;
struct Perf{
int x,y,z;
Perf(){}
Perf(int _x,int _y,int _z){
x=_x,y=_y,z=_z;
}
}p[N];
int find(int x,int dx){
while (!a[x]&&1<=x&&x<=n)
x+=dx;
return x;
}
void pef(int x,int y,int z){
a[x]^=1,a[y]^=1,a[z]^=1;
p[++m]=Perf(x,y,z);
}
int gettot(){
int tot=0;
for (int i=1;i<=n;i++)
tot+=a[i];
return tot;
}
void del(int x){
pef(x-6,x-3,x);
pef(x-5,x-4,x-3);
pef(x-6,x-5,x-4);
}
int main(){
n=read();
for (int i=1;i<=n;i++)
a[i]=read();
int L=1,R=n;
while (L+2<=R){
if (a[L]&&a[L+1]&&a[L+2]){
pef(L,L+1,L+2);
L+=3;
continue;
}
if (a[R]&&a[R-1]&&a[R-2]){
pef(R-2,R-1,R);
a[R-2]=a[R-1]=a[R]=0;
R-=3;
}
if (!a[L]){
L++;
continue;
}
if (!a[R]){
R--;
continue;
}
int l=find(L+1,1);
int r=find(R-1,-1);
if (l==R)
break;
if (l!=L+1&&2*l-L<=R){
pef(L,l,l*2-L);
continue;
}
else if (r!=R-1&&2*r-R>=L){
pef(2*r-R,r,R);
continue;
}
else if (l==L+1&&r==R-1){
if ((R-L)%2==0){
int m=(L+R)/2;
pef(L,m,R);
pef(L+1,m,R-1);
continue;
}
else {
int m1=(L+R)/2,m2=m1+1;
pef(L,m1,R-1);
pef(L+1,m2,R);
continue;
}
}
else if (l==L+1&&2*r-R>=L){
pef(2*r-R,r,R);
continue;
}
else if (r==R-1&&2*l-L<=R){
pef(L,l,l*2-L);
continue;
}
else if (l==L+1)
pef(L,l,l+1);
else if (r==R-1)
pef(r-1,r,R);
else
break;
}
if (gettot()>0){
int l=find(1,1);
int r=find(n,-1);
if (l!=r){
while (r+3<=min(9,n)){
pef(r,r+1,r+2);
pef(r+1,r+2,r+3);
r+=3;
}
while (l+3<=min(9,n)){
pef(l,l+1,l+2);
pef(l+1,l+2,l+3);
l+=3;
}
if (gettot()){
if (l>=7&&r>=7){
del(l);
del(r);
}
else {
if ((l+r)%2==0)
return puts("NO"),0;
if (l+1!=r)
pef(l+1,(l+r+1)/2,r);
if (l+2<=n)
pef(l,l+1,l+2),l=r=l+2;
else
pef(l-1,l,l+1),l=r=l-1;
}
}
}
if (gettot()){
while (l+3<=min(9,n)){
pef(l,l+1,l+2);
pef(l+1,l+2,l+3);
l+=3;
}
if (l<7)
return puts("NO"),0;
del(l);
}
}
puts("YES");
printf("%d
",m);
for (int i=1;i<=m;i++)
printf("%d %d %d
",p[i].x,p[i].y,p[i].z);
return 0;
}