1547-D, *1300

Problem - 1547D - Codeforces

풀이

• 수열 $a_{1}a_{2}...a_{n}$에 대해 $i$에서 $a_{i}\&a_{i+1}=a_{i},\ i = 1,\ 2,...,\ n-1$일때 수열이 $growing$이라고 한다
• 두 수열 $a,\ b$에 대해 수열 $\left \{ (a_{1}\oplus b_{1}),\ (a_{2}\oplus b_{2}),\ ...\ ,\ (a_{n}\oplus b_{n}) \right \}$이 $growing$이면
  두 수열 $a,\ b$는 $co-growing$이라고 한다
• 수열 $x$가 주어질 때 $x,\ y$가 $co-growing$에게 하는 lexicographically minimal sequence $y$를 구하라

 

$O(n)$

index	$i$	$i+1$
$x_{(2)}$	1011	1101
$y_{(2)}$	0	a
$x\oplus y$	1011	b

위 표와 같이 a, b 를 제외하고 정보를 알고있다고 하자
수열 {$x\oplus y$}은 $growing$이기 때문에 b = 1?11 (비트가 1이었던 부분은 유지되어야 한다)
따라서 a = 0?10 ($\because 1101 \oplus a = b\Leftrightarrow a=b\oplus 1101$)

a 는 최소값이어야 하므로 ?는 0으로 바꾸면 되고, a = 0010. 따라서 b = 1111

귀납적으로 $y$가 결정된다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n;
 
        int x;
        int y = 0;
        cin >> x;
        cout << y << ' ';
        int z = x;
 
        for(int i = 0; i < n-1; i++){
            cin >> x;
            y = (z^x)&z;
            z = x^y;
            cout << y << ' ';
        }
        cout << endl;
 
    }
 
    return 0;
}cs