CF2119E.And Constraint

wowaka & 初音未来 - Tosenbo

给定一个长度为 $n-1$ 的序列 $a$ 和一个长度为 $n$ 的序列 $b$。

你可以进行如下操作任意次（也可以不进行）：

• 选择一个下标 $1 \le i \le n$，将 $b_i$ 增加 $1$（即令 $b_i \leftarrow b_i + 1$）。

你的目标是用最少的操作次数，使得对于每个 $1 \le i \le n-1$，都有 $b_i \,\&\, b_{i+1} = a_i$，其中 $\&$ 表示按位与运算。如果无法满足条件，也请输出。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）。

第二行包含 $n-1$ 个整数 $a_1, a_2, \ldots, a_{n-1}$（$0 \le a_i < 2^{29}$）。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i < 2^{29}$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果可以达成目标，输出一个整数——所需的最小操作次数。否则输出 $-1$。

在第一个测试用例中，一种最优策略是进行 $4$ 次操作，使 $b = [1,5,4,4]$，此时满足所有条件。可以证明无法用少于 $4$ 次操作达成目标。

在第二个测试用例中，由于 $b_1 \,\&\, b_2 = 4$ 且 $b_2 \,\&\, b_3 = 0$，则 $b_3 \,\&\, 4 = 0$。但又要求 $b_3 \,\&\, b_4 = 4$，因此无法满足所有条件。

由 ChatGPT 4.1 翻译