Codeforces 1174D:Ehab and the Expected XOR Problem 题解

主要思路

这道题还蛮妙的,自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\),根据异或按位处理的性质,显然对于所有的\(S_i\)都会小于\(2^n\)。最后,我们可以把限制变成:

  • 不存在两个相同的前缀和。
  • 不存在一对前缀和,其异或值为\(x\)。

针对\(x\)的大小关系,我们可以分成两种情况:

  • \(x \geq 2^n\),不存在一对\((S_i, S_j)\)的异或为\(x\),因为存在更高的位并不会被消除。
  • \(x < 2^n\),我们发现每选择一个数作为前缀和,整个\(2^n\)中就会少一个对应的可以被选择的数。所以,我们每次选一个作为\(S_i\)的数时,都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

代码

// CF1174D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = (1 << 18) + 200;

int n, x, seq[MAX_N];
bool vis[MAX_N];

int main()
{
    scanf("%d%d", &n, &x);
    if (x >= (1 << n))
    {
        int len = (1 << n) - 1;
        printf("%d\n", len);
        for (int i = 1; i <= len; i++)
            printf("%d ", i ^ (i - 1));
    }
    else
    {
        vis[x] = true;
        int tot = 0;
        for (int i = 1, last = 0; i < (1 << n); i++)
            if (vis[i] == false)
                vis[i ^ x] = true, seq[++tot] = i ^ last, last = i;
        printf("%d\n", tot);
        for (int i = 1; i <= tot; i++)
            printf("%d ", seq[i]);
    }
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注