Binary Spiders

2022-02-05

字数统计: 979字 | 阅读时长≈ 4分

题目大意

给定$n(2 \le n \le 3\times10^5)$个数$a_i(0 \le k \le 2^{30}-1))$和自然数$k(0 \le a_i \le 2^{30}-1)$，挑出尽可能多的数，并且使得它们的疑惑和不小于$k$，输出数量和挑选的数。

题目链接 ## 思路首先需要推出一个非常重要的结论:

从$n$个数中挑出两个数，使得它们的异或和最小，那么这两个数一定是把这$n$个数排序后相邻的数。

证明:假设有三个数$a < b < c$:

$a \oplus c < b \oplus c$，那么我们比较一下$b,c$，二进制下从最高位往低位找，出现的第一个不同的位数，因为$a < b < c$,所以这一位肯定是$c$这一位为$1$,$a,b$这一位为$0$。所以即可推出$a \oplus b < a \oplus c$
$a \oplus c > b \oplus c$,我们只需要比较一下$ a b,b c$即可，最小值还是出现在相邻的数中的。

有了这个结论后，我们就可以继续做了，我们把$n$个数从小到大排序后，从小到大遍历。假如我们已经找到了一个集合$s$，我们遍历到了一个新的数$a_i$,想要判断它能否放入这个集合中，只需判断$a_i \oplus max(s) \ge k$即可，与集合中的其他数没有了关系。

因此，我们设$dp_i$表示以$a_i$为最大值的集合中最多有多少个数，可以得到状态转移方程$dp_j = max(dp_i) + 1,$ 其中 $a_j \oplus a_i \ge k$。

同时题目让我们输出每个被选中的数，所以我们在更新$dp_j$时，要记录下它的值是从哪里继承来的$pre[j] = i$。

但是，直接进行状态转移的时间复杂度是$O(n^2)$，会超时，由于是异或操作，我们想到用$trie$树来进行加速。

从最高位开始往树中插入。

我们遍历到了$a_i$,那么为了找到异或和大于$k$的数，我们需要这么寻找: 设二进制下$a_i$这一位为$bit$,root为当前节点。

如果这一位$k$为$1$,那么我们只能往$trie[root][bit\oplus 1]$
如果这一位$k$为$0$,那么我们有两种选择，选择$trie[root][bit\oplus 1]$，那么异或和就一定大于$k$了，所以就没必要继续了，直接更新答案。或者选择$trie[root][bit]$，继续往下寻找更新答案。

更新完$dp_i$后，我们把$a_i$插入树中，同时我们需要更新$f[root]$，表示经过这个点的数中，集合最大的数是多少。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 3e5 + 5;

struct Num {
    int val, index;
}a[maxN];

bool cmp(Num x, Num y)
{
    return x.val < y.val;
}

int n, k, pre[maxN * 31], trie[maxN * 31][2], f[maxN * 31], d[maxN * 31], cnt = 1;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i].val);
        a[i].index = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1; i <= n; ++i) {
        int ans = 0, root = 1;
        for(int j = 30; j >= 0 && root; --j) {
            int bit = (a[i].val >> j) & 1, rev = bit ^ 1;;
            if((k >> j) & 1)
                root = trie[root][rev];
            else {
                if(d[ans] < d[f[trie[root][rev]]])
                    ans = f[trie[root][rev]];
                root = trie[root][bit];
            }
            if(j == 0 && d[ans] < d[f[root]])
                ans = f[root];
        }
        d[i] = d[ans] + 1; pre[i] = ans; root = 1;
        for(int j = 30; j >= 0; j--) {
            int bit  = (a[i].val >> j) & 1;
            if(!trie[root][bit])
                trie[root][bit] = ++cnt;
            root = trie[root][bit];
            if(d[f[root]] < d[i])
                f[root] = i;
        }
    }
    int ans = 1;
    for(int i = 2; i <= n; ++i)
        if(d[ans] < d[i])
            ans = i;
    if(d[ans] < 2)
        printf("-1\n");
    else {
        printf("%d\n", d[ans]);
        for(int i = ans; i != 0; i = pre[i])
            printf("%d ", a[i].index);
    }
    return 0;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2022/02/05/Codeforces-1625-D/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！