← 返回题目列表

AtCoder · pakencamp_2025_day3_h

H. 或偏好

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

配点 : 100 点

問題文

请注意,内存限制是特殊的。 请解决

T 测试用例的以下问题。

长度 小于或等于 N 整数序列 给出 A = (A_0, A_1, \dots, A_{N-1}) 。 对于
重复以下操作之一,直到数组的长度为 1。

  • \mathrm{AND} 操作:两个相邻元素 选择 (a, b) ,合并它们并用一个元素替换它们。此时新元素为 a \,\&\, b 。
  • \mathrm{OR} 操作:两个相邻元素 选择 (a, b) ,合并它们并用一个元素替换它们。此时新元素为 a \,|\, b 。

当数组最后有一个元素时,其值为 必须是 0 。

在满足该条件的操作序列中, 求执行\mathrm{OR} 操作的最大次数。

但是,如果不存在这样的操作列, -1 输出。

制約

  • 1 \leq T \leq 2^{12}
  • 2 \leq N \leq 2^{13}
  • 0 \leq A_{i} < 2^{13}
  • 在每个测试用例中 N 的总和是 2^{13} 不超过
  • 所有输入均为整数

部分点

对于此问题,以下规则确定提交的分数。

  • 在所有输入情况下 如果您得到 AC ,您将获得满分。
  • 如果没有, 我们可以使用以下规则获得m = 1,2 \ldots 12 的部分分数。

    • “在每个测试用例中 N 的总和是 不超过 2^m 并且A_i < 2^m'' 对于满足条件的所有输入案例 如果您得到 AC ,另外 可获得 m 积分。
  • 例如,“在每个测试用例中 如果您得到 N 的总和是 不超过 2^4 (=16) 并且A_i < 2^4'' 对于满足条件的所有输入案例 如果您得到 AC ,1+2+3+4 点,即 10 积分。


入力

输入是按以下格式从标准输入给出的。输入的 1 行具有以下格式。

T

然后,T 测试用例如下。每个测试用例均按以下格式给出。

N
A_{1} A_{2} \cdots A_{N}

出力

T 行。i 行中,i 个测试用例中完成。 \mathrm{OR} 查找最大操作数。


入力例 1

4
6
3 0 1 4 1 5
2
0 1
8
2 0 1 6 1 2 0 3
10
1 7 6 7 5 7 5 3 2 7

出力例 1

3
0
5
6

该输入包含 包含4 测试用例。

1 对于第二个测试用例,请按照以下步骤操作。 2 第次操作 3 可以进行回合。

  • 最初、A = (3,0,1,4,1,5) 。
  • (A_{3}, A_{4}) 反对 \mathrm{OR} 执行操作。手术后,A = (3,0,5,1,5) 变为。
  • (A_{1}, A_{2}) 反对 \mathrm{AND} 执行操作。手术后,A = (0,5,1,5) 变为。
  • (A_{3}, A_{4}) 反对 \mathrm{OR} 执行操作。手术后,A = (0,5,5) 变为。
  • (A_{2}, A_{3}) 反对 \mathrm{OR} 执行操作。手术后,A = (0,5) 变为。
  • (A_{1}, A_{2}) 反对 \mathrm{AND} 执行操作。手术后,A = (0) 变为。

这个操作方法最终 由于 A_{1} = 0 成立,因此满足条件。 \mathrm{OR} 操作 通过执行超过 4 这是一种多次执行的方法,答案是 3 。 对于