题解 P6824 【「EZEC-4」可乐】

· · 题解

提供一个考试时的奇怪做法。

首先显然这个聪明值不会超过 2^{21}=2097152，因为 2a_i<2^{21}。

然后我们考虑一个 naive 的暴力，就是枚举这个范围的每个数，每次暴力统计

显然暴力的瓶颈在于判断是否可行，那我们可以考虑建一个 Trie 来维护二进制的 a_i，判断的时候找 x\oplus k 对应的路径，然后判断如果 k 这一位恰好是 1 就把这一位取反得到的子树的大小全部加进去，正确性是显然的。

复杂度 O(2^{21}\times 21)。

注意题目条件中要求的是 (a_i\oplus x)\le k，我们需要在 query 的末尾特判一下，不然会被

5 10
4
1
14
13
13

这组数据给叉掉。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,k,ans,a[N],cnt[2];
int tot,sz[N*21],trie[N*21][2];
void insert(int x){
    int p=0;
    for(int k=21,c;k>=0;k--){
        c=(x>>k)&1;
        if(!trie[p][c])trie[p][c]=++tot;
        p=trie[p][c];
        sz[p]++;
    }
}
int query(int x){
    int ret=0,p=0;
    bool flag=0;
    for(int i=21,c;i>=0;i--){
        c=(x>>i)&1;//x这一位的值
        int t=(k>>i)&1;//k这一位的值
        if(t==1)ret+=sz[trie[p][1-(c^t)]];//如果k这一位的值是1，那么这一位取1-(c^t)的时候一定可行，反之一定不可行
        if(!trie[p][c^t]){flag=1;break;}//如果走不到就返回
        p=trie[p][c^t];
    }
    if(!flag)ret+=sz[p];
    return ret;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),insert(a[i]);
    for(int i=0;i<2097152;i++){
        ans=max(ans,query(i));
        if(ans==n)break;
    }
    printf("%d\n",ans);
    return 0;
}