【鏈接】點(diǎn)擊打開鏈接

【題意】

給出一個(gè)數(shù)組，每次操作將整個(gè)數(shù)組亦或一個(gè)數(shù)x，問(wèn)得到的數(shù)組的結(jié)果中的mex.mex表示為自然數(shù)中第一個(gè)沒有出現(xiàn)過(guò)的數(shù)。

【題解】

異或的效果是可以累加的,所以不用每次都算出來(lái)每一次的a是什么。而只要把前i個(gè)詢問(wèn)的x取一下異或和now,然后用異或和對(duì)每個(gè)ai異或就可以了。 對(duì)于這道題.我們需要用字典樹來(lái)做. 對(duì)于一開始的a數(shù)組中沒有出現(xiàn)的數(shù)字,都把它按照位加入到字典樹中,最多19位。 設(shè)原數(shù)組是a,然后沒出現(xiàn)的數(shù)字組成數(shù)組A. 結(jié)論:則我們對(duì)原數(shù)組進(jìn)行一次異或操作即a xor 了x,則異或之后的a數(shù)組的mex值就是A數(shù)組也xor x之后的最小值。 感性的證明: 假設(shè)進(jìn)行了一次異或操作. 則,相當(dāng)于把每個(gè)數(shù)字的二進(jìn)制形式中的一些1翻轉(zhuǎn)成了0,而0翻轉(zhuǎn)成了1,就是x的二進(jìn)制中為1的那些位置都進(jìn)行了翻轉(zhuǎn)操作,那么假如數(shù)字t沒有出現(xiàn)過(guò),則進(jìn)行了一次異或操作之后,t可能就出現(xiàn)了,而t xor x可能就沒有出現(xiàn)了,則我們就直接認(rèn)為t出現(xiàn)了,而t xor x變成沒有出現(xiàn)的了. 可以這么做是因?yàn)?如果t xor x也是沒有出現(xiàn)的話,它也會(huì)對(duì)x進(jìn)行異或操作,則也會(huì)認(rèn)為t是沒有出現(xiàn)的,這樣之前認(rèn)為t出現(xiàn)過(guò)的錯(cuò)誤結(jié)論就能得到訂正,這樣就不會(huì)造成錯(cuò)解了,t 和 t xor x還是都沒出現(xiàn)的。 而如果沒有出現(xiàn)的數(shù)字里面沒有t xor x的話,那就說(shuō)明原數(shù)組里面有t xor x這個(gè)數(shù)字,則進(jìn)行異或操作之后還是會(huì)有t這個(gè)數(shù)字,則之前的結(jié)論也就對(duì)了,而進(jìn)行了異或操作之后 t xor x也就變成沒有出現(xiàn)過(guò)的了。 也就是說(shuō),A里面的數(shù)字,xor之后還是沒有出現(xiàn)的.且只有這些數(shù)字是沒有出現(xiàn)的。
這樣就感性地解釋了那個(gè)結(jié)論. 那么現(xiàn)在的問(wèn)題就變?yōu)?給你一個(gè)數(shù)字X,然后讓你在A里面找一個(gè)數(shù)字,然后Ai和X的異或值最小. 則我們從高位開始,盡量讓Ai的位和X的對(duì)應(yīng)位一樣(異或結(jié)果就變成0),這樣高位就盡量小了。 字典樹的作用就在此。

【錯(cuò)的次數(shù)】

1

【反思】

反面去考慮問(wèn)題,從中得到結(jié)論. 二進(jìn)制的問(wèn)題好多和字典樹有關(guān)呢。 那個(gè)結(jié)論挺難想的。

【代碼】

/**/ #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <map> #include <queue> #include <iomanip> #include <set> #include <cstdlib> #include <cmath> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define pb emplace_back #define fi first #define se second #define ld long double #define ms(x,y) memset(x,y,sizeof x) #define ri(x) scanf("%d",&x) #define rl(x) scanf("%lld",&x) #define rs(x) scanf("%s",x) #define rf(x) scnaf("%lf",&x) #define oi(x) printf("%d",x) #define ol(x) printf("%lld",x) #define oc putchar(' ') #define os(x) printf(x) #define all(x) x.begin(),x.end() #define Open() freopen("F:\\rush.txt","r",stdin) #define Close() ios::sync_with_stdio(0) #define sz(x) ((int) x.size()) #define ld long doubletypedef pair<int, int> pii; typedef pair<LL, LL> pll;//mt19937 myrand(time(0)); //int get_rand(int n){return myrand()%n + 1;} const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 }; const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 }; const double pi = acos(-1.0); const int N = 19;struct node {node *ch[2];int val;node() { ch[0] = ch[1] = NULL; val = 0; } } *root;int n, m, a[N + 10]; bool bo[1 << N];void insert(int x) {node *p = root;rep2(i, (N-1), 0) {int temp = (x >> i) & 1;if (p->ch[temp] == NULL) p->ch[temp] = new node();p = p->ch[temp];}p->val = x; }int query(int x) {node *p = root;rep2(i, (N-1), 0) {int temp = (x >> i) & 1;if (p->ch[temp] == NULL)p = p->ch[temp ^ 1];elsep = p->ch[temp];}return p->val; }int main() {//Open();//Close();root = new node();ri(n), ri(m);rep1(i, 1, n) {int x;ri(x);bo[x] = 1;}rep1(i, 0, (1 << N)-1) if (!bo[i])insert(i);int now = 0;rep1(i, 1, m) {int x;ri(x);now ^= x;oi(now^query(now)); puts("");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AWCXV/p/7626069.html

總結(jié)

以上是生活随笔為你收集整理的【Codeforces Round #430 (Div. 2) D】Vitya and Strange Lesson的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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