Gray Code (CSES 2205)

題目網址

A Gray code is a list of all \(2^n\) bit strings of length \(n\), where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one). Your task is to create a Gray code for a given length \(n\).

解題思路: 這題實作上非常簡單,但就是在想解題的過程很有趣,我想到一種一定是解的作法,有遞迴的感覺,底下舉個例子:
\(n=1\):
0
1

\(n=2\):
00
01
11
10

\(n=3\):
000
001
011
010
110
111
101
100

會發現 \(n\) 的 Gray Code 就是在 \(n-1\) 的 Gray Code 前面加上 0,再把 \(n-1\) 的 Gray Code 反過來加上 1,這樣就能保證相鄰的兩個字串只有一個 bit 不同,而且也能保證所有的字串都會出現,所以就是一定是解,但只知道這樣其實在實作上會有點麻煩,會需要紀錄之前的 Gray Code,其實可以發現每一位之間是有規律的,以最右邊的一位為例,必定會是 011001100110…,第二位就是 0011110000111100…,第 \(i\) 為的間格會是 \(2^i\),那就可以一位位分析應該擺 0 或 1,但再仔細觀察一下,這樣的關係,恰好會是兩位之間 XOR=1 的間格,以第一位為例:
無論數字多大,位元的第一和第二位都會是如下規律:
00
01
10
11
00
01
10
11
00
…
兩位間 XOR 關係後恰巧會是:011001100110…

而若是第二位: 無論數字多大,位元的前三位都會是如下規律: 000
001
011
010
110
111
101
100
000
…
第二三位間 XOR 關係後恰巧會是:0011110000111100…
以此類推,最後一位就看目前有沒有過半,過半前是 0,過半後是 1,就能輕鬆秒殺這題了。

Gray Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pii pair<int, int>
#define int long long
#define rep(i, a, b) for(int i = a; i<=b; i++ )
#define rev(i, a, b) for(int i = a; i>=b; i-- )
#define tomax(a, b) (a)=max((a), (b))
#define tomin(a, b) (a)=min((a), (b))
#define pb push_back
#define eb emplace_back
using namespace std;

signed main(){
ios
int n;
cin >> n;
rep(i, 0, (1<<n)-1){
cout << (i>>(n-1));
rev(j, n-2, 0)
cout << (((i>>j)&1) ^ ((i>>(j+1))&1));
cout << '\n';
}
return 0;
}