题意简述

给定长度为 $n-1$ 的数组 $b$，需要构造长度为 $n$ 的数组 $a$，使得

$$a_i \mathbin{\&} a_{i+1} = b_i \quad (1 \le i \le n-1) $$

若不存在，输出 -1。

逐位分析

按位与的性质：某一位为 $1$ 当且仅当参与运算的两个数在该位都为 $1$。
因此，若 $b_i$ 的第 $k$ 位为 $1$，则 $a_i$ 和 $a_{i+1}$ 的第 $k$ 位必须都是 $1$。
若 $b_i$ 的第 $k$ 位为 $0$，则 $a_i$ 和 $a_{i+1}$ 的第 $k$ 位不能同时为 $1$。

构造方法

1. 初始化 $a_1 \dots a_n$ 为 $0$。
2. 遍历 $i = 1 \dots n-1$，将 $a_i$ 和 $a_{i+1}$ 都按位或上 $b_i$。这一步将所有必须为 $1$ 的位设置好。
3. 再次遍历 $i = 1 \dots n-1$，检查 $(a_i \mathbin{\&} a_{i+1})$ 是否等于 $b_i$。
   • 若相等，说明所有 $0$ 位的限制也满足（因为那些位上不会同时为 $1$）。
   • 若不等，说明某个必须为 $0$ 的位被迫变成了 $1$，此时无解，输出 -1。

正确性说明

• 步骤 2 设置了最少的必要 $1$ 位，如果这样仍然导致某个 $b_i=0$ 的位在 $a_i$ 和 $a_{i+1}$ 上同时为 $1$，那么任何其他赋值也不可能满足（因为那些 $1$ 位是强制要求的）。
• 若检查通过，则构造出的 $a$ 就是合法的。

时间复杂度 $O(n)$（每一位独立操作可以合并为按位或），总复杂度 $O(\sum n) \le 10^5$，足够快。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> b(n - 1);
        for (int i = 0; i < n - 1; ++i) {
            cin >> b[i];
        }

        vector<int> a(n, 0);
        for (int i = 0; i < n - 1; ++i) {
            a[i] |= b[i];
            a[i + 1] |= b[i];
        }

        bool ok = true;
        for (int i = 0; i < n - 1; ++i) {
            if ((a[i] & a[i + 1]) != b[i]) {
                ok = false;
                break;
            }
        }

        if (!ok) {
            cout << "-1\n";
        } else {
            for (int i = 0; i < n; ++i) {
                cout << a[i] << " \n"[i == n - 1];
            }
        }
    }
    return 0;
}