\(\text{Problem}:\)Triple Flips
\(\text{Solution}:\)?
考虑初始有一个未确定的大区间 \([1,n]\)，每次操作平均减少 \(3\) 的长度（对于区间左端点三个位置的权值进行分类讨论，右侧相同）。当未确定区间 \([l,r]\) 较小时暴搜。暴力打表可以发现，当 \(n\geq 8\) 时必定有解，故最后保留 \(8\)? 个位置进行即可。具体实现可参考代码（毕竟是构造题）。
\(\text{Code}:\)
#include <bits/stdc++.h>
//#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=100100;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,a[N],len,sta[N],cnt,fir;
struct Node { int x,y,z; };
vector<Node> ans; vi lst;
inline void Opt(int x,int y,int z)
{
a[x]^=1, a[y]^=1, a[z]^=1;
ans.eb((Node){x,y,z});
}
void DFS(int x,int now,vi &g)
{
if(x==cnt+1)
{
if(now^fir) return;
if(lst.empty() || (int)lst.size()>(int)g.size()) lst=g;
return;
}
DFS(x+1,now,g);
g.eb(sta[x]);
DFS(x+1,now^sta[x],g);
g.pop_back();
}
signed main()
{
n=read();
for(ri int i=1;i<=n;i++) a[i]=read();
int l=1,r=n;
while(r-l+1>8)
{
while(r-l+1>8)
{
if(!a[l]) l++;
else if(!a[r]) r--;
else break;
}
if(r-l+1<=8) break;
if(a[l] && a[l+1] && a[l+2]) Opt(l,l+1,l+2), l+=3;
else if(a[l] && !a[l+1] && !a[l+2]) Opt(l,l+3,l+6), l+=3;
else if(a[l] && !a[l+1] && a[l+2]) Opt(l,l+2,l+4), l+=3;
else if(a[r] && a[r-1] && a[r-2]) Opt(r-2,r-1,r), r-=3;
else if(a[r] && !a[r-1] && !a[r-2]) Opt(r-6,r-3,r), r-=3;
else if(a[r] && !a[r-1] && a[r-2]) Opt(r-4,r-2,r), r-=3;
else if((l+r)&1) Opt(l,(l+r-1)/2,r-1), Opt(l+1,(l+r+1)/2,r), l+=3, r-=3;
else Opt(l,(l+r)/2,r), Opt(l+1,(l+r)/2,r-1), l+=3, r-=3;
}
while(r-l+1<=8 && l>1) l--; while(r-l+1<=8 && r<n) r++;
len=r-l+1;
for(ri int i=0;i<len;i++)
{
fir|=(a[i+l]<<i);
for(ri int j=i+2;j<len;j+=2)
{
sta[++cnt]=(1<<i)|(1<<((i+j)/2))|(1<<j);
}
}
vi g; DFS(1,0,g);
if(fir && lst.empty()) return puts("NO")&0;
puts("YES");
for(auto i:lst)
{
Node w={0,0,0};
for(ri int j=0;j<len;j++)
{
if((i>>j)&1^1) continue;
if(!w.x) w.x=j+l;
else if(!w.y) w.y=j+l;
else if(!w.z) w.z=j+l;
}
ans.eb(w);
}
if((int)ans.size()>n/3+12) return puts("NO")&0;
printf("%d\n",(int)ans.size());
for(auto i:ans) printf("%d %d %d\n",i.x,i.y,i.z);
return 0;
}