AcWing 3485. 最大异或和 带注释
原题链接
中等
作者:
蓬蒿人
,
2021-05-10 22:52:42
,
所有人可见
,
阅读 2766
本题可视作143延伸
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010*31;
//int son[N][2],cnt[N],a[100010],n,idx,s[100010];
// 整体思路 字典树求最大异或对的做法
// 将子数组l~r的异或和a[l]^...^a[r] 转化为前缀异或和数组(s[r]^s[l-1])
// 遍历s数组每轮内查询s[i]在合法范围的最大异或和 最后得到结果
// ps:合法范围就是s[max(i-m,0)]~s[i]
int son[N][2],a[100010],s[100010],n,idx,cnt[N];
//son数组 第一维是节点编号第二维是0或1儿子
//存的是p节点的0或1儿子的节点编号
//cnt数组当前存编号为p的节点出现的次数
void insert (int x,int v){
//插入兼删除函数 通过v的正反实现插入与删除
int p=0;
for (int i=30;i>=0;i--){
int u=x>>i&1;
if (!son[p][u]) son[p][u]=++idx;
p=son[p][u];
cnt[p]+=v;
//cnt数组存当前编号为p的节点出现的次数
}
}
int query (int x){
//查询x最大异或和
int p=0,res=0;
for (int i=30;i>=0;i--){
int u=x>>i&1;
if (cnt[son[p][!u]]) {
//由于我们的x可求异或和的范围不是所有s
//所以不是if (son[p][!u])
//而是cnt[son[p][!u]]当前可异或节点的出现次数
res=res*2+1;
p=son[p][!u];
}
else {
res*=2;
p=son[p][u];
}
}
return res;
}
int main()
{
int m;
cin>>n>>m;
for (int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]^a[i];
}
insert(s[0],1);
//子数组可以为空 插入0
int res=0;
for (int i=1;i<=n;i++){
if (i>m) insert(s[i-m-1],-1);
//s[i]可求异或合法范围是s[max(i-m,0)]~s[i]
//要及时把超出范围的数去掉
res=max(res,query(s[i]));
insert(s[i],1);
}
cout <<res;
}
为什么用res=res2+u或res=res2+!u的话答案不对啊,非要用那个res=res*2+1什么的吗,到底是什么意思
同问
我好像知道了,用 res = res * 2 + u 和 res = res * 2 + !u 最后返回的结果是找到 最大的异或的值
用 res = res * 2 + 1 和 res = res * 2 最后返回的结果是 传入的数和最大的异或的数已经异或完的值
就是 max(ant, ant ^ query(x)) 和 max(ant, query(x)) 的区别 ant 就是所有数中最大的异或值
res = res * 2 或者 res = res * 2 + 1,这个结论怎么得到的呢
这里的res保存的是与s[i]异或的最大结果
秦九韶进制转换
为什么上面不是加!u而是直接加1啊,搞不懂
因为如果有!u,就代表一定是有1的,因此求异或就是res = res*2+1
啊?为什么就一定代表有1啊,大佬能不能说详细点
!u存在就说明该位置有和自身不同的,那么这个位置就是取1,因此就是2*res + 1。
异或是相同取0,不同取1
佬,cnt数组是什么意思啊
某个节点出现的次数
可以求最小异或和吗该如何做哈,怎么避开自己去寻找其它最小的异或和呢?谢谢!
应该是可以 异或和最小是0 首先特判一下有无相邻的两个大小相同的数字 如果有最小异或和就是0
如果没有那把本题的query函数改一下就行
orz
问一下 res=res*2+1;什么意思
我们是从最高位一位一位异或下来的
若当前最新一位可以异或 则该位的值为1 那么res左移一位(即*2)+1
异或值为0 则是仅左移
明白了 原来这里的res保存的是与s[i]异或的最大结果 谢谢!!
orz