题目
给出一个 \(01\) 序列，一次操作可以选择连续的三个数，把它们都变成三个数的异或和。
问能否在 \(n\) 次以内全变成 0，输出方案。
思路
我们先从简单的地方入手:第一个位置,因为第一个位置仅有一种操作可以改变它的值,前三个数最优情况下最多执行一次操作.
若第一位为0,可以直接跳过.
若第一位为1,我们需要借助第二第三位消去第一位,更具体地:
- 若前三位为
111,借助后面将第三个变成0然后消掉,我们没有必要动第二位,因为动了第二位,第三位也会跟着变,接着就是100或者111,还是不能将第一位消去 - 若前三位为
110,直接消 - 若前三位为
101,直接消 - 若前三位为
100,借助后面将第三个变成1然后消掉,同1,不动第二位
因此,我们写两个函数to_0(int pos),to_1(int pos),借助\(pos+1\sim n\)位,构造方案将\(pos\)位改为0/1.
不用管什么后效性问题,我们一定要将第一位变成0,暂时不考虑后面的.
然后全序列的前端至少有一个0.
找到第一个1,若下一个位置也是1,又因为前一位为0,直接消掉这两位即可.若下一位是0,懒得写了,看代码.
只要后面1的个数为偶数,就可以全部消去,否则,不能消.
代码
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int read() {
int re = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return re;
}
const int N = 2e5 + 10;
int n;
int a[N];
bool to0(int pos);
bool to1(int pos);
vector <int> ans;
bool to0(int pos) {
if(pos + 2 > n)return false;
if(a[pos] == 0)return true;
if((a[pos] ^ a[pos + 1] ^ a[pos + 2]) == 0) {
ans.push_back(pos);
a[pos] = a[pos + 1] = a[pos + 2] = 0;
return true;
}
if((a[pos + 2] == 0) ? to1(pos + 2) : to0(pos + 2) ) {
a[pos] = a[pos + 1] = a[pos + 2] = 0;
ans.push_back(pos);
return true;
}
return false;
}
bool to1(int pos) {
if(pos + 2 > n)return false;
if(a[pos] == 1)return true;
if((a[pos] ^ a[pos + 1] ^ a[pos + 2]) == 1) {
ans.push_back(pos);
a[pos] = a[pos + 1] = a[pos + 2] = 1;
return true;
}
if((a[pos + 2] == 0) ? to1(pos + 2) : to0(pos + 2)) {
a[pos] = a[pos + 1] = a[pos + 2] = 1;
ans.push_back(pos);
return true;
}
return false;
}
void solve() {
ans.clear();
n = read();
for(int i = 1 ; i <= n ; i++)
a[i] = read();
if(a[1] == 1)
if(to0(1) == false) {
puts("NO");
return;
}
a[n + 1] = 3;
for(int i = 2 ; i <= n - 1 ; i++)
if(a[i] == 1) {
if(a[i + 1] == 0 && a[i + 2] == 0) {
ans.push_back(i) , ans.push_back(i - 1);
a[i] = a[i + 1] = 0 , a[i + 2] = 1;
} else if(a[i + 1] == 0 && a[i + 2] == 1) {
ans.push_back(i);
a[i] = a[i + 1] = a[i + 2] = 0;
} else if(a[i + 1] == 1) {
ans.push_back(i - 1);
a[i] = a[i + 1] = 0;
}
}
for(int i = 1 ; i <= n ; i++)
if(a[i] == 1) {
puts("NO");
return ;
}
puts("YES");
printf("%d\n" , ans.size());
if(ans.size()) {
for(int i : ans)
printf("%d " , i);
putchar('\n');
}
}
int main() {
int T = read();
while(T--)solve();
return 0;
}