第十三届蓝桥杯省赛C++A组 D 题、C++C组 F 题、Java C 组 F 题——选数异或（AC）

超、凢脫俗 2023-09-28 23:26 13阅读 0赞

#### 目录 ####

*  1.选数异或
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.选数异或 ##

### 1.题目描述 ###

给定一个长度为  n n n 的数列  A 1 , A 2 , ⋯   , A n A\_\{1\}, A\_\{2\}, \\cdots, A\_\{n\} A1,A2,⋯,An和一个非负整数  x x x, 给定  m m m 次查 询, 每次询问能否从某个区间  \[ l , r \] \[l, r\] \[l,r\] 中选择两个数使得他们的异或等于  x x x 。

### 2.输入格式 ###

输入的第一行包含三个整数  n , m , x n, m, x n,m,x 。

第二行包含  n n n 个整数  A 1 , A 2 , ⋯   , A n A\_\{1\}, A\_\{2\}, \\cdots, A\_\{n\} A1,A2,⋯,An 。接下来  m m m 行，每行包含两个整数  l i , r i l\_\{i\}, r\_\{i\} li,ri表示询问区间  \[ l i , r i \] \\left\[l\_\{i\}, r\_\{i\}\\right\] \[li,ri\]。

### 3.输出格式 ###

对于每个询问, 如果该区间内存在两个数的异或为  x x x 则输出 `yes`, 否则输出 `no`。

### 4.样例输入 ###

4 4 1  
1 2 3 4  
1 4  
1 2  
2 3  
3 3

### 5.样例输出 ###

yes  
no  
yes  
no

### 6.数据范围 ###

1 ≤ n , m ≤ 100000 , 0 ≤ x < 2 20 , 1 ≤ l i ≤ r i ≤ n , 0 ≤ A i < 2 20 1≤n,m≤100000,0≤x<2^\{20\},1≤li≤ri ≤n, 0 \\leq A\_\{i\}<2^\{20\} 1≤n,m≤100000,0≤x<220,1≤li≤ri≤n,0≤Ai<220。

### 7.原题链接 ###

[选数异或][Link 1]

## 2.解题思路 ##

对于异或的性质不过多在这讲解，利用的也是非常简单的公式：如果存在`a^b=x`，那么一定满足`a^x=b`，`b^x=a`。也就是说，对于一个整数 `a` ,有且只存在一个数`b`使得其和`a`异或得到`x`，我们可以通过`a^x`来得到这个数的值。

对此，我们可以处理得到数组中所有符合的数对  ( a , b ) (a,b) (a,b)，其中  a a a 是数组中靠左的数， b b b是靠右边的。我们可以枚举  b b b , 然后判断在数组前面是否出现过数  a a a ，这一步我们可以使用哈希表记录维护每个数最后出现的位置，如果存在则说明找到一对符合的数对。那我们该如何记录答案呢？

我们定义 f \[ i \] f\[i\] f\[i\]为前  i i i 个数出现数对中  a a a 的**最大**下标。为什么要这么设计呢？  
考虑查询时需要确保 ( a , b ) (a,b) (a,b)都在查询区间 \[ l , r \] \[l,r\] \[l,r\]中，由于只需要考虑是否存在任意一对，那我们只需要维护最有可能的一对。当我们查询 f \[ r \] f\[r\] f\[r\] 时，可以保证查询到的所有  b b b 下标 一定不超过  r r r。那么此时就只需要保证是否存在一个  a a a 满足它的下标大于  l l l 即可。那么这样我们对于每个查询 \[ l , r \] \[l,r\] \[l,r\]，只需要去判断 f \[ r \] > = l f\[r\]>=l f\[r\]>=l 即可，符合则输出`yes`，否则输出`no`。

当然我们需要考虑如何转移，对于当前的值  v v v ,下标为  i i i。如果哈希表中不存在数 `x^v`，则 f \[ i \] = f \[ i − 1 \] f\[i\]=f\[i-1\] f\[i\]=f\[i−1\]，如果存在则为 f \[ i \] = m a x ( f \[ i − 1 \] , m \[ v ˆ x \] ) f\[i\]=max(f\[i-1\],m\[v ˆx\]) f\[i\]=max(f\[i−1\],m\[vˆx\])。因为 C++ 的`map`对不存在的数默认输出`0`，所以不影响我们的答案，即转移方程为：  
 f \[ i \] = m a x ( f \[ i − 1 \] , m \[ v ˆ x \] ) f\[i\]=max(f\[i-1\],m\[v ˆx\]) f\[i\]=max(f\[i−1\],m\[vˆx\])

## 3.Ac\_code ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair<int, int> PII;
    #define pb(s) push_back(s);
    #define SZ(s) ((int)s.size());
    #define ms(s,x) memset(s, x, sizeof(s))
    #define all(s) s.begin(),s.end()
    const int inf = 0x3f3f3f3f;
    const int mod = 1000000007;
    const int N = 200010;
    
    int n, q, x;
    map<int, int> m;
    int f[N];
    void solve()
    {
        
    	cin >> n >> q >> x;
    	for (int i = 1; i <= n; ++i) {
        
    		int v;
    		cin >> v;
    		f[i] = max(f[i - 1], m[x ^ v]);
    		m[v] = i;
    	}
    	while (q--) {
        
    		int l, r;
    		cin >> l >> r;
    		if (f[r] >= l) cout << "yes" << '\n';
    		else cout << "no" << '\n';
    	}
    }
    int main()
    {
        
    	ios_base :: sync_with_stdio(false);
    	cin.tie(nullptr);
    	int t = 1;
    	while (t--)
    	{
        
    		solve();
    	}
    	return 0;
    }

[Link 1]: https://www.lanqiao.cn/problems/2081/learning/