P6824 「EZEC-4」可乐

题目背景

很久以前，有一个 pigstd，非常迷恋美味的可乐。为了得到美味的可乐，他几乎用尽了所有的钱，他甚至对自己的 npy 也漠不关心其实是因为他没有npy，更不爱好看戏。除非买了新可乐，才会坐上马车出门炫耀一番。每一天，每个钟头他都要喝上一瓶新可乐。

pigstd 最近又买了许多箱新可乐——当然，这些可乐只有聪明的人才能喝到。

题目描述

pigstd 现在有 $n$ 箱可乐，第 $i$ 箱可乐上标着一个正整数 $a_{i}$。

若 pigstd 的聪明值为一个非负整数 $x$，对于第 $i$ 箱可乐，如果 $(a_{i} \oplus x )\le k$，那么 pigstd 就能喝到这箱可乐。

现在 pigstd 告诉了你 $k$ 与序列 $a$，你可以决定 pigstd 的聪明值 $x$，使得他能喝到的可乐的箱数最大。求出这个最大值。

输入格式

第一行两个由空格分隔开的整数 $n,k$。

接下来 $n$ 行，每行一个整数 $a_i$，表示第 $i$ 箱可乐上标的数。

输出格式

一行一个正整数，表示 pigstd 最多能喝到的可乐的箱数。

输入输出样例 #1

输入 #1

1
2
3
4
3 5
2
3
4

输出 #1

1
3

输入输出样例 #2

输入 #2

1
2
3
4
5
4 625
879
480
671
853

输出 #2

1
4

说明/提示

提示

pigstd 的聪明值 $x$ 可以为 $0$。

样例解释

样例 1 解释：容易构造当 $x = 0$ 时，可以喝到所有可乐。

样例 2 解释：容易构造 $x = 913$，可以喝到所有可乐。

样例解释未必是唯一的方法。

数据范围

本题采用捆绑测试。

  • Subtask 1（29 points）：$1 \le n,k,a_{i} \le 1000$。

  • Subtask 2（1 points）：$a_{i} \le k$。

  • Subtask 3（70 points）：无特殊限制。

对于所有数据，保证 $1 \le n,k,a_{i} \le 10^6$。

$\oplus$ 代表异或，如果您不知道什么是异或，请单击这里。

题解

基本思想就是从高到低根据a和k二进制对应位上的1数选择x的对应位是0/1
假设有一个b数组，b[i]表示当x=i时，能喝到的可乐箱数，初始状态为0
下面来看看x每一位上的选择对b数组的影响（用ki表示k的第i位）
如果ki=1
如果xi=ai, 则后面x的所有位任取 这时合法的x取值对应一个区间，b[该区间]都+1
else xi=!ai, 则继续选择后面x的每一位
else ki=0
只有一种可能，xi = !ai，且后面x每一位仍需继续斟酌
按照以上方法最后得到一个x, 这个x也符合情况 这时b[x]++
（另外我们容易发现进行区间修改之后不用再决定下一位，这意味着我们修改当前位时，前面决定出的x所有位与a对应位的异或结果都等于k的对应位）

以上过程中我们需要对b数组进行区间修改，而在最后得到答案时，我们需对b进行多个单点查询

单点查询+区间修改->我们可以使用差分数组与前缀和很快的实现数据的修改与查询

注意

递推到最终才得到的x也是符合情况的，也需要在差分数组中修改对应点的值！！！如果只记得在循环过程中进行区间修改，容易落下这个操作##

容易知道最后得到的这个x与a异或的结果等于k

ACcode

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 <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k;
int a, c[2*N]; // c为差分数组，索引为x的可能取值
int ans, maxx;
int s1[50], s2[50];
void Find(int v) {
    int tmp = 0;
    for(int i=20; i>=0; i--) { // 第i位情况
        int ai = (v>>i) & 1;
        int ki = (k>>i) & 1;
        if(ki) {
            // 如果xi=ai, 则后面任取，一个区间内的x取值对应的结果都+1
            // 易知此处为区间修改，想到差分数组
            int l = tmp + (1<<i) * ai;
            int r = l + (1<<i);
            maxx = max(maxx, r);
            c[l]++, c[r]--;
            // 如果xi=!ai, 则后面每一位还要继续选择
            tmp += (!ai) << i;
        }
        else {
            tmp += ai << i; // 继续选择后面的位数
        }
    }
    // 最后选完每一位得到的tmp也是符合题意的，记得修改区间！！！
    c[tmp]++, c[tmp+1]--;
}
int main() {
    cin >> n >> k;
    for(int i=1; i<=n; i++) {
        cin >> a;
        Find(a);
    }
    for(int i=0; i<=maxx; i++) {
        if(i>=1) c[i] += c[i-1];
        ans = max(ans, c[i]);
    }
    cout << ans << endl;
    return 0;
}