题目描述
给定一个非负整数数列 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
0(nlogn)
思路
先求出前i个数的异或和sum[i],再在大小为m的滑动窗口内进行trie.
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
const int N=31e5+10;//最多有n*31
int p[N][35],ct[N],idx;//ct[n]的作用是标记滑动窗口内0,1的数量
int sum[100010];//sum[i]存前i个数的异或和
void insertt(int u,int c){
int t=0;
for(int i=30;i>=0;i--){
int x=u>>i&1;
if(!p[t][x]){
p[t][x]=++idx;
}
t=p[t][x];
ct[t]+=c;//标记这里(有或删除)一个数可以达到该位置
}
}
int query(int u){
int t=0;
int res=u;
for(int i=30;i>=0;i--){
int x=u>>i&1;
if(ct[p[t][!x]]>0){//当x对面的那个数!x存在时(0,1)
x=(x+1)%2;//x就变成另外一个数 !x
}
res^=x<<i;
t=p[t][x];
}
return res;
}
int main(){
cin>>n>>m;
int t;
for(int i=1;i<=n;i++){
scanf("%d",&t);
sum[i]=sum[i-1]^t;//sum[i]表示前i个数的^
}
insertt(0,1);//插入0,是为了方便前m个数进行异或得出的答案可以是它本身的值
int res=0;//求最大值
for(int i=1;i<=n;i++){
if(i>m) insertt(sum[i-m-1],-1);//将滑动窗口外的数除去,这时就要修改ct,故-1
res=max(res,query(sum[i]));//在滑动窗口内求最大值
insertt(sum[i],1);//求完后记得插入该值,方便后面的值进行异或
}
cout<<res;
return 0;
}
if(ct[p[t][!x]]>0) 我想问一下,这里判断与当前位不同的数是否存在为什么用 ct[p[t][!x]]> 0,而不是先判断p[t][!x] == 0?因为当ct[p[t][!x]] <= 0的时候,可能是p[t][!x] >0 而 p[t][x] = 0,如果沿着x往下走不就错了?
例如当前位是0,在Trie中找对应位的1,如果此时对应的1的数量为0,但p[t][1]不为零,p[t][0]为零,直接判断 if(ct[p[t][!x]]>0) 就直接往p[t][0]走了,这样不是错的吗
为什么删除时时删除s[i - m - 1],而不是s[i - m],从i-m到 i 不是m+1个数吗
同问
因为求i到j的异或和的话,s[i]^s[j-1],然后j-1相当于i-m,但是要删除在j-1的前一个所以就是s[i-m-1]
懂了,感谢🙇
呃呃呃呃呃呃呃
这一句是什么意思呀
res=max(res,query(sum[i]));
为啥是用的 sum[i] 去查询,sum[i] 不也包括了 sum[i - m] 异或的值吗?为啥不是
query(sum[i] - sum[i - m - 1])
res = res * 2 + !u
res = res * 2 + u 这个组合是返回能与x异或得到最大的数 需要继续异或
res = res * 2 + 1;
res = res * 2;这个组合返回的是与x异或的最大值
我懂了,感谢ヾ(•ω•`)o
想问一下,那个idx是起什么作用的,在网上看了trie树另一个题目也有idx,但是也没用到idx,不太懂,能帮忙解释一下吗?
idx是在插入函数insertt()的时候用到,用来跳转的,idx后面用来赋值时,起步就是1。具体可以看下y总基础课的trie,挺详细的。
感谢感谢
不客气⊙▽⊙能帮到你就好!加油
idx模拟的就是结点
嗯,好的~ o( ̄▽ ̄)o
赞一个!解决我挺多问题。 就是举例子那里 窗口里的那些数和s的下标太像了,容易混淆
嗯嗯,下次一定改进,谢谢你宝贵的意见!笔芯
说到底我还是不太理解为什么需要插入s[0],的确,插入了之后可以异或到每个数本身的值,而当i>m的时候,后面的数字岂不是就不能得到自身的值了?
当i<m的时候,才可以选择s[i],而之后就不能选择s[i],因为只能选择连续的m个数,s[i]里面的数的个数已经>m了,你可以再看看我画的那张图
我觉得这个前缀和sj - si-1,所以才要插入s0吧?不然的话a1就没有被考虑进去了
wuwuwu,忘记回复了
不好意思 ,我没看懂你的意思。假如没有先插入0,那么s1在执行的时候就根本不能顺利进行下去
没事
我没说好,如果没有插入0的话,s1就无法执行下去!对!
辛苦了!我终于理解了wuwuwu
不客气哦!
对的!
当子数组长度的M为1的时候,是否意味着每个子数组就是和0进行异或,答案就是本身?
m为1的时候,只能选择一个数,相当于只能选择本身来进行求max,但是这里的s[i]指的是前i个数的异或
hi,我想问一下子数组可为空是什么意思啊?
就是不选择数,直接为0
这里要用ct[]来记录就是因为可能有多个相同的数在滑动数组里面
up主还在吗
insertt(sum[i-m-1],-1);为什么是i-m-1呢,后面查的sum[i], i-(i-m-1)是m+1个数呀
我觉得:s[i]^s[j]=a[j+1]^a[j+2]^.....^a[i],所以边界是保留到s[i-m]
很强,昨天刚做了单调队列就是没想起来怎么处理区间m的问题
tql,马上就懂了
为什么s6^s3,是第4~6的数的异或
一个数x异或两次y就会变回x,s6是1-3异或上4-6,现在在异或一次1-3就变回4-6的了。
ct[]数组 难道不应该开到节点编号的最大值嘛? 全建满 idx不是应该等于 1e5 * 31 * 2吗?