C. A Good Problem

问题描述

给定四个正整数 $n, l, r, k$。你需要找到一个长度为 $n$ 的字典序最小*的整数数组 $a$，满足：

1. 对于每个 $1 \leq i \leq n$，都有 $l \leq a_i \leq r$。
2. $a_1 \And a_2 \And \ldots \And a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n$，其中 $\And$ 表示按位与操作，$\oplus$ 表示按位异或操作。

如果不存在这样的数组，输出 $-1$。否则，由于整个数组可能太大而无法输出，仅输出 $a_k$。

注意： 当且仅当以下条件之一成立时，数组 $a$ 的字典序小于数组 $b$：

• $a$ 是 $b$ 的前缀，但 $a \neq b$；或者
• 在 $a$ 和 $b$ 不同的第一个位置，数组 $a$ 的元素小于 $b$ 中对应的元素。

输入

每个测试包含多个测试用例。第一行是测试用例的数量 $t$ $(1 \leq t \leq 10^4)$。接下来是测试用例的描述。

每个测试用例包含四个正整数 $n, l, r, k$ $(1 \leq k \leq n \leq 10^{18}, 1 \leq l \leq r \leq 10^{18})$。

输出

对于每个测试用例，输出 $a_k$，如果不存在满足条件的数组，则输出 $-1$。

题解

如果 $n$ 是奇数，我们可以构造一个所有元素都等于 $l$ 的数组。

然后我们可以考虑当 $n$ 是偶数时会发生什么。在这种情况下，我们可以让 $n-2$ 个元素等于 $l$，这意味着与操作的结果将是 $l$，但异或操作的结果将是 $0$。

最后两个元素应满足条件 $l \And v_1 \And v_2 = v_1 \oplus v_2 = res$。考虑 $l$ 中的一个位，如果我们想在结果 $res$ 中保留这个位，那么这个位在 $v_1$ 和 $v_2$ 中都必须被设置。如果两个位都被设置，那么异或的结果将是 $0$，这意味着它们是无效的。 因此，对于 $l$ 中所有被设置的位，我们不能在 $v_1$ 和 $v_2$ 中都设置它们。 并且值 $v_1$ 和 $v_2$ 应该大于 $l$。 所以我们可以让 $v_1 = v_2 = 2^{\text{(l的最高位)}}$。在这种情况下，$\text{res} = 0$，并且 $v_1, v_2$ 是可能的最小值。

提交链接