说在前面的
我希望以后的每日一题也是以小专题出现的,我觉得这样的练习效果才好。而且题有点少,并且有很多重复。例如 解决异或和,权值 ,合并 没有出现,有点小伤心。牛客工作人员找了这么多的例题真的很辛苦。感谢牛客。
异或
异或是一种位运算。满足 。这个比较好理解,大概就是两个数异或,那么在一位上相同的的数变为 ,反之变为 。
性质
那么异或又满足什么性质呢,个人认为下面的式子非常简单,如果有问题可以私聊。
- 交换率
- 结合率
01 Trie
算是 的一种变形。关于 的讲解,为了方便大家,我直接把以前的博客搬过来 这里 ,自我感觉还是不错的。
例题
牛客的例题只有由高到低建树的 ,但是覆盖的非常全面。
- The XOR Largest Pair
异或最大值的模板,算是一个引入。这里讨论最大值。一个数和一个序列中一个数的异或最大值是多少?要支持询问。 - 考虑把序列插入,构建一个 树。那么在询问时,只需要讨论该数的位是 还是 就行了。这样就需要 的预处理, 的询问和修改,为什么是对的。因为异或中我们如果可以满足最高位,那么没有理由不改变最高位,因为 。那么由高位到地位贪心就可以了。
- 奶牛异或
这道题和上一道题没有本质区别,由于我们知道 ,所以我们可以考虑做一次前缀异或和。那么区间操作就变为单点操作了,和上一道就一样了。 - Vitya and Strange Lesson
- 这题就有点不一样了,先说 根据结合率,等价于 。
- 因为我们要求的是 ,那么我们就考虑 到 的数是否全部出现过。那么就变为查询异或最小值了,我们在构建 时要顺便记录 中的元素个数,当一个节点的元素个数填满时,我们是不能考虑的。
- Perfect Security
- 这道题引入了删除操作,如果没有删除操作,这道题就是单纯的求出异或最小值。但是现在要求删除。那么我们在 上再维护一个 标记,表示是否这个节点下还有没有可用元素。那么删除和插入都只会影响一条链。
- Xor-MST
- 考察了一个最小生成树算法 算法,关于这个算法在网上并没有比较好的讲解,这个算法也不是常用的解决 算法,但是在类生成树的题中,这个思想还是挺广泛的。大概意思用一张图来讲解就是加一句话
- 对每个连通块,找到一条与该连通块相连的,且另一端点不在此连通块中的边权最小的边。将所有的这些边都加入最小生成树。重复若干遍上述操作,直到图连通。
- 那么运用在 最小生成树中,我们可以按一位为 划分出两个集合,那么显然两个集合中只有可能出现一条边,而且该边是最小的,那么我们可以枚举一个集合的所有元素,在另一个集合中查询异或最小值,那么我们按高位到低位考虑一次就做完了。
- 最大异或和
- 引入了可持久化 ,我们发现序列操作先转为为异或前缀和的单点操作。那么现在就是考虑 这个区间的中的可用元素有哪些。如果我们知道主席树的操作。那么我们可以类比。给每个前缀构建一个 。那么当两个节点的 做差。如果差还大于 ,那么就可以证明这个还有可以元素。而我们其实没必要对每个前缀都建一个 树,我们只需要修改上一棵树的一条链就可以了(这个可以参见主席树的建树)。那么剩下的就是查询异或最大值的模板了。
代码(按题目讲解顺序给出)
悄悄告诉你,这都是每道题比较短的代码。
#include<bits/stdc++.h> using namespace std; const int N = 2e6 + 100; int ch[N][2],n,rt,size; int read() {int x;scanf("%d",&x);return x;} void ins(int u,int t,int x) { if(t < 0) return; int i = ((x >> t) & 1); if(!ch[u][i]) ch[u][i] = ++size; ins(ch[u][i],t - 1,x); } int ask(int u,int t,int x) { if(t < 0) return 0;int i = ((x >> t) & 1); if(ch[u][!i]) return ask(ch[u][!i],t - 1,x) + (1 << t); return ask(ch[u][i],t - 1,x); } int main() { n = read();int ans = 0;rt = ++size; for(int i = 1,x;i <= n;i++) { x = read();ins(rt,30,x); if(i != 1) ans = max(ans,(ask(rt,30,x))); } cout << ans << endl;return 0; } #include<bits/stdc++.h> using namespace std; int read() {int x = 0;scanf("%d",&x);return x;} const int N = 2e7 + 100; int ch[N][2],n,a[N],id[N]; int Ans1,Ans2 = 1,Ans3 = 1,rt = 1,size = 1; void insert(int u,int t,int x,int Id) { if(t < 0) {id[u] = Id;return;} int i = ((x >> t) & 1); if(!ch[u][i]) ch[u][i] = ++size; insert(ch[u][i],t - 1,x,Id); } int ask(int u,int t,int x) { if(t < 0) return id[u]; int i = ((x >> t) & 1); if(ch[u][!i]) return ask(ch[u][!i],t - 1,x); else return ask(ch[u][i],t - 1,x); } int main() { n = read();a[0] = 0; for(int i = 1;i <= n;i++) a[i] = (a[i - 1] ^ read()); for(int i = 1;i <= n;i++) { insert(rt,22,a[i - 1],i); int x = ask(rt,22,a[i]) - 1; if((a[x] ^ a[i]) > Ans1) {Ans1 = (a[x] ^ a[i]);Ans2 = x + 1;Ans3 = i;} } cout << Ans1 << " " << Ans2 << " " << Ans3 << endl; return 0; } #include<bits/stdc++.h> using namespace std; const int N = 6e6 + 10; int read() {int x;scanf("%d",&x);return x;} int si[N],ch[N][2],size = 1,rt = 1; int n,m,last; void insert(int u,int t,int x) { if(t < 0) {si[u] = 1;return;} int i = (x >> t) & 1; if(!ch[u][i]) ch[u][i] = ++size; insert(ch[u][i],t - 1,x); si[u] = si[ch[u][0]] + si[ch[u][1]]; } int query(int u,int t,int x) { if(t < 0 || u == 0) return 0; int i = (x >> t) & 1; if((1 << t) != si[ch[u][i]]) return query(ch[u][i],t - 1,x); else return query(ch[u][!i],t - 1,x) + (1 << t); } int main() { n = read();m = read(); for(int i = 1,a;i <= n;i++) a = read(),insert(rt,20,a); while(m--) { int x = read();last ^= x; printf("%d\n",query(rt,20,last)); } return 0; } #include<bits/stdc++.h> using namespace std; const int N = 6e6 + 100; int read() {int x;scanf("%d",&x);return x;} int ch[N][2],si[N],size = 1,rt = 1; void insert(int u,int t,int x) { if(t < 0) return; int i = (x >> t) & 1; if(!ch[u][i]) ch[u][i] = ++size; si[ch[u][i]]++;insert(ch[u][i],t - 1,x); } void erase(int u,int t,int x) { if(t < 0) return; int i = (x >> t) & 1; si[ch[u][i]]--;erase(ch[u][i],t - 1,x); } int query(int u,int t,int x) { if(t < 0) return 0; int i = (x >> t) & 1; if(si[ch[u][i]]) return query(ch[u][i],t - 1,x) + (i << t); else return query(ch[u][!i],t - 1,x) + ((!i) << t); } int a[N],b[N]; int main() { int n = read(); for(int i = 1;i <= n;i++) a[i] = read(); for(int i = 1;i <= n;i++) b[i] = read(),insert(rt,30,b[i]); for(int i = 1;i <= n;i++) { int y = query(rt,30,a[i]); printf("%d ",(y ^ a[i])); erase(rt,30,y); } } #include<bits/stdc++.h> using namespace std; #define ll long long int read() {int x;scanf("%d",&x);return x;} const int N = 4e6 + 100; const ll inf = 0x3f3f3f3f3f3f3f3f; int L[N],R[N],a[N],ch[N][2],size = 1,rt = 1,n; void ins(int u,int t,int x,int id) { if(L[u]) L[u] = min(id,L[u]);else L[u] = id; if(R[u]) R[u] = max(id,R[u]);else R[u] = id; if(t < 0) return; int i = ((x >> t) & 1); if(!ch[u][i]) ch[u][i] = ++size; ins(ch[u][i],t - 1,x,id); } ll query(int u,int t,int x) { if(t < 0) return 0; int i = ((x >> t) & 1); if(ch[u][i]) return query(ch[u][i],t - 1,x); else return query(ch[u][!i],t - 1,x) + (1 << t); } ll solve(int u,int t) { if(t < 0) return 0; if(ch[u][0] && ch[u][1]) { ll mi = inf; for(int i = L[ch[u][1]];i <= R[ch[u][1]];i++) mi = min(mi,query(ch[u][0],t - 1,a[i])); return solve(ch[u][0],t - 1) + solve(ch[u][1],t - 1) + (1 << t) + mi; } if(ch[u][0]) return solve(ch[u][0],t - 1); if(ch[u][1]) return solve(ch[u][1],t - 1); } int main() { n = read(); for(int i = 1;i <= n;i++) a[i] = read(); sort(a + 1,a + 1 + n); for(int i = 1;i <= n;i++) ins(rt,31,a[i],i); printf("%lld\n",solve(rt,31)); } #include<bits/stdc++.h> using namespace std; const int N = 4000100; int rt[N],ch[N<<2][2],cnt[N<<2],size = 0,n,m,qz[N]; int read(){int x;scanf("%d",&x);return x;} void ins(int a,int b,int t,int x) { if(t < 0) return; int i = (x>>t)&1; ch[a][i^1] = ch[b][i^1]; ch[a][i] = ++size; cnt[ch[a][i]] = cnt[ch[b][i]] + 1; ins(ch[a][i],ch[b][i],t-1,x); } int qu(int a,int b,int t,int x){ if(t < 0) return 0; int i = (x>>t)&1; if(cnt[ch[b][!i]] > cnt[ch[a][!i]]) return (1<<t)+qu(ch[a][!i],ch[b][!i],t-1,x); return qu(ch[a][i],ch[b][i],t-1,x); } int main() { n = read();m = read(); rt[0] = ++size; ins(rt[0],0,25,0); for(int i = 1;i <= n;i++) { int a = read(); qz[i] = qz[i-1]^a; rt[i] = ++size; ins(rt[i],rt[i-1],25,qz[i]); } for(int i = 1;i <= m;i++) { char ch[5]; scanf("%s",ch); if(ch[0] == 'A') { int b = read(); n++; qz[n] = qz[n-1]^b; rt[n] = ++size; ins(rt[n],rt[n-1],25,qz[n]); } else { int a = read(),b = read(),x = read(); a--;b--; if(a == 0) printf("%d\n",qu(0,rt[b],25,qz[n]^x)); else printf("%d\n",qu(rt[a-1],rt[b],25,qz[n]^x)); } } return 0; }