暑假牛客多校第七场 2023-8-7（C）

dkdklcx / 2023-08-10 / 原文

C. Beautiful Sequence

参考博客

算法：构造

做法：
首先我们有 \(a_i \oplus a_{i+1} = b_i\)，那么我们设一个函数为 \(f(i) = b_0 \oplus b_1 \oplus b_3 \oplus ... \oplus b_i\)，其中 \(b_0 = 0\)。实际上我们由上面的函数可得 \(f(i) = a_1 \oplus a_{i+1}\)，自己把所有 \(b_i = a_i \oplus a_{i+1}\) 都代进去就可以得到了。

那么我们对于每一位 \(a_i\) 有 \(a_i = a_1 \oplus f(i-1)\)，我们规定 \(f(0) = 0\)。研究题目我们可以知道一旦确定了 \(a_1\)，那么所有 \(a\) 值就确定了，而且 \(a_1\) 的二进制的某一位确定了，那么所有 \(a\) 的二进制的这一位也就确定了。我们首先对 \(a_1\) 的二进制的所有位都置为 \(-1\) 表示未确定的位。随后我们枚举每一个 \(a_i\) 和 \(a_{i+1}\)，即枚举 \(a_1 \oplus f(i-1)\) 和 \(a_1 \oplus f(i)\)。我们只需考虑 \(f(i - 1)\) 和 \(f(i)\) 从大到小的对应的二进制位，当有不同时，如果 \(a_1\) 的二进制的这一位没有被确定，那么我们就把这一位置为 \(f(i-1)\) 相应的位的值。解释：因为 \(f(i-1)\) 和 \(f(i)\) 的这一位是不同的，那么当 \(a_1\) 的这一位和 \(f(i-1)\) 不同时，那么这一位异或后 \(a_i\) 的这一位是1，而\(a_{i+1}\)的这一位是0，不符合题意，因此必须与 \(f(i-1)\) 这一位相同。如果这一位之前已经确定了，那么我们判断一下这一位是否与 \(f(i-1)\) 的对应的位相同，不相同则输出-1。最后得到了 \(a_1\) 的所有需要确定位，那么我们对于 \(k\) 转化为二进制，判断能满足题意，最后构造 \(a_1\) 的未确定位为 \(k\) 的二进制数即可。

code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 1000100, M = 300010, INF = 0x3f3f3f3f;

LL n, k;
LL a[N], b[N], f[N];
bool flag;
LL num[35];

void init()
{
    f[0] = 0;
    a[1] = 0;
    flag = false;
    for (int i = 0; i < 35; i++)num[i] = -1;
}

void solve()
{
    init();
    cin >> n >> k;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> b[i];
        f[i] = f[i - 1] ^ b[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        if (flag)break;
        for (int j = 29; j >= 0; j--)
        {
            if (((f[i] >> j) & 1) != ((f[i + 1] >> j) & 1))
            {
                if (num[j + 1] == -1)
                {
                    num[j + 1] = (f[i] >> j) & 1;
                }
                else if (num[j + 1] != ((f[i] >> j) & 1))
                {
                    flag = true;
                }
                break;
            }
        }
    }
    
    if (flag)
    {
        cout << -1 << endl;
        return;
    }

    k--;
    LL s = 0;
    for (int i = 30; i >= 1; i--)
        if (num[i] == -1)s = s * 2 + 1;
    if (s < k)
    {
        cout << -1 << endl;
        return;
    }

    int p = 1;
    while (k)
    {
        int x = k & 1;
        while (num[p] != -1)p++;
        num[p] = x;
        k = k >> 1;
    }
    for (int i = 30; i >= 1; i--)
        if (num[i] == -1)num[i] = 0;
    for (int i = 1, w = 1; i <= 30; i++, w *= 2)
        if (num[i])a[1] += w;
    for (int i = 2; i <= n; i++)
        a[i] = b[i - 1] ^ a[i - 1];
    if (a[n] >= (LL)pow(2, 30))
    {
        cout << -1 << endl;
        return;
    }
    for (int i = 1; i <= n; i++)cout << a[i] << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}