这道题目能想到正解还是不容易的。
首先看数据范围：

1 \le n,m \le 5 \times 10^5

。如果暴力做肯定超时。

前置知识

字典树，模板题传送门。

具体过程

那么看到题目中的异或运算，我们可以试着往字典树的方向来思考题目。
建一个只有

0

和

1

的字典树，对于每个结点都有一个标记

x

，表示从根结点到这个结点所形成的二进制数

k

能满足

x

个

i

使得

(a_i\oplus k)\le b_i

，其中

\oplus

是按位异或。

完成定义后，就开始来思考，进行分类讨论：

如果在二进制下这一位的 $b_i$ 是 $1$ ，这个时候异或的结果可以有两种情况，如果异或的结果为 $0$ ，则一定满足条件， $k$ 的这一位就要等于 $a_i$ 的这一位，这时就不用往下走了，直接给那个结点的标记 $+ 1$ 。如果异或的结果为 $1$ ，则还需要考虑后面的位数，于是就继续往下走。需要注意的是，如果到了最后一位，异或的结果为 $1$ 时也能满足条件，也要给更新标记。
如果在二进制下这一位的 $b_i$ 是 $0$ ，这个时候异或的结果只能有一种情况，那就是 $0$ ，这个时候 $k$ 的这一位等于 $a_i$ 的这一位。然后还需要继续往下走，同样要特判最后一位。

这样就基本解决完了。在计算答案时，把

k

的二进制在字典树上走一遍，把一路上的标记都相加即可。

代码

理解透了代码就很好写。

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, MX = 15000005;
int n, T, trie[MX][3], a[N], b[N], Q, lst, jd[MX], cnt;
void ins(int num, int num2){
	int now = 0;
	for(int i = 29;i >= 0;i--){
		int zh = ((num >> i) & 1), zh2 = ((num2 >> i) & 1);
		if(zh2){
			//如果没有这个结点就新建一个结点
			if(trie[now][zh] == 0) trie[now][zh] = ++cnt; 
			jd[trie[now][zh]]++;
			if(trie[now][zh ^ 1] == 0) trie[now][zh ^ 1] = ++cnt;
			now = trie[now][zh ^ 1];
			if(i == 0) jd[now]++;//特判i==0 
		} else{
			if(trie[now][zh] == 0) trie[now][zh] = ++cnt;
			now = trie[now][zh];
			if(i == 0) jd[now]++;
		}
	}
}
int fin(int num){
	int now = 0, ans = 0;
	for(int i = 29;i >= 0;i--){
		int zh = ((num >> i) & 1);
		if(trie[now][zh] == 0) break;
		now = trie[now][zh];
		//把k的二进制在字典树上走一遍，把所有标记相加
		ans += jd[now];
	}
	return ans;
}
int main(){
    scanf("%d%d%d", &T, &n, &Q);
    for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
    for(int i = 1;i <= n;i++){
    	scanf("%d", &b[i]);
    	ins(a[i], b[i]);
	}
    while(Q--){
    	int k;
    	scanf("%d", &k);
    	k = k ^ (lst * T);
    	int da = fin(k);
    	printf("%d\n", da);
    	lst = da;
	}
	return 0;
}

题解：P11209 『STA - R8』小熊游景点 II

文章操作

前置知识

具体过程

代码

相关推荐

评论

题解：P11209 『STA - R8』小熊游景点 II