构造，CF862C. Mahmoud and Ehab and the xor

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 862C - Codeforces

---

二、解题报告

1、思路分析

非常松的一道构造题目

我们只需让最终的异或和为x即可

下面给出个人一种构造方式：

先选1~N-3，然后令o = (1 << 17) ^ 1^2^3...^(N-3), w = (1 << 18) ^ o, z = x ^ w

这样除了x，其余所有数的贡献都被异或掉了

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

​

#include 
using PII = std::pair<int, int>;
using i64 = long long;
 
const int inf = 1e9;
 
 
void solve() {
    int N, x;
    std::cin >> N >> x;
    if (N == 1) {
        std::cout << "YES\n" << x;
        return;
    }
    else if(N == 2) {
        if (x) {
            std::cout << "YES\n" << 0 << ' ' << x;
            return;
        }
        std::cout << "NO";
        return;
    }
    std::cout << "YES\n";
    int pre = 0, o = 1 << 17, w = 1 << 18;
    for (int i = 1; i <= N - 3; i ++ ) std::cout << i << ' ', pre ^= i;
    std::cout << (o ^ pre) << ' ' << (w ^ o) << ' ' << (x ^ w);
}
 
 
int main () {
    std::ios::sync_with_stdio(false);   std::cin.tie(0);  std::cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_ --)
        solve();
    return 0;
}