[Codeforces]Round #731. D

작성일 | In

D. Co-growing Sequence

문제 출처: https://codeforces.com/contest/1547/problem/D

  • 문제 풀이

    문제가 요구하는 대로 따라간다면 어렵지 않다.

    1. lexicographically minimal sequence 를 요구하므로 yi 의 초기값은 0으로 한다.
    2. xi ^ yi 의 값을 가지는 수열을 resi라고 할 때, resi-1과 resi 가 growing을 만족한다면 아래과정 생략
    3. resi = resi-1 | resi 를 하여 growing 관계를 만들어준다.
    4. resi = yi ^ xi 이므로 yi = resi ^ xi 이다. 이를 이용해 yi 를 갱신한다.
    5. i = 2~n 반복

  • 풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define INF 1e9
#define ll long long
#define pii pair<int, int> 
#define vi vector<int> 
#define foi(n) for(int i=0;i<n;++i)
#define endl '\n'
using namespace std;

int t;
int n, x[MAX], y[MAX], res[MAX];
 
void solve(){
    memset(y, 0, sizeof(y));
    res[0]=x[0];
    for(int i=1;i<n;++i){
        int tmp=x[i]^y[i];
        res[i]=tmp;
        if((tmp&res[i-1])!=res[i-1]){
            tmp=tmp|res[i-1];
            res[i]=tmp;
            y[i]=tmp^x[i];
        }
    }
    foi(n) cout<<y[i]<<' ';
    cout<<endl;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin>>t;
    while(t--){
        cin>>n;
        foi(n) cin>>x[i];
        solve();
    }
}