当前位置: 代码迷 >> 综合 >> 【CodeForces - 706D 】Vasiliy's Multiset(字典树、贪心)
  详细解决方案

【CodeForces - 706D 】Vasiliy's Multiset(字典树、贪心)

热度:82   发布时间:2023-12-06 19:31:27.0

题意:

3个操作,集合初始有元素0,集合中可以有重复元素。1、往集合中加入1个元素。2、从集合中删除一个元素。3、求给定数x与集合中某个元素异或的最大值。

思路:

将集合内的元素建立字典树,查询时,贪心选择与给定x当前位不同的。

 

ac代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#include<unordered_map>
#define mod (1000000007)
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
const ll inf = 1e14;
unordered_map<int,int> mp;
int nxt[maxn*32][2],cnt=0,num[maxn*32][2];
void add(int x){mp[x]++;if(mp[x]==1){int now=0;for(int i=30;i>=0;i--){int tmp=((1ll<<i)&x)>0?1:0;if(nxt[now][tmp]==-1)nxt[now][tmp]=++cnt;num[now][tmp]++;now=nxt[now][tmp];}}
}
void del(int x){mp[x]--;if(mp[x]==0){int now=0;for(int i=30;i>=0;i--){int tmp=((1ll<<i)&x)>0?1:0;if(num[now][tmp]==1) {num[now][tmp] = 0;nxt[now][tmp] = -1;break;}num[now][tmp]--;now=nxt[now][tmp];}}
}//1000 011 1001
ll query(int x){ll res=0;int now=0;for(int i=30;i>=0;i--){int tmp=((1ll<<i)&x)>0?1:0;if(nxt[now][tmp^1]!=-1) {res|=((tmp^1)<<i);now=nxt[now][tmp^1];}else{res|=(tmp<<i);now=nxt[now][tmp];}}return max(1ll*x,x^res);
}
int main() {char op[5];int q,x;scanf("%d",&q);memset(nxt,-1, sizeof(nxt));memset(num,0, sizeof(nxt));add(0);while(q--){scanf("%s%d",op,&x);if(op[0]=='+'){add(x);}else if(op[0]=='-'){del(x);}else{printf("%lld\n",query(x));}}return 0 ;
}