模板 :
const int Bit = 32;struct Trie{ Trie *ch[2]; LL v; inline void init(){ for(int i=0; i<2; i++) this->ch[i] = NULL; this->v = -1; }};Trie *root;///记得在 main 函数的时候分配空间给 root 并初始化inline void CreateTrie(LL x){ Trie * p = root, *tmp; for(int i=Bit; i>=0; i--){ int idx = (x>>i)&1; if(p->ch[idx] == NULL){ tmp = (Trie *)malloc(sizeof(Trie)); tmp->init(); p->ch[idx] = tmp; }//else //加个权值啥的 p = p->ch[idx]; } p->v = x;///在结尾打上标记，表示这串二进制的十进制表示是多少}LL Query(LL x){ Trie *p = root; for(int i=Bit; i>=0; i--){ int idx = (x>>i)&1; if(p->ch[idx^1]){ p = p->ch[idx^1]; }else p = p->ch[idx]; } return p->v;}inline void DelTrie(Trie *T){ if(T == NULL) return ; for(int i=0; i<2; i++){ if(T->ch[i]){ DelTrie(T->ch[i]); } }free(T);} const int maxn = 100000 + 5; //集合中的数字个数typedef long long LL;int ch[32 * maxn][2]; //节点的边信息LL value[32 * maxn]; //节点存储的值int node_cnt; //树中当前节点个数inline void init(){ //树清空 node_cnt = 1; memset(ch[0],0,sizeof(ch));}inline void Insert(LL x){ //在字典树中插入 X //和一般字典树的操作相同 将X的二进制插入到字典树中 int cur = 0; for(int i = 32;i >= 0;--i){ int idx = (x >> i) & 1; if(!ch[cur][idx]){ memset(ch[node_cnt],0,sizeof(ch[node_cnt])); ch[cur][idx] = node_cnt; value[node_cnt++] = 0; } cur = ch[cur][idx]; } value[cur] = x; //最后的节点插入value}LL Query(LL x){ //在字典树中查找和X异或的最大值的元素Y 返回Y的值 int cur = 0; for(int i = 32;i >= 0;--i){ int idx = (x >> i) & 1; if(ch[cur][idx ^ 1]) cur = ch[cur][idx ^ 1]; else cur = ch[cur][idx]; } return value[cur];}
01字典树是求区间连续的异或和以及异或最大值的有利工具
参考博客 ==>
相关题目 :
题意 : 给出一个数集，然后给出 M 个询问，每个问询是一个数 S ，问你数集中哪个数和 S 异或后的值是最大的
分析 : 模板题
#includeusing namespace std;const int maxn = 100000 + 5; //集合中的数字个数typedef long long LL;int ch[32 * maxn][2]; //节点的边信息LL value[32 * maxn]; //节点存储的值int node_cnt; //树中当前节点个数inline void init(){ //树清空 node_cnt = 1; memset(ch[0],0,sizeof(ch));}inline void Insert(LL x){ //在字典树中插入 X //和一般字典树的操作相同 将X的二进制插入到字典树中 int cur = 0; for(int i = 32;i >= 0;--i){ int idx = (x >> i) & 1; if(!ch[cur][idx]){ memset(ch[node_cnt],0,sizeof(ch[node_cnt])); ch[cur][idx] = node_cnt; value[node_cnt++] = 0; } cur = ch[cur][idx]; } value[cur] = x; //最后的节点插入value}LL Query(LL x){ //在字典树中查找和X异或的最大值的元素Y 返回Y的值 int cur = 0; for(int i = 32;i >= 0;--i){ int idx = (x >> i) & 1; if(ch[cur][idx ^ 1]) cur = ch[cur][idx ^ 1]; else cur = ch[cur][idx]; } return value[cur];}int main(void){ int nCase, n, m; scanf("%d", &nCase); for(int ca=1; ca<=nCase; ca++){ init(); scanf("%d %d", &n, &m); for(int i=0; i
题意 : 在一个数集里面找出三不同的数，使得 ( i + j )^k 最大，并输出这个最大的结果
分析 : 为了达到 i、j、k 三个数都不同的效果，我们需要对01字典树添加上删除操作，只要在结构体里面加上一个标记标识就行了，具体看代码实现，很简单
#include#define LL long longusing namespace std;const int Bit = 32;struct Trie{ Trie *ch[2]; LL v; int pass; inline void init(){ for(int i=0; i<2; i++) this->ch[i] = NULL; this->v = 0; this->pass = 1;///标记 }};Trie *root;inline void RunTrie(LL x, bool isDel){ Trie * p = root, *tmp; for(int i=Bit; i>=0; i--){ int idx = (x>>i)&1; if(!isDel){ if(p->ch[idx] == NULL){ tmp = (Trie *)malloc(sizeof(Trie)); tmp->init(); p->ch[idx] = tmp; }else p->ch[idx]->pass += 1; p = p->ch[idx]; }else{ p->ch[idx]->pass -= 1; p = p->ch[idx]; } } if(!isDel) p->v = x;}LL Query(LL x){ Trie *p = root; for(int i=Bit; i>=0; i--){ int idx = (x>>i)&1; if(p->ch[idx^1] && p->ch[idx^1]->pass > 0){ p = p->ch[idx^1]; }else p = p->ch[idx]; } return (p->v)^x;}inline void DelTrie(Trie *T){ if(T == NULL) return ; for(int i=0; i<2; i++){ if(T->ch[i]){ DelTrie(T->ch[i]); } }free(T);}LL arr[1001];int main(void){ int nCase, n, m; scanf("%d", &nCase); while(nCase--){ root = (Trie *)malloc(sizeof(Trie)); root->init(); scanf("%d", &n); for(int i=0; i
题意 : 在一个本来就包含 0 的数集里面进行三种操作 ' + ' 添加一个数、 ' - ' 删去一个数、' ? ' 数集里面哪两个数的异或值最大，输出
分析 : 跟上一题如出一辙，不过要小心本来就包含 0 这个陷阱
#include#define LL long longusing namespace std;const int Bit = 30;struct Trie{ Trie *ch[2]; LL v; int pass; inline void init(){ for(int i=0; i<2; i++) this->ch[i] = NULL; this->v = -1; this->pass = 1; }};Trie *root;inline void TrieOP(LL x, bool del){ Trie * p = root, *tmp; for(int i=Bit; i>=0; i--){ int idx = (x>>i)&1; if(!del){ if(p->ch[idx] == NULL){ tmp = (Trie *)malloc(sizeof(Trie)); tmp->init(); p->ch[idx] = tmp; }else p->ch[idx]->pass++; p = p->ch[idx]; }else{ p = p->ch[idx]; p->pass -= 1; } } if(!del) p->v = x;}LL Query(LL x){ Trie *p = root; for(int i=Bit; i>=0; i--){ int idx = (x>>i)&1; if(p->ch[idx^1] && p->ch[idx^1]->pass > 0){ p = p->ch[idx^1]; }else p = p->ch[idx]; } return p->v;}inline void DelTrie(Trie *T){ if(T == NULL) return ; for(int i=0; i<2; i++){ if(T->ch[i]){ DelTrie(T->ch[i]); } }free(T);}int main(void){ int nOperator; root = (Trie *)malloc(sizeof(Trie)); root->init(); TrieOP((long long)0, false); scanf("%d", &nOperator); while(nOperator--){ char ch; LL tmp; scanf(" %c", &ch); scanf("%I64d", &tmp); if(ch == '+') TrieOP(tmp, false); else if(ch == '-') TrieOP(tmp, true); else if(ch == '?') printf("%I64d\n", Query(tmp)^tmp); }DelTrie(root); return 0;}