当前位置: 代码迷 >> 综合 >> Codeforce#430D.Vitya and Strange Lesson(01Trie)
  详细解决方案

Codeforce#430D.Vitya and Strange Lesson(01Trie)

热度:83   发布时间:2023-12-06 19:27:08.0

题意:

每次询问一个x,问数组中的数与x异或后,不存在的最小的数。

分析:

01字典树上贪心选择一下,选择的时候判断左孩子和右孩子满不满。每次询问的亦或值x只要一直累?就行

#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define H 19
bool vis[N];
struct node
{node *nxt[2];int sz;node(){sz=0;nxt[0]=nxt[1]=NULL;}
};
void Insert(node *rt, int x)
{for(int i=H; i>=0; i--){int id=(x>>i)&1;if(rt->nxt[id]==NULL) rt->nxt[id]=new node();rt=rt->nxt[id];rt->sz++;}
}
int getsz(node *p)
{if(p==NULL) return 0;return p->sz;
}
int query(node *rt, int X, int h)
{if(rt==NULL) return 0;if((X>>h)&1){if(getsz(rt->nxt[1])!=(1<<h)) return query(rt->nxt[1], X, h-1);else return query(rt->nxt[0], X, h-1)+(1<<h);}else{if(getsz(rt->nxt[0])!=(1<<h)) return query(rt->nxt[0], X, h-1);else return query(rt->nxt[1], X, h-1)+(1<<h);}
}void solve()
{node *rt=new node();int n, m, X=0;cin>>n>>m;for(int i=1; i<=n; i++){int x;cin>>x;if(!vis[x]) Insert(rt, x), vis[x]=1;}while(m--){int x;cin>>x;X^=x;cout << query(rt, X, H) << endl;}
}
int main()
{solve();return 0;
}


  相关解决方案