题意
给出一个 01
序列，一次操作可以选择连续的三个数，把它们都变成三个数的异或和。
问能否在 \(n\) 次以内全变成
0，输出方案。
思路
显然，把三个数都变为异或和不改变异或和，则若所有数异或和为0，无解。
若\(n\)为奇数，则可以依次操作\(n-2, n-4,n-6,...1\)，则操作后有\(a_1=0, a_{2k}=a_{2k+1}\)，则再依次对\(1,3,5,...n-2\)操作，可使所有数变为0。
若n为偶数，则可将数列拆成两段长度为奇数、异或和为0的子数列，分别操作。若没有为0的奇子数列，则无解。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
typedef pair<int, int> pii;
typedef long long ll;
int n, m, k, q;
void work()
{
cin >> n;
vector<int> a(n), sum(n), ans;
for (int i = 0; i < n; i++)
cin >> a[i], sum[i] = sum[i - 1 < 0 ? 0 : i - 1] ^ a[i];
if (sum[n - 1])
{
cout << "NO\n";
return;
}
if (n & 1)
{
for (int i = n - 2; i >= 1; i -= 2)
ans.emplace_back(i);
for (int i = 1; i < n; i += 2)
ans.emplace_back(i);
}
else
{
int stop = -1;
for (int i = 0; i < n; i += 2)
if (!sum[i])
{
stop = i;
break;
}
if (stop == -1)
{
cout << "NO\n";
return;
}
stop++;
for (int i = stop - 2; i >= 1; i -= 2)
ans.emplace_back(i);
for (int i = 1; i < stop; i += 2)
ans.emplace_back(i);
stop++;
for (int i = n - 2; i >= stop; i -= 2)
ans.emplace_back(i);
for (int i = stop; i < n; i += 2)
ans.emplace_back(i);
}
cout << "YES\n" << ans.size() << endl;
for (auto x : ans)
cout << x << ' ';
cout << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t --> 0)
{
work();
}
}
|