← 返回题目列表

Codeforces · 2147/E

E. 最大 OR Popcount

中文机器翻译题面 查看原题

给你一个 $$$n$$$ 非负整数数组。

您想要回答给定的 $$$q$$$ 独立场景。第$$$i$$$场景下,允许执行以下操作 最多 $$$b_i$$$ 次:

  • 选择数组的一个元素并将其增加$$$1$$$。

您的目标是在数组中所有数字的按位或中,最大化等于 $$$1$$$ 的位数。找到每个场景的这个数字。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 10^{5}$$$) - 数组的大小和场景的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{9}$$$) — 数组的元素。

接下来的 $$$q$$$ 行中的第 $$$i$$$ 行包含一个整数 $$$b_i$$$ ($$$0 \leq b_i \leq 10^{9}$$$) — 第 $$$i$$$ 场景中允许的最大操作数。

保证所有测试用例的$$$n$$$总和不超过$$$10^{5}$$$,所有测试用例的$$$q$$$总和不超过$$$10^{5}$$$。

输出

对于每个测试用例,输出 $$$q$$$ 行,其中第 $$$i$$$ 包含单个整数 - 在第 $$$i$$$ 场景中按位或中的最大可能位数等于 $$$1$$$。

示例

输入
复制

3
1 3
0
0
2
4
2 2
1 3
0
3
2 1
1000000000 1000000000
1000000000

输出
复制

0
1
2
2
3
31

注意

展示台链接

在第一个测试用例中:

  • 在第一种情况下,我们没有任何操作,因此答案等于原始数组 $$$0$$$ 的按位 OR 中 $$$1$$$ 位的数量,该数组在其二进制表示中设置了 $$$0$$$ 位。
  • 在第二种情况下,在按位 OR 中实现 $$$1$$$ 位设置的一种方法是将 $$$a_1$$$ 增加 $$$1$$$ 两次,获得 $$$2={(10)}_2$$$ 的按位 OR。可以证明,这是我们最多执行两次操作可以获得的最佳值。
  • 在第三个场景中,实现 $$$2$$$ 结果的一种方法是将 $$$1$$$ 与 $$$a_1$$$ 相加三次,这可以证明是最佳的。请注意,您不必应用操作 $$$4$$$ 次。

在第二个测试用例中:

  • 在第一种情况下,我们没有任何操作,因此答案等于原始数组按位或中的 $$$1$$$ 位的数量,即 $$$2$$$。
  • 在第二种情况下,实现 $$$3$$$ 结果的一种方法是将 $$$1$$$ 添加到 $$$a_2$$$ 三次,这可以证明是最佳的。