CodeForces 979D Kuro and GCD and XOR and SUM 【01字典树】

发表于 | 更新于 | 分类于

题目大意：

现在要对一个数组执行q次指令，指令有两种类型，分别为”1 x”和”2 x k s”，前一种是向数组中加一个数x，后一种是查询数组中是否存在这样一个v，使得v满足$k \mid \gcd(x, v) , x + v < s$, 若不存在，输出-1，否则输出满足条件的v中值最大的那个。

解题思路：

首先观察条件，很明显的当$x \mod k \neq 0$时，答案是-1， 当$s - x \leq 0$时，答案是-1。
对于其余情况，因为插入的数在1 ~ $10^5$间，而且用到这个数只要它出现过就可以，与它出现的次数无关。所以我们可以用桶排序的思想，用一个数组标记这个数字是否出现过。对于给出的查询，我们只需从k开始找，到$s - x$为止，每次加k，看枚举的数是否出现过，同时更新记录最大值就OK了。
然而这样会T。因为当k = 1时，这样做就和暴力无差了。那么我们怎么办呢？k = 1，就是从1 ~ $s - x$中找出一个数使得这个数与x的异或结果最大。没错，就是区间异或最大值！字典树！
前两篇讲的是没有最大值限制的查询，这里有了限制也很简单，我们把之前用的这一位是0|1的pre数组改为到此结点时最小值是多少，然后从根结点开始往下搜索，最后返回叶子结点存的值就好了。为什么这样是对的？因为我们往下找的时候是根据异或结果找的，找到叶子结点时当然就是最大的了。对了，往下找的时候要多加一句判断——是否下面的最小值不大于我们的限制。

Mycode：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e5+5;

int t, x, k, s, maxx, op, a[MAX];
struct Trie
{
    int nex[MAX * 17][2], o[MAX * 17], tot;
    void init()
    {
        tot = 1;
        memset(o, 0x3f, sizeof(o));
        memset(nex, 0, sizeof(nex));
    }
    void add()
    {
        int now = 1;
        o[now] = min(o[now], x);
        for(int i = 17; i >= 0; --i)
        {
            if(nex[now][(x >> i) & 1] == 0)
                nex[now][(x >> i) & 1] = ++tot;
            now = nex[now][(x >> i) & 1];
            o[now] = min(o[now], x);
        }
    }
    int query()
    {
        if(o[1] > maxx)    return -1;
        int now = 1;
        for(int i = 17; i >= 0; --i)
        {
            if(nex[now][((x >> i) & 1) ^ 1] && o[nex[now][((x >> i) & 1) ^ 1]] <= maxx)
                now = nex[now][((x >> i) & 1) ^ 1];
            else
                now = nex[now][(x >> i) & 1];
        }
        return o[now];
    }
}trie;

int main()
{
    trie.init();
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d", &x);
            trie.add();
            a[x] = true;
        }
        else
        {
            scanf("%d%d%d",&x,&k,&s);
            maxx = s - x;
            if(x % k)
                puts("-1");
            else if(k == 1)
                printf("%d\n", trie.query());
            else
            {
                int maxxor = -1, res = -1;
                for(int i = k; i <= maxx; i += k)
                {
                    if(a[i] && (i ^ x) > maxxor)
                    {
                        res = i;
                        maxxor = i ^ x;
                    }
                }
                printf("%d\n", res);
            }
        }
    }
    return 0;
}
Donate comment here
0%