牛客多校七 C

• 将每一个数看成是 $3030$ 位二进制整数
• 只要确定了 $a_{1}a\_1$, 剩下的数就都确定了 ， 因为 $a_{i+1}\leftarrow b_i\oplus a_{i}a\_\{i+1\}\; \backslash gets\; b\_i\; \backslash oplus\; a\_i$
  • $a_2\leftarrow b_1\oplus a_{1}a\_2\; \backslash gets\; b\_1\; \backslash oplus\; a\_1$
  • $a_3\leftarrow a_2\oplus b_2\leftarrow a_1\oplus b_1\oplus b_{2}a\_3\; \backslash gets\; a\_2\; \backslash oplus\; b\_2\; \backslash gets\; a\_1\; \backslash oplus\; b\_1\; \backslash oplus\; b\_2$
  • $a_4\leftarrow a_1\oplus b_1\oplus b_2\oplus b_{3}a\_4\; \backslash gets\; a\_1\; \backslash oplus\; b\_1\; \backslash oplus\; b\_2\; \backslash oplus\; b\_3$
• 设$su{m}_i\leftarrow b_i\oplus b_{i-1}sum\_i\; \backslash gets\; b\_i\; \backslash oplus\; b\_\{i-1\}$, 则 $a_i\leftarrow a_1\oplus su{m}_{i-1}a\_i\; \backslash gets\; a\_1\; \backslash oplus\; sum\_\{i-1\}$
• 要一对儿一对儿的考虑限制，即考虑所有的$su{m}_i,su{m}_{i+1}sum\_i,\; sum\_\{i+1\}$ (前缀异或和)
• 观察发现 $a_{1}a\_1$ 的每一位上的数的取值情况可以通过分析前缀异或和得到
• $a_{1}a\_1$ 上的每一位的取值情况一共有三种
  • 只能取 $11$;
  • 只能取 $00$;
  • $0,10,1$ 都能取也就是没有限制。
• 对于每个限制就是找到 $su{m}_i,su{m}_{i+1}sum\_i,\; sum\_\{i+1\}$，的二进制表示从左往后第一位不相同的，则 $a_{1}a\_1$ 的该位置应该与 $su{m}_{i}sum\_i$ 保持一致（异或不同才是$11$） 如此可保证数组 $aa$ 的单调性;
• 计算字典序第 $kk$ 小的数 要记得 $k-1k-1$ ,再转成二进制填到 $a_{1}a\_1$ 可以变化的位数上去。因为字典序第一小的数是 $a_{1}a\_1$ 所有可以变化的位置都为 $00$ 的情况；
• 时间复杂度 $O(n)O(n)$, 常数为 $3030$;

参考代码：

#include <cstring>
#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;

const int N =1e6+6;

int a1[30]; // 0-29 表示有效示数
int a[N];
int sum[N]; // 前缀异或和
void solve(){
    int n,k; cin >> n >> k;
    sum[0] = 0;
    for(int i =1; i < n; i++){
        int b;
        cin >> b;
        sum[i] = sum[i-1]^b;
    }
    memset(a1,-1,sizeof a1);
    bool has_ans = true;
    // sum[0] = 0  一共是 n-1 个限制 a_i  <= a_{i+1}
    for(int i = 0; i < n-1; i++){
        // 从高位开始枚举
        if(!has_ans)
            break;
        for(int j =29; j >= 0; j--){
            int t1 = (sum[i]>> j) & 1;
            int t2 = (sum[i+1] >> j) & 1;
            if(t1 != t2){
                if(a1[j] == -1){
                    // 第 i+1 位没有限制时 限制第 i+1 位
                    a1[j] = t1;
                }
                else{
                    if(a1[j] != t1){
                        has_ans = false;
                    }
                }
                break;
            }
        }
    }
    if(!has_ans){
        cout << -1 << '\n';
    }
    else{
        k--; int cnt = 0;
        for(int i =29; i >= 0; i--){
            if(a1[i] == -1){
                cnt = cnt*2+1;
            }
        }
        if(k > cnt){
            cout << -1 << '\n';
        }
        else{
            int p = 0;
            while(k){
               int t = k & 1;
                while (a1[p] != -1 && p <= 29){
                    p++;
                }
                a1[p] = t;
                k >>= 1;
            }
            // 计算a_1 的值
            a[1] = 0;
            for(int i = 29; i>=0; i--){
                if(a1[i] == 1){
                    a[1] = a[1]*2+1;
                }
                else a[1] *=2;
            }
            for(int i =2; i <= n; i++){
                a[i] = a[1]^sum[i-1];
                if(a[i] > 1 << 30){
                    cout << -1 << '\n';
                    return;
                }
            }
            for(int i =1; i <= n; i++){
                cout << a[i] << ' ';
            }
            cout << '\n';
        }
    }
}