CF1991B AND Reconstruction

原题链接：B. AND Reconstruction

Tag：位运算、构造

题目描述

给一个由 \(n - 1\) 个整数组成的数组 \(b\)。 尝试构造一个长度为 \(n\) 数组 \(a\)，满足 \(b_i = a_i \ \& \ a_{i+1} (1 \leq i \leq n - 1)\)。 如果不存在这样的数组，输出 \(-1\)。

分析

因为题目给出的条件是 \(b_i = a_i \ \& \ a_{i+1} (1 \leq i \leq n - 1)\)， 所以，如果二进制下一个数位在 \(b_i\) 和 \(b_{i-1}\) 上同时为 \(1\) 时， 在 \(a_i\) 上对应的二进制位也是 \(1\)。

所以我们可以让 \(a_i = b_i \ | \ b_{i-1}\)。 最后我们检查一下这个方式构造出来的数组 \(a\) 是否合法即可。

代码实现

void NeverSayNever() {
    int n;
    cin >> n;
    vector<int> vec(n + 5),ans(n + 5);
    for (int i = 1; i < n; ++i) {
        cin >> vec[i];
    }
    ans[1] = vec[1];
    ans[n] = vec[n - 1];
    for (int i = 2; i < n  ; ++i) {
        ans[i] = vec[i] | vec[i - 1];
    }
    bool flag = false;
    for (int i = 1; i < n  ; ++i) {
        if(vec[i] != (ans[i] & ans[i + 1])){
            flag = true;
            break;
        }
    }
    if(flag){
        cout << -1 << endl;
    }else{
        for (int i = 1; i <= n ; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    }
}

额外思考

唉，位运算

日志

本页面创建于 2024/7/29 21:58