题面已经说的很清晰了,就不再重复。
这道题 \(n\) 要分为奇数和偶数分类讨论。
我们需要将所有的数都变为一个数,那么需要保证不断地和同一个数做异或,而这道题操作的方式是把三个数变为它们的异或,也就是说,需要另外两个数相等,这样操作才能保证所有的数都变为一个数。
那么对于奇数,我们只需要构造出一个『前面的都是 \(2\) 个 \(2\) 个相等的数,后面是一个单独的数』这样的序列就可以了。
那么只需要在做异或的时候按顺序做,下一个异或操作的起点是上一个异或操作的终点,就可以在 \(n\) 是奇数时构造出上面的序列。
\(n\) 是偶数的情况要复杂一些,可以从题面显然得出,无论操作多少次,序列的异或和不会改变,而最后所有的数都是相等的,那么最后序列的异或和是 \(0\) ,所以如果一开始序列的异或和不是 \(0\) 且 \(n\) 是偶数,就可以直接输出 NO
了。
而如果我们把 \(n\) 拆成 \(n-1\) 和 \(1\) ,前面的 \(n-1\) 按照奇数处理就可以了,而因为无论操作多少次,序列的异或和都是 \(0\) ,所以最后的那个数也一定是和前面的 \(n-1\) 个数相等的。
代码:
// jaco2567 AK IOI
// #include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <cmath>
#include <string>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = 0, F = 1;
char k;
while (!isdigit(k = getchar())) if (k == ‘-‘) F = -1;
while (isdigit(k)) {
res = res * 10 + k - ‘0‘;
k = getchar();
}
return res * F;
}
inline void write(int x) {
if (x < 0) {
putchar(‘-‘);
x = -x;
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + ‘0‘);
}
const int NR = 1e5 + 5;
int n, a[NR], sum;
int main() {
n = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
sum ^= a[i];
}
if (n % 2 == 0 && sum != 0) {
cout << "NO" << endl;
return 0;
}
if (n % 2 == 0) n--;
cout << "YES" << endl << n - 2 << endl;
for (int i = 1; i <= n - 2; i += 2) cout << i << ‘ ‘ << i + 1 << ‘ ‘ << i + 2 << endl;
for (int i = 1; i <= n - 4; i += 2) cout << i << ‘ ‘ << i + 1 << ‘ ‘ << n << endl;
return 0;
}