提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  数据库

当前栏目

01字典树

输出 数组 数据
2023-04-22 10:58:16 时间

1. 两个数异或最大

先做一个入门题：传送门

给定的 n个数中选出两个来异或，得到的结果最大是多少？

输入格式
第一行输入一个整数N。

第二行n个数

输出格式
输出一个整数表示答案。

数据范围

输入样例：
3
1 2 3
输出样例：
3

我们就是构建一个01字典树，就是再查询的时候，p=(x>>i)&1,如果有t[root][!p]就让他走t[root][!p]并加上对于的权值,
否者就做t[root][p]

code 
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=4e6+100;
int a[maxn];
int t[maxn][3];
int cnt[maxn];
int idx;
void insert(int x){
    int root=0;
    for(int i=30;i>=0;i--){
        int p=(x>>i)&1;
        if(!t[root][p]){
            t[root][p]=++idx;
        }
        root=t[root][p];
        cnt[root]++;
    }
}
int query(int x){
    int ans=0;
    int root=0;
    for(int i=30;i>=0;i--){
        int p=(x>>i)&1;
        if(t[root][!p]){
            ans+=(1<<i);
            root=t[root][!p];
        }
        else{
            root=t[root][p];
        }
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    insert(a[1]);
    for(int i=2;i<=n;i++){
        ans=max(ans,query(a[i]));
        insert(a[i]);
    }
    printf("%d",ans);
}

2. 异或奶牛问题

传送门

农夫约翰在给他的奶牛们喂食时遇到了一个问题。

他共有 N 头奶牛，编号1-N。每次喂食前，这 N 头奶牛会按照 1-N的顺序站成一排。

此外，每头奶牛都被分配了一个可能不唯一的整数。

那么所有被分配的整数就形成了一个长度为 N 的整数序列。

请你在该整数序列中找出一个连续的非空子序列，使得子序列中元素的异或和能够最大。

如果存在多个这样的序列，那么选择序列末端整数对应的奶牛编号更小的那个序列。

如果仍然存在多个可选的序列，那么选择长度最短的那个序列。

输入格式
第一行包含整数 N。

第2-N 行，每行包含一个整数，其中第i 行的整数表示编号为 i 的牛被分配的整数值。

输出格式
输出三个整数，分别表示最大的异或和，所选序列首端整数对应的奶牛编号，所选序列末端整数对应的奶牛编号。

数据范围

这个题的题意就是在一个序列中选一段连续的子序列，使得其异或起来最大
这个用的知识是前缀和，令sum[i]=(a[1] ^ a[2] ^ a[3]......a[i])，就是
求一段区间[l,r]的前缀和就是sum[r] ^ sum[l-1],为什么可以这样呢，因为x^x=0;
然后问题就转化为在1到n中找两个值sum[i]和sum[j]使其异或起来最大，
就是这样。
代码待更新

3.连续异或最大子段

给定一个非负整数数列 a，初始长度为 N。

请在所有长度不超过 M 的连续子数组中，找出子数组异或和的最大值。

子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

输入格式
第一行包含两个整数 N,M。

第二行包含 N 个整数，其中第 i 个为 ai。

输出格式
输出可以得到的子数组异或和的最大值。

数据范围
对于 20% 的数据，1≤M≤N≤100
对于 50% 的数据，1≤M≤N≤1000
对于 100% 的数据，1≤M≤N≤105,0≤ai≤231−1
输入样例：
3 2
1 2 4
输出样例：
6

这个题和上一个基本上是一样的，就就是这个多了一个m,就是在你到i的时候你要删除(i-m-1)之前的，
对于这个删除操作的话，就是你可以用一个数组标记这个节点有几个数，就是加点的时候让cnt[p]++，删点的时候
让cnt[p]--,然后判断的时候判断cnt[t[root][!op]就行

code 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=3e6+100;
int t[maxn][2];
int a[maxn];
int sum[maxn];
int cnt[maxn];
int idx;
void add(int x,int v){
    int root=0;
    for(int i=30;i>=0;i--){
        int op=(x>>i)&1;
        if(!t[root][op]) t[root][op]=++idx;
        root=t[root][op];
        cnt[root]+=v;
    }
}
int query(int x){
    int root=0;
    int sum=0;
    for(int i=30;i>=0;i--){
        int op=(x>>i)&1;
        if(cnt[t[root][!op]]){
            sum+=(1<<i);
            root=t[root][!op];
        }
        else{
            root=t[root][op];
        }
    }
    return sum;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]^a[i];
    }
    int ans=0;
    add(sum[0],1);
    for(int i=1;i<=n;i++){
        if(i>m) add(sum[i-m-1],-1);
        ans=max(ans,query(sum[i]));
        add(sum[i],1);
    }
    printf("%lld",ans);
}

相关文章