AcWing 4645. 选数异或 :大白话 推理一遍Y总代码运行过程
原题链接
中等
作者:
kerry2023
,
2023-01-03 14:50:29
,
所有人可见
,
阅读 786
题目:选数异或
新手小白 解释了Y总代码运行过程
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010, M=(1<<20)+10;;
int n,m,x;
int g[N],s[M];
int main()
{
cin>>n>>m>>x;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
g[i]=max(g[i-1],s[a^x]);
//g[i]本质上存得是位置 s[a^x]求得是a^x后的位置 如果存在则记录下来 不存在就s[a^x]=0
//g[i]每次更新 新a符合的异或值 比如第一个a1^x=b1=2 第二个a2^x=b2=0 第二个a3^x=b3=3;那么g[3]=b3;更新到最近的
//这样方便我们下面进行判断
//比如判断l=3 r=5区间内
//g[5]>=l就可以筛选出区间内是否有合适的值 如果没有更新那么b1=2 显然<L,所以3-5之间就没有合适的值 输出no
//但如果更新到b3,那么b3=3,g[3]>=L 所以输出yes
s[a]=i; //给s[a]按顺序安排位置 注意这里的a是读入的n个数 不一定每次都是顺序大小 我们记录他们的位置 方便上面进行判断
}
while(m--)
{
int l,r;
cin>>l>>r;
if(g[r]>=l) puts ("yes");//g[r]判断最大得最靠右得是否>=L g[r]本身就<=r(因为g[r]是从1-r进行遍历得 )
else puts ("no");
}
return 0;
}
//g[r]一定是小于等于N,因为给g[r] r的范围是从1-N进行遍历的
//s[a^x]存在就等于这个位置的值 不存在则等于0 所以即使a^x在括号中的值非常大 如果它这个数不存在那么就是0
//除非前面1-n遍历的时候已经记录 所以s[a^x]一定小于N s[a]每次更新直到更新到N
//所以我门只需要判断是否大于等于L
g[i]那一点不是太明白为什么要取g[i-1]和是s[a^x]的max
因为L和R询问是一个区间,所以我们要取g[i]的最大值
如果s[a^x]出现新的符合预期的值且靠右 那么我们就更新成它
如果s[a^x]不存在 那么值为0,所以就取上一个可以异或的值!
实在不理解可以看Y总视频结合分析下
好的谢谢
s[a^x]=0是初始化就实现的吗
是的 它在main函数外 所以默认是0