題目鏈接：點擊查看

題目大意：給出一個正整數(shù)n，初始時有一個multiset，接下來有n次操作，實現(xiàn)所有操作，對于每個操作，會有三種形式：

+ x：向集合中添加一個 x

- x：從集合中刪掉一個 x

? x：從集合中選出一個數(shù)k，使得 k xor?x 的結(jié)果最大，輸出這個結(jié)果

題目分析：因為需要讓異或值最大，那么顯然就是要用01字典樹處理了，使用字典樹遇到的問題是如何在字典樹中刪除掉一個數(shù)，其實并不麻煩，我們只需要在每個節(jié)點上多開一個val數(shù)組，用來記錄每個節(jié)點被多少個數(shù)字所公用，若需要刪除某個數(shù)值時，在樹上遍歷一遍這個數(shù)，讓所經(jīng)過的val都減一，如果遍歷到某個節(jié)點，發(fā)現(xiàn)節(jié)點只有當前的數(shù)字所使用時，也就是val[node]=1，這個時候在將val數(shù)組減一之后，順便將其父節(jié)點與當前節(jié)點的連邊也刪除掉，也就是讓trie[pos][to]=0就好了，具體實現(xiàn)可以看代碼，剩下的就是01字典樹的模板題了

有一個小細節(jié)可以注意一下，為了加快代碼的運行速度，字典樹中完全可以只儲存種類，開一個無序map儲存?zhèn)€數(shù)即可，插入和刪除的操作只發(fā)生在第一次添加某個數(shù)字以及最后一次刪掉某個數(shù)字才會與字典樹發(fā)生交互，剩下的改變都只是O(1)改變無序map中的值

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int trie[N*35][2],val[N*35],cnt;//val記錄每個節(jié)點被遍歷過多少次 unordered_map<int,int>mp;void insert(int x) {int pos=0;for(int i=31;i>=0;i--){int to=(x>>i)&1;if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];val[pos]++;} }void erase(int x) {int pos=0;for(int i=31;i>=0;i--){int to=(x>>i)&1;int ppos=pos;//儲存一下父節(jié)點pos=trie[pos][to];val[pos]--;if(!val[pos])//如果后續(xù)節(jié)點空出來了，則刪掉父節(jié)點-當前節(jié)點這條邊trie[ppos][to]=0;} }int serach(int x) {int pos=0,ans=0;for(int i=31;i>=0;i--){int to=(x>>i)&1;if(trie[pos][!to]){pos=trie[pos][!to];ans|=(1<<i);}elsepos=trie[pos][to];}return ans; } int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);insert(0);while(n--){char s[5];int num;scanf("%s%d",s,&num);if(s[0]=='+'){if(!mp[num])insert(num);mp[num]++;}else if(s[0]=='-'){mp[num]--;if(!mp[num])erase(num);}else{printf("%d\n",serach(num));}}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 706D Vasiliy's Multiset(字典树删除操作)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。