原创 | codeforces 1438D，思路非常非常巧妙的构造题

大家好，欢迎来到codeforces专题。

今天选择的问题是contest1438的D题，全场通过人数为1325人。一般在codeforces当中千人通过的题难度都不算太高，但是这题有点例外，虽然没有涉及一点高深的算法，但是想要自己做出来还是有点难度的。

题目链接：https://codeforces.com/contest/1438/problem/D

废话不多说了，我们直接来看题。

题意

给定一个拥有n（

）个正整数的数组，然后我们对数组当中的元素进行一种神奇的异或操作。

操作如下，我们选择三个不同的下标i、j、k。对a[i],a[j],a[k]这三个元素执行异或操作，即

。之后这三个数分别赋值成这个异或之后的结果。

现在我们想要在n步这样的神奇异或操作之内让数组当中的所有元素全部相等，请问这一点是否可能呢？首先输出YES或NO，表示是否有解。如果有解输出需要操作的步数，以及对应选择的元素下标。

样例

在第一个样例当中，4、1、7的异或结果为2，所以通过这样一步操作之后，即可以满足所有元素全部均等。

题解

我一开始的时候惯性思维，既然是异或运算，那么肯定要从二进制下手。一个数组当中的所有元素均等，其实就等价于它们在每一个二进制位上也等相等，同为0或者是同为1。于是我就一直在思考怎么来针对每一个二进制位来进行判断和选择，不知不觉就走进了死胡同，因为这些二进制位之间彼此影响， 我们很难一位一位地梳理清楚。

我之所以走进死胡同是因为被题目当中的一个条件给欺骗了，这个条件就是最多n个操作步骤的限制。我们直观上都会觉得这是一个非常严苛的要求，所以会期望想到一个完美的解法，可以用最少的步骤解开这个问题。

但实际上这个n足够大，足够一些看起来非常笨的方法也能AC。不得不说这也是很多题目当中惯用的思维陷阱，考验的就是选手的胆量和经验。

异或的性质

首先我们来分析一下异或运算，这题当中并没有对异或做什么特殊的处理。唯一不同的地方就是，我们是对三个数进行异或。我们从最基础的01二进制位来分析，3个数做异或只有四种情况。000、010、011和111，我们发现其中000和011的结果都是0，010和111的结果是1。因为异或相同为0，不同为1的计算特性，会导致相同的数被消除。

比如我们计算的三个数是[a,b,b]那么最后的结果是a，我们可以利用这一点来做文章。想起来或许有些复杂，但是说穿了真的一文不值。

我们假设n=7，这7个数分别是[a,b,c,d,e,f,g]。首先我们对前三个数进行异或操作，这样我们会得到：[h,h,h,d,e,f,g]，接着我们选择第3、4、5位的元素操作，得到：[h,h,j,j,j,f,g]。我们继续选择第5、6、7位的元素进行操作，得到[h,h,j,j,k,k,k]。

到这里其实已经有点眉目了，因为[a,b,b]的操作结果是a，我们剩下要做的就是继续选择，把除了k之外其他的元素全部消除。

我们继续选择第3、4、5位的元素操作，得到[h,h,k,k,k,k,k]，同理我们最后选择第1、2、3位的元素操作，这样整个数组当中的元素都变成了k。到这里，我们一共进行了5次，也就是n-2次操作，完全没有超过题目的限制。

但是这里有一个小问题，这个方案之所以可行是有前提的。它最大的前提就是n是奇数。如果n是偶数，就会最后剩下一个元素，这个应该怎么解决呢？

偶数的情况

偶数的情况我们光想是很难想出办法来的，因为我们解决不了最后多余一个元素的问题。

这里需要用到一个关键性的推论，这个推论非常隐蔽，真的不容易想到。我们假设

，当n为偶数时，那么无论我们对这n个元素如何操作，这个异或得到的k保持不变。

这个结论是从哪里来的？其实也是从异或的性质当中来的。我们对三个数做异或，从具体某一个二进制位来分析。我们会发现我们的操作不会改变整体这n个bit的奇偶性。对于异或操作而言，两两相消，最后的结果只和奇偶性相关。最终的结果只和这个奇偶性相关。

从这一点出发，我们进一步可以得到如果

，那么一定无解。

这个结论其实也很简单，因为我们已经知道了，无论我们如何操作也不会改变这个k值。由于n是偶数，所以如果n个数完全相等的话，那么它们的异或值一定等于0，所以k不等于0的时候，一定无解。

当k等于0的时候怎么办呢？其实非常简单，我们只需要抛弃掉最后一个元素，把之前的n-1个元素按照上面n为奇数时的操作全部操作相等即可。这样一番操作之后，数组会变成这样[a,a,a,a...a,b]。前面n-1个a的异或值为a，而整体n个数的异或值为0，所以可以得到a=b。那么我们就完成了整个操作。

整个思路有了之后，代码实现就太简单了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N=100050;
const long long Mod=1000000007;

using namespace std;

int a[N];
int main() {
    int n, x;
    scanf("%d", &n);
    rep(i, 0, n) {
        scanf("%d", a + i);
    }
    // 如果n为奇数，一定有解
    if (n % 2) {
        puts("YES");
        printf("%d\n", n-2);
        for (int i = 0; i + 2 < n; i+=2) {
            printf("%d %d %d\n", i+1, i+2, i+3);
        }
        for (int i = n-3; i - 2 >= 0; i-=2) {
            printf("%d %d %d\n", i+1, i, i-1);
        }
    }else {
     // 如果n为偶数，判断整个数组的异或值是否为0
        x = 0;
        rep(i, 0, n) x ^= a[i];
        if (x > 0) {
            puts("NO");
        }else {
            n --;
            puts("YES");
            printf("%d\n", n-2);
            for (int i = 0; i + 2 < n; i+=2) {
                printf("%d %d %d\n", i+1, i+2, i+3);
            }
            for (int i = n-3; i - 2 >= 0; i-=2) {
                printf("%d %d %d\n", i+1, i, i-1);
            }
        }
    }
    return 0;
}

到这里，今天这道题就做完了，怎么样，今天的题目还挺有意思吧。讲道理把算法讲出来之后非常简单，几乎没有难度，但是如果让我们自己思考，会变得非常难，我们很难从当中整理出思绪来。思路巧妙有趣这也是codeforces题目的最大魅力所在，希望大家都能体会到算法的乐趣。