NEFU 1248 智力异或(字典树)

本文主要是介绍NEFU 1248 智力异或(字典树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有一个数列包含n个正整数a[1]~a[n]（1<=n<1e5,0<=a[i]<1e9）,现在有q次操作(q<1e5)，每次操作是以下两种操作中的一种：1、输入x，对这n个数分别异或x；2、输入x，求数列中的某个数与x异或的最大值（即从数组中找一个数，使其与x异或值最大）；

第一行为T，表示有T（T<=10）组数据，每组数据的第一行为n和q，表示这个数列长为n，q次操作。然后输入这n个数。接下来,每次操作输入一行两个数op（op为1或者2）和x（0<=x<1e9），op=1表示进行操作1，op=2表示进行操作2；

每次进行操作2时，用一行输出最大的异或值；

1
4 3
6 7 5 4
1 3
2 4
2 5

3
3

CJJ

思路：
建一棵字典树，里面存的是从高位到低位的二进制。因为在查询的时候，高位的影响更大，所以应该优先考虑高位，把高位放在前面。

在进行op1操作时候，并不用遍历字典树将所有数都与x异或。只需要存下一个y=0来与x异或就行。因为它们在op1过程中中间改变的(a^b^...^z)是一定的，只需要用y来记录下来再进行op2操作时候传入x^y就相当于那棵树上的所有节点已经完成了之前op1的操作。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
int cnt,root;
struct node
{int next[2];
}q[40*maxn];
void in(int root,int n)
{for(int i=30;i>=0;i--){int x=(n>>i)&1;if(q[root].next[x]==0){q[root].next[x]=++cnt;}root=q[root].next[x];}
}
int query(int root,int n)
{int ans=0;for(int i=30;i>=0;i--){ans<<=1;int x=(n>>i)&1;if(q[root].next[!x]!=0){ans=ans|(!x);root=q[root].next[!x];}else{ans=ans|x;root=q[root].next[x];}}return ans^n;
}
int main()
{int t,n,qq,x,o,y;scanf("%d",&t);while(t--){y=0,cnt=0,root=0;memset(q,0,sizeof(q));scanf("%d%d",&n,&qq);for(int i=1;i<=n;i++){scanf("%d",&x);in(root,x);}for(int i=1;i<=qq;i++){scanf("%d%d",&o,&x);if(o==1){y^=x;}else{printf("%d\n",query(root,y^x));}}}return 0;
}

这篇关于NEFU 1248 智力异或(字典树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！