CF1547D Co-growing Sequence（位运算，思维）

原题链接

题目

给一个长度为 $n$ 的序列 $a$

构造一个字典序最小的数组 $b$

使 $a_i$ $xor$ $b_i$ $(1<=i<=n)$ 后满足 $a_i$ $and$ $a_{i+1}$ $==$ $a_i$ $(1<=i<=n?1)$

思路

一个数 $xor0$ 等于它本身

一个数 $and$ 本身等于 $0$

那么为了字典序最小，$b_1$ 肯定是 $0$，后面答案唯一。为了使 $a_i$ $and$ $a_{i?1}=a_i$，将 $a_i$ 和 $a_{i?1}$ 换成二进制，使 $a_{i?1}$ 有 $1$ 的位置，$a_i$ 也要是 $1$，那么就用 $a_{i?1}or{a}_i$，找出所有有 $1$ 的位置，然后再减去 $a_i$ 上原本有的 $1$，这样这个数与 $a_i$ $xor$ 后所有 $1$ 的位置肯定都包含了 $a_{i?1}$ 上有 $1$ 的位置。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin >> t;while (t -- ){
    int n;cin >> n;int a[n + 10] ;for (int i = 1; i <= n; i ++ ){
    cin >> a[i];}cout << 0 << " ";for (int i = 2; i <= n; i ++ ){
    int x = (a[i] | a[i - 1]) - a[i];a[i] ^= x;cout << x << " ";}
// cout << endl;
// for (int i = 1; i <= n; i ++ ) cout << a[i] << " ";cout << endl;}return 0;
}

总结

位运算，要好好琢磨琢磨。