从2024.7.29开始记录。代码不放可能是因为我没写。
1. P7470 [NOI Online 2021 提高组] 岛屿探险
先考虑 \(b_i > d_j\) 的情况。那么答案就是 \(\sum [a_i \oplus c_j \le d_j]\)。我们把 \(a_i\) 插入 \(01 \text{trie}\) 中。然后我们从上往下走，走到深度为 \(h\) 的节点，那么代表他的值等于 \(c_i \oplus d_j\) 的前 \(h\) 位。然后我们考虑第 \(h + 1\) 位。
-
\(d_i = 0\)，那么 \(a_i\) 和 \(c_j\) 的第 \(h + 1\) 位必须相等，否则 \(a_i \oplus c_j > d_j\)，然后直接往这个方向走即可。
-
\(d_i = 1\)，那么此时 \(a_i\) 和 \(c_j\) 的第 \(h + 1\) 位任意取都行。那么就有两种可能：
- 如果 \(a_i\) 和 \(c_j\) 的第 \(h + 1\) 位不一样，那么此时 \(a_i\) 依然等于 \(c_j \oplus d_j\)，所以我们向这个方向继续走即可。
- 如果 \(a_i\) 和 \(c_j\) 的第 \(h + 1\) 位一样，那么此时 \(a_i \oplus c_j\) 就会一定小于 \(d_j\) 了，那么对于答案的贡献就是这个字数里 \(a_i\) 的个数之和。
这一部分就是 CF817E。比较简单。
接下来我们考虑 \(b_i \le d_j\) 的情况。这一个部分比较困难。但是我们发现这一个部分和 \(a_i \oplus c_j \le d_j\) 的结构很像，所以我们可以考虑类似的操作。
标签：le,那么,oplus,数据结构,好玩,我们,qwq From： https://www.cnblogs.com/Carousel/p/18329721