说在前面的

我希望以后的每日一题也是以小专题出现的,我觉得这样的练习效果才好。而且题有点少,并且有很多重复。例如 解决异或和,权值 ,合并 没有出现,有点小伤心。牛客工作人员找了这么多的例题真的很辛苦。感谢牛客。

异或

异或是一种位运算。满足 。这个比较好理解,大概就是两个数异或,那么在一位上相同的的数变为 ,反之变为

性质

那么异或又满足什么性质呢,个人认为下面的式子非常简单,如果有问题可以私聊。

  • 交换率
  • 结合率

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;
}