E. And Constraint

问题描述

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

你可以执行以下操作任意次数（可能为零次）：

• 选择一个索引 $1 \leq i \leq n$ 并将 $b_i$ 增加 1（即，设置 $b_i \leftarrow b_i + 1$）。

你的目标是执行最少次数的操作，使得对于每个 $1 \leq i \leq n-1$，都满足条件 $b_i \And b_{i+1} = a_i$，其中 $\And$ 表示按位与操作。如果无法满足条件，也请报告。

输入

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

第一行包含一个整数 $n$ ($2 \leq n \leq 10^5$)。

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

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

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

输出

对于每个测试用例，你只需要输出一个整数。

如果目标可以实现，输出一个整数 — 所需的最少操作次数。否则，输出 $-1$。

题解

提交链接

关键观察

必要条件分析

问题要求对于所有的 $i$，$b_i \And b_{i+1} = a_i$，这意味着 $a_i$ 的所有位在 $b_i$ 和 $b_{i+1}$ 中都必须被设置。

由于我们还有 $b_{i+1} \And b_{i+2} = a_{i+1}$，所以 $a_{i+1}$ 的位在 $b_{i+1}$ 和 $b_{i+2}$ 中也必须被设置。

为了让 $b_{i+1}$ 同时满足这两个条件，它必须包含 $a_i$ 和 $a_{i+1}$ 中所有的置位。因此，最低要求是：

注意，$b_1$ 和 $b_n$ 分别只需要满足一个条件。

可行性检查

这给了我们一个必要条件：如果我们用 $b_i = a_i | a_{i-1}$ 构建 $b$，而这个 $b$ 不满足 $b_i \And b_{i+1} = a_i$，那么就不存在有效的解决方案（输出 -1）。

反之，如果 $b$ 满足必要条件且 $b_i \And b_{i+1} = a_i$，那么我们总能找到一个满足所有约束的有效 $b$。

优化的动态规划解法

问题分析

为了找到最小的操作次数，我们使用动态规划，因为 $b_i$ 仅依赖于 $b_{i-1}$，$a_{i-1}$ 和 $a_i$。

关键的洞察是确定 $b_i$ 的哪些状态对于最小化操作是有用的。

状态空间优化

考虑约束条件，$b_i$ 必须包含来自 $a_i | a_{i-1}$ 的所有位。对于超出这个最低要求的任何附加位，我们只需要考虑一组有限的有用值。

例如，如果 $a_i | a_{i-1} = \text{0xa}$，那么 $b_i$ 必须至少包含 $\text{0xa}$。对于附加的位，我们只考虑遵循特定模式的值，以避免冗余计算。

关键的观察是，如果我们有一个需要更多操作才能达到的更高位值，而较低的位值将不需要，我们应该将它们全部设置为0（查看下面的代码以更好地理解这一点）。这意味着我们只需要为每个 $b_i$ 考虑大约30个可能的值。

实现细节

我们使用以下代码预计算有用的位模式：

const int HIGHEST = 0x00ffffffffffffff;
p[0] = make_pair(0xffffffffffff, 0);
p[1] = make_pair(0xfffffffffffe, 1);
for (int i = 2; i < 40; i++) {
    p[i].first = p[i - 1].first << 1;
    p[i].second = p[i - 1].second << 1;
    p[i].first &= HIGHEST;
}

对于每个位置 $i$，我们计算目标值如下：

int target_val = (b[i] & bits.first) | bits.second | a[i] | a[i - 1];

这个公式确保：

• 我们保留了来自 $a_i | a_{i-1}$ 的必要位
• 我们只考虑来自我们预计算集合的有用位模式
• 我们维持达到每个有效状态的最小成本

时间复杂度

动态规划的运行时间为 $O(n \cdot k)$，其中 $n$ 是数组长度，$k \approx 30$是每个位置的有用位模式数量。这对于给定的约束是足够高效的。