题解：E. And Constraint

题目理解

我们有两个序列：

• $a_1, a_2, \dots, a_{n-1}$（长度 $n-1$）
• $b_1, b_2, \dots, b_n$（长度 $n$）

可以进行的操作：每次选择任意 $b_i$ 增加 $1$，花费 $1$ 次操作。

目标：用最少操作次数使得对所有 $1 \le i \le n-1$ 满足：

$$b_i \ \&\ b_{i+1} = a_i$$

其中 $\&$ 是按位与运算。如果不可能，输出 $-1$。

---

核心难点

1. 操作只能增加 $b_i$，不能减少。所以初始 $b_i$ 是下界。
2. 约束 $b_i \& b_{i+1} = a_i$ 是位级约束。
3. 操作次数最小化 = 让 $b_i$ 尽量小，但又必须满足所有与约束。

---

位运算性质

对任意两个数 $x, y$：

$$x \& y = z \quad \Rightarrow \quad z \le x \text{ 且 } z \le y $$

并且 $z$ 的二进制位必须是 $x$ 和 $y$ 都有的位。

更关键：若 $x \& y = z$，则：

• 若 $z$ 的某一位是 $1$，则 $x$ 和 $y$ 的这一位都必须是 $1$。
• 若 $z$ 的某一位是 $0$，则 $x$ 和 $y$ 不能同时在这一位为 $1$（可以一个 $1$ 一个 $0$，或两个 $0$）。

---

动态规划思路

标程使用了按位构造的 DP。

状态定义

设 $f_i$ 表示：在考虑前 $i$ 个 $b$ 值且满足前 $i-1$ 个与约束后，$b_i$ 可能取的值以及达到该值的最少操作数。

但 $b_i$ 范围很大（$<2^{29}$），不能直接枚举。标程技巧：
只枚举 $b_i$ 可能的值，这些值由 $a_{i-1}$、$a_i$ 和 $b_i$ 的初始值决定。

---

关键观察

固定 $b_i$ 和 $b_{i+1}$ 需要满足：

$$b_i \& b_{i+1} = a_i$$ $$b_{i+1} \& b_{i+2} = a_{i+1}$$

对于 $b_{i+1}$，它必须同时满足：

1. 与 $b_i$ 的与等于 $a_i$
2. 与 $b_{i+2}$ 的与等于 $a_{i+1}$

所以 $b_{i+1}$ 的二进制位受两个方向约束。

标程采用了从左到右递推，每个 $b_i$ 只依赖于 $a_{i-1}$ 和 $a_i$。

---

转移方法

标程中的核心循环：

for(int i=1;i<=n;i++){
    int x=0;
    g.clear();
    for(int j=30;j>=-1;j--){
        int y = x | a[i-1] | a[i];
        if(j!=-1) y |= (1<<j); 
        if(y >= b[i]){
            ll mn=inf;
            for(stu l:f){
                if((l.x & y) != a[i-1]) continue;
                mn = min(mn, l.dp + y - b[i]);
            }
            if(mn<inf) g.push_back((stu){y,mn});
        }
        x |= ((1<<j) & b[i]);
    }
    swap(f,g);
}

解释：

• $x$：当前已经确定必须为 $1$ 的位（来源于 $b_i$ 的初始值）。

• 从高位到低位（$j=30$ 到 $j=-1$）枚举：

  • 尝试在 $y$ 中设置或不设置这位（当 $j=-1$ 时表示不设置任何新位）。
  • $y$ 必须包含 $a_{i-1}$ 和 $a_i$ 的所有 $1$ 位（因为 $b_{i-1}\&b_i = a_{i-1}$ 和 $b_i\&b_{i+1}=a_i$ 都要求 $b_i$ 在这些位为 $1$）。
  • 如果 $y \ge b[i]$（不能减少，只能增加），则 $y$ 是一个可能的 $b_i$ 新值。
  • 从上一层的 $f$ 中找出所有 $b_{i-1}$ 值 $l.x$ 满足 $l.x \& y = a_{i-1}$，计算操作数增量 $y - b[i]$，取最小值。
  • 加入 $g$ 作为这一层的可能状态。

• $x$ 逐步累加 $b[i]$ 的当前位，确保我们考虑了所有可能的 $y$。

---

为什么这样枚举是充分的？

因为 $b_i$ 只能从初始值 $b[i]$ 开始增加，且增加的位只能从 $0$ 变 $1$。
所有可能达到的 $b_i$ 必须是：

$$b_i \ge b[i] \quad \text{且} \quad b_i \ \&\ a_{i-1} = a_{i-1} \ \text{且} \ b_i \ \&\ a_i = a_i $$

即 $b_i$ 必须包含 $a_{i-1}$ 和 $a_i$ 的所有 $1$ 位。

标程中的枚举方式，从高位到低位尝试设置 $0$ 或 $1$，覆盖了所有满足 $b_i \ge b[i]$ 且包含 $a_{i-1} | a_i$ 所有 $1$ 位的值。

---

初始化和最终答案

• 初始 $f$ 只有一个状态：$b_0$ 为 $0$（虚拟前驱），操作数 $0$。但注意第一个约束是 $b_1 \& b_2 = a_1$，所以 $b_1$ 需要包含 $a_1$。
• 最终 $i=n$ 时，$f$ 中存储所有可能的 $b_n$ 值及其最小操作数。取最小 $dp$ 值即为答案。
• 若 $f$ 为空，输出 $-1$。

---

复杂度分析

• 每个位置最多枚举约 $31 \times 2$ 种 $y$（$j$ 从 $30$ 到 $-1$，共 $32$ 次）。
• 每次需要遍历上一层的 $f$ 大小，但 $f$ 大小不会超过 $32$（因为每个 $y$ 都不同且数量有限）。
• 总复杂度：$O(n \cdot 32^2) = O(1024n)$，对于 $n \le 10^5$ 可接受。

---

样例验证

以第一个样例为例：

n=4
a=[1,4,4]
b=[1,2,3,4]

过程：

• $b_1$ 可能值：包含 $a_1=1$ 且 $\ge 1$，最小为 $1$。
• $b_2$ 需要包含 $a_1|a_2=1|4=5$，且 $\ge 2$，并满足 $b_1\&b_2=1$。尝试得 $b_2=5$ 是可行且最小的，操作数 $5-2=3$。
• 继续推导得 $b_3=4$，$b_4=4$，总操作数 $3+1=4$。

---

代码实现要点

• 用结构体 stu{int x; ll dp;} 存储状态。
• $a_n$ 设置为 $0$ 以统一处理边界。
• 使用 inf 表示不可达。
• 注意位运算优先级。

---

总结

本题的关键在于：

1. 利用按位与的约束将 $b_i$ 的可行值限制在较小的集合中。
2. 从高位到低位贪心枚举 $b_i$ 的可能取值。
3. 动态规划记录每个位置每种取值的最小操作数。
4. 由于位数 $<29$，状态数 $O(32)$，复杂度可行。

这是一个巧妙的按位构造 + DP 的题目，适合练习位运算与状态压缩思想。