最资讯丨ACWING 4645. 选数异或

2023-01-09 13:15:57 来源：博客园

url:4645. 选数异或 - AcWing题库

(相关资料图)

题意:

给n个数,再给m次查询,给一个数x

每次询问给一个区间l,r,问是否能从$[l,r]$中选出两个下标不同的数

使得它们的异或值等于x

思路:

这题有个异或性质我没想到(

找两个数使得$a[l] ⊕ a[r] = x$

根据异或的交换性来说

式子可以变成:$a[r] ⊕ x = a[l]$

那么我们直接用$a[r] ⊕ x$即可得到$a[l]$

这时候问题就变成了去找离r最近的$a[r] ⊕ x$即可

暴力思路就是先枚举后端点,往前枚举前端点,记录每个点的满足条件的最右边的值

当然这是O₂的,肯定不行

用个map即可很好地解决这个问题

每次map都记录一下a[i]的值,并且使得$mp[a[i]] = i$

这样后面用map来寻找值就直接找到的是下标

并且由于是顺序遍历,后面新的值会覆盖旧的值,而新的值的下标一定是优于旧的值的

然后再用map来弄出$a[i]⊕x$的最右端下标,即$mp[a[i]⊕x]$

用个数组g来记录这些值

然后最后接收l和r,比较是否$l <= g[i]$

然后就发现样例都过不去(

因为这里算的是每个$a[i]$对应的最优解

实际上如果[2,3]满足的话,[2,4]是一定满足的

因为是从这个范围选择两个数,其中一个数并不一定要在最右端点

这里的解决方案就是:

在算$b[i]$的时候对$b[i - 1]$取个max,即是:$b[i] = max(b[i - 1],mp[a[i] ⊕ x]])$

这样就保证了后面的值会继承前面的最右下标

代码:

void solve(){map mp;int x;cin >> n >> m >> x;vector a(n + 10),b(n + 10);for(int i = 1;i <= n;i++) cin >> a[i];for(int i = 1;i <= n;i++){b[i] = max(mp[a[i]^x],b[i - 1]);mp[a[i]] = i;}while(m--){int l,r;cin >> l >> r;if(b[r] >= l) YES;else NO;}}

总结:

异或是具有交换性的

所以问是否$x ⊕ y == z$时,就要联想到$z ⊕ y == x$或者$z ⊕ x == y$

看题目要求什么,这种后面有很多询问的,一般的$O(n^2)$算法都能预处理优化成$O(n)$再处理后面的询问

如果一种情况包含另一种情况,考虑用max那个预处理的东西来维护

关键词：解决方案满足条件可以变成