CF842D Vitya and Strange Lesson

|

01trie真是个可爱的算法呢!

传送门

差不多是01trie的模板吧。

所谓01trie,就是把我们平时处理字符串的普通trie树边的信息改为一个数字二进制下这一位是0还是1。

这样就可以将一个数字变成一个01串存下来,做一些ans,or,xor之类的二进制操作。

本题要求序列在xor一个数下的mex,正常求mex的方法是在值域上建树,如果左子树不满就走向左子树,否则走向右子树。

同理,在trie里计一下数的个数就好了。

一些细节:不用把满二叉树建出来,找到一个不存在的节点直接默认我们之后的位上全是0,return好了。

我的代码有一些奇怪的小优化,可能不太好懂。

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
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t[6000005][2],k,n,maxn,num;
int c[300005],sum[600005][2],m;
inline void insert(int x){
int u=1;
for (int i=maxn; i>=0; i--){
int a=((x&(1<<i))!=0);
if (!t[u][a]) t[u][a]=++num;
sum[u][a]++;u=t[u][a];
}
}
inline int query(){
int u=1,ans=0;
for (int i=maxn; i>=0; i--){
int a=((k&(1<<i))!=0);
if (sum[u][a]<(1<<i)){
u=t[u][a]; if (!u) return ans;
}
else{
u=t[u][a^1];
ans|=(1<<i); if (!u) return ans;
}
}
return ans;
}
int main(){
int x;
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) scanf("%d",&c[i]);
sort(c+1,c+n+1);
maxn=min((int)log2(c[n])+1,20);
if (c[n]==0) maxn=1;
num=1; c[0]=-1;
for (int i=1; i<=n; i++)
if (c[i]!=c[i-1]) insert(c[i]);
while (m--){
scanf("%d",&x);
k^=x; printf("%d\n",query());
}
return 0;
}
文章目录
,
载入天数...载入时分秒... 字数统计:75.7k