题解：P10696 [SNCPC2024] 写都写了，交一发吧

· · 题解

P10696 [SNCPC2024] 写都写了，交一发吧 题解

注：本题解做法可能不适合新手，仅仅为适合本题的特殊情况，仅仅在此分享，不喜勿喷。

赛后感受：还行啊，就是字典树嘛，20 分钟搞定。主要是当时我要去上课，只做了一些，等级分亏了……

大概是黄题的难度，具体参考 P10471 最大异或对 The XOR Largest Pair。

题目简述

给定 n 个整数，求任意两个数字（可以是同样的两个数字）按位与运算后的最大值。这样的任务共有 t 组。

思路简述

此题与 P10471 最大异或对 The XOR Largest Pair 相似，可以参考题解：P10471 最大异或对 The XOR Largest Pair。

对，就是我写的哈哈。

正事。

因为是两两按位与，所以朴素算法为 O(n^2) 的暴力枚举，时间肯定超时（4\times 10^{10}）。虽然可以过部分测试点，但是由于比赛是只看完全做对的题目，部分分没用，还会加罚时，所以我当场排除了此思路。

考虑用字典树对其进行优化。

不难想到，因为是按位与，所以可以将其转化为二进制的 01 串，存储在字典树里。

存图方式如下，设我们需要插入数字 3、2、1、0。

我们每次遍历的时候，都会有一个分叉，即继续遍历分支的 0 还是 1。

不难想到，由于是尽可能地让这个值大，所以我们每次都尽量遍历 1，实在不行了，没有 1，再去遍历 0。

字典树：

具体介绍可参考我发的博客（上文），这里不再啰嗦，直接讲代码实现。

用一个结构体来表示字典树的每个节点，每个结构体存一个数组，仅存 0 或 1：

struct NODE{
    int son[2];//代表分支
}node[20000005];//众所周知，字典树的长度很玄学

将一个数字插入：

void insert(int num)
{
    now=start;//多测，起始点设一下
    for(int i=30;i>=0;i--)//数字的每个二进制位
    {
        t=(num>>i)&1;//取这位
        if(!node[now].son[t]) node[now].son[t]=++tot;//如果没有此节点，则新建节点，编号为++tot
        now=node[now].son[t];//否则直接走下去
    }
    return ;
}

查询：

int find(int num)
{
    ans=now=start;
    for(int i=30;i>=0;i--)
    {
        t=(num>>i)&1;
        //从这里开始与插入不同
        if(!node[now].son[t&1])//如果不存在该位&1的节点，则只能从此节点继续遍历
            now=node[now].son[t];
        else//否则最开心，按着最优情况遍历
        {
            now=node[now].son[t&1];
            ans=ans&(1<<i);//打擂台
        }
    }
    return ans;
}

别忘了，规则里还有自己与自己也可以相互按位与，所以再添上挨个比较的代码即可：

for(int i=1;i<=n;i++)
            ans=max(ans,find(a[i]));
        for(int i=1;i<=n;i++)
            ans=max(ans,a[i]&a[i]);

最后给个完整代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,T,a[MAXN],now,t,tot,start,ans;
struct NODE{
    int son[2];
}node[20000005];
void insert(int num)
{
    now=start;
    for(int i=30;i>=0;i--)
    {
        t=(num>>i)&1;
        if(!node[now].son[t]) node[now].son[t]=++tot;
        now=node[now].son[t];
    }
    return ;
}
int find(int num)
{
    ans=now=start;
    for(int i=30;i>=0;i--)
    {
        t=(num>>i)&1;
        if(!node[now].son[t&1])
            now=node[now].son[t];
        else
        {
            now=node[now].son[t&1];
            ans=ans&(1<<i);
        }
    }
    return ans;
}
int main(){
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            insert(a[i]);
        }
        for(int i=1;i<=n;i++)
            ans=max(ans,find(a[i]));
        for(int i=1;i<=n;i++)
            ans=max(ans,a[i]&a[i]);
        printf("%d\n",ans);
        start=++tot;
    }
    return 0;
}