「2017 山东一轮集训 Day1」Set

题目大意

给出 n 个非负整数,将数划分成两个集合,记为一号集合和二号集合。x1 为一号集合中所有数的异或和,x2 为二号集合中所有数的异或和。在最大化 x1+x2 的前提下,最小化 x1 。

输入格式

一个n 然后跟着n个10^18内的整数

输出格式

一个数字:x1

样例输入

8
1 1 2 2 3 3 4 4

样例输出

7

解题报告

令A为所有数字xor和。

考虑A的每一位

  • 如果为1,则表示不管怎么分,x1和x2中一定有且仅有一个数字这个位置为1,于是我们希望x1这一位是0,对应的x2为1
  • 如果为0,则表示不管怎么分,x1和x2中一定是要么两个数这一位都是1,或者两个数这一位都是0,我们希望x1这一位是1,x2这一位也是1,这样才能最大化x1+x2

我们发现我们对x2的希望很简单:根据优先级来选择1。

于是确定了优先级就可以线性基了。

0高>0低>1高>1低

我的代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, b[64], p[64], tot, a[100005];
int main() {
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    LL ans = 0;
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", a + i);
        ans ^= a[i];
    }
    for (int i = 0; i < 64; ++i)
        if (ans >> i & 1)
            p[tot++] = i;
    for (int i = 0; i < 64; ++i)
        if (!(ans >> i & 1))
            p[tot++] = i;
    for (int i = 1; i <= n; ++i) {
        for (int jj = 63; jj >= 0; --jj) {
            int j = p[jj];
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int kk = jj - 1; kk >= 0; --kk) {
                        int k = p[kk];
                        if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
                    }
                    for (int kk = jj + 1; kk < 64; ++kk) {
                        int k = p[kk];
                        if (b[k] >> j & 1) b[k] ^= b[j];
                    }
                    break;
                }
            }
        }
    }
    for (int i = 0; i < 64; ++i) ans ^= b[i];
    printf("%lld", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据