CF 1547D Co-growing Sequence

D Co-growing Sequence

来源:https://codeforces.com/problemset/problem/1547/D
标签:【位运算】【思维】

题目简述

定义一个数列为growing: 对于数列a, i从1到n-1,ai & ai+1=ai

For example, the following four sequences are growing:
[2,3,15,175] — in binary it's [10,11,1111,10101111];
[5] — in binary it's [101];
[1,3,7,15] — in binary it's [1,11,111,1111];
[0,0,0] — in binary it's [0,0,0].

The following three sequences are non-growing:
[3,4,5] — in binary it's [11,100,101];
[5,4,3] — in binary it's [101,100,011];
[1,2,4,8] — in binary it's [0001,0010,0100,1000].

定义两个数列为co-growing :对于数列x和y,(x1^y1 , x2^y2 , ... , xn^yn)所组成的数列为growing.
现给出x数列,求能和其组成co-growing的最小y数列,更小指的是第一个不相同的数更小。

Input
第一行为整数t(1≤t≤104)。接下来是t个测试用例。
每个测试用例的第一行包含一个整数n(1≤n≤2⋅105)-序列xi的长度。
第二行包含n个整数x1,x2,…,xn(0≤xi<230) -序列xi的元素。
所有测试用例的n总和不超过2⋅105

Output
对于每个测试用例,输出n个整数y1,y2,…,yn(0≤yi<2^30) 字典序最小序列,使其与给定序列xi co-growing。

Sample Input

5
4
1 3 7 15
4
1 2 4 8
5
1 2 3 4 5
4
11 13 15 1
1
0

Sample Output

0 0 0 0 
0 1 3 7 
0 1 0 3 2 
0 2 0 14 
0 

More Info


题目思路

观察规律得xi+yi = (x1 | x2 | ..... | xi).

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005;

int n,t;

int main()
{          
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int a[N];
        for(int i=1;i<=n;i++) cin>>a[i];
        cout<<0<<' ';
        int p=a[1];
        for(int i=2;i<=n;i++){
            p|=a[i];
            cout<<p-a[i]<<' ';
        }
        cout<<endl;
    }
    return 0;
}
原文地址:https://www.cnblogs.com/unravel-CAT/p/15001638.html