題目鏈接：http://codeforces.com/contest/842/problem/D

?

題解：像這種求一段異或什么的都可以考慮用字典樹而且mex顯然可以利用貪心+01字典樹，和線段樹差不多就是比較節點總數和有的數字數比較有限向左邊轉移。

然后這個異或其實可以利用一個數num與一個一個的x異或然后求異或的mex也是容易的只要判斷當前二進制位是1那么左右節點擁有的數字數互換（不用真的互換

只要用轉移體現出來就行了）。這里的01字典樹寫法是類似線段樹且利用遞歸的方法。

#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int M = 2e5 + 10; int ch[20 * M][2] , nodes[20 * M]; int node_size , num; void build(int pos , int node) {if(pos < 0) return;for(int i = 0 ; i < 2 ; i++) {ch[node][i] = ++node_size;nodes[node_size] = 0;build(pos - 1 , ch[node][i]);} } void init() {node_size = 0;nodes[0] = 0;build(19 , 0); } void Insert(int node , int x , int pos) {if(pos < 0) {nodes[node] = 1;return ;}int id = (x >> pos) & 1;Insert(ch[node][id] , x , pos - 1);nodes[node] = nodes[ch[node][id]] + nodes[ch[node][id ^ 1]]; } int query(int node , int x , int pos) {if(pos < 0) return x;int gg = (num >> pos) & 1;if(nodes[ch[node][gg]] < (1 << pos)) return query(ch[node][gg] , x , pos - 1);return query(ch[node][gg ^ 1] , x | (1 << pos) , pos - 1); } int main() {int n , m , x;num = 0;init();scanf("%d%d" , &n , &m);for(int i = 0 ; i < n ; i++) {scanf("%d" , &x);Insert(0 , x , 19);}for(int i = 0 ; i < m ; i++) {scanf("%d" , &x);num ^= x;printf("%d\n" , query(0 , 0 , 19));}return 0; }

?

轉載于:https://www.cnblogs.com/TnT2333333/p/7513807.html

總結

以上是生活随笔為你收集整理的codeforces 842 D. Vitya and Strange Lesson（01字典树+思维+贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。