抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

AutumnKite's Blog

博客

归档

友链

关于

说说

留言

「LOJ 6060」「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set

This is a picture without description

AutumnKite
题解LOJ

发布于：2019年8月18日
次浏览

LOJ 6060

题解

我们发现，\(x_1\text{ xor }x_2\) 的值是固定的，也就是整个集合的异或和，我们记为 \(s\)。

很显然 \(x_1+x_2\ge s\)，我们把 \(x_1+x_2-s\) 的值叫做“差值”。显然我们需要使差值最大化。

考虑 \(s\) 第 \(i\) 位（从右往左，从 \(0\) 开始标号，下同），若是 \(1\)，则 \(x_1\) 和 \(x_2\) 的这一位上有且仅有一个 \(1\)，那么显然对差值的贡献为 \(0\)；否则，\(x_1\) 和 \(x_2\) 的这一位要么都是 \(0\)，要么都是 \(1\)，显然最好是两个都为 \(1\)，那么会对差值产生 \(2^{i+1}\) 的贡献。

题目同时又规定，需要在最大化 \(x_1+x_2\) 的前提下，最小化 \(x_1\)，也就是要最大化 \(x_2\)。

自然想到线性基。通常我们在线性基中插入、查询时直接从最高位遍历到最低位，因为我们可以认为高位的优先级高于低位。

但是，在本题中，由于要优先最大化差值，所以我们需要先最大化 \(x_2\) 的所有在 \(s\) 中为 \(0\) 的那些位置。

于是，我们在插入、查询时，强制这些位置的优先级高于其他位置，而内部仍然按照从高位到低位的顺序进行遍历。这样就能保证先最大化差值，在这个前提下最大化 \(x_2\)。

代码

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
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
long long read(){
    register long long x = 0;
    register char f = 1, ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f ^= 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    return f ? x : -x;
}
#define N 100005
int n;
long long sum, a[N], b[65], ans;
void insert(long long x){
    for (register int i = 60; ~i; --i)
        if (!(sum >> i & 1))
            if (x >> i & 1){
                if (!b[i]) return b[i] = x, void(0);
                x ^= b[i];
            }
    for (register int i = 60; ~i; --i)
        if (sum >> i & 1)
            if (x >> i & 1){
                if (!b[i]) return b[i] = x, void(0);
                x ^= b[i];
            }
}
int main(){
    n = read();
    for (register int i = 1; i <= n; ++i) a[i] = read(), sum ^= a[i];
    for (register int i = 1; i <= n; ++i) insert(a[i]);
    for (register int i = 60; ~i; --i)
        if (!(sum >> i & 1))
            if (!(ans >> i & 1))
                ans ^= b[i];
    for (register int i = 60; ~i; --i)
        if (sum >> i & 1)
            if (!(ans >> i & 1))
                ans ^= b[i];
    printf("%lld\n", sum ^ ans);
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://autumnkite.github.io/loj6060-sol/

更新于：2020年3月26日

线性基

评论