Processing math: 100%

「AtCoder ABC126-F」XOR Matching

Description

构造一个序列 {a},这个序列的长度是 2m+1,且 02m1 中的每一个整数都必须出现 2 次。对于任何 ai=aj (i<j),都满足 aiai+1aj1aj=k 。 如果不存在这样的序列输出 -1(0m17,0k109)

Source

[AtCoder]ABC126-F

Solution

显然当 k>2m1 时无解,因为 2m1 的每一个二进制位都是 1,与比它小的数异或后不可能大于 2m1

考虑构造一个合法的序列。

我们在中间放一个数 k,然后在其两边放相同的数,比如:

0,1,2,3,,2m1,k,2m1,,3,2,1,0

这显然是没有问题的,因为对于任意两个相同的数,它们中间两两相同的数能互相抵消为 0,最终的异或和一定是 k 。如果按这种方法构造,可以让除了 k 之外的所有数符合条件,但是还多了一个 k,考虑这个 k 应该放在哪里。

我们可以通过异或运算的性质得到一个结论:

n 为大于 1 的整数时,存在

012(2n1)=0

证明:

将它们两两异或得到一个新的序列。

0(2n1)=2n11(2n2)=2n12(2n3)=2n1(2n11)2n1=2n1

显然异或后只剩下 2n12n1,根据异或运算的性质(偶数个相同数的异或和为 0)得到:当 n>1 时,2n1 一定为偶数,该式子的值为 0 得证。

因此我们只需要将另一个 k 放在最后即可,这样两个 k 中间的数与其中一个 k 的异或和刚好为 00 异或另一个 k 的值为 k 。最后注意 n=1 时结论不成立需要特判。时间复杂度为 O(n)

Code

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = (1 << 18) + 5;
int n, m, k, maxn, ans[MAXN + 5];

int main() {
read(m), read(k);
maxn = (1 << m) - 1, n = 1 << (m + 1);
if (m == 1) {//特判 m = 1
if (k == 0) puts("0 0 1 1");
else puts("-1");
return 0;
}
if (k > maxn) {//无解
puts("-1");
return 0;
}
ans[n / 2] = ans[n] = k;//中间和末项都是 k
for (int p = 0, i = 1; i <= maxn; ++i, ++p) {
if (p == k) ++p;//k 已经被占用,k 的两边不能放 k
ans[i] = ans[n - i] = p;//对称地在 k 两边放数
}
for (int i = 1; i <= n; ++i) {
write(ans[i]);
putchar(' ');
}
putchar('\n');
return 0;
}

本文标题:「AtCoder ABC126-F」XOR Matching

文章作者:Heartlessly

发布时间:2019年05月20日 - 11:21:03

最后更新:2019年05月28日 - 20:04:32

原始链接:https://heartlessly.github.io/problems/atcoder-abc126-f/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!

0%