Fork me on GitHub

Codeforces 862C(构造+Xor)

Codeforces 892C
题意:给出$n,x$,求构造$n$个不同的数使得其异或和为$x$.
注意两个特判,具体看代码。
Xor的性质:$x ⊕ 0 = x, x ⊕ x = 0$
那么我们可以构造出$n-3$个数,分别为$1,2,…,n-3$,并记录异或和$a$
然后剩下三个数,分别输出两个不同的极大数(比$n$大), 以及他们的异或和与$a$的异或值

这样相当于前面的被后面的异或和抵消(异或和满足右结合律),然后两个不同的极大数是为了防止异或和重复

Codeforces Submission

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, x;
void clean() {
}
void solve() {
clean();
if (n == 1) {
if (x == 0) printf("YES\n0");
else printf("YES\n%d\n", x);
return ;
} else if (n == 2) {
if (x == 0) printf("NO\n"); else printf("YES\n%d 0\n", x);
return ;
}
printf("YES\n");
int tmp = 0, tmp1 = (1 << 17), tmp2 = (1 << 18);
for (int i = 1; i <= n - 3; i++) {
printf("%d ", i);
tmp ^= i;
}
printf("%d %d %d", tmp1, tmp2, (tmp1 ^ tmp2 ^ tmp ^ x));
}
int main() {
scanf("%d%d", &n, &x), solve();
return 0;
}

------ 本文结束 ------