CF1438D 题解

题面已经说的很清晰了,就不再重复。

这道题 \(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;
}

CF1438D 题解

上一篇:Codeforces Round #734 (Div. 3) E. Fixed Points


下一篇:Vue配置开发环境及初始化项目