【CSES】2205. Gray Code

題目連結

時間複雜度

• $O(2^N)$

完整程式

/* Question : CSES 2205. Gray Code */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int n, cnt;
string res, init;

signed main(){
    opt;
    cin >> n;
    for( int i = 0 ; i < n ; i++ ) init.pb('0');
    for ( int i = 0; i < (1 << n); i++){
        res = init;
        cnt = i ^ (i >> 1);
        for( int j = 0 ; j < n ; j++ ){
            if( cnt & (1 << j) ) res[j] = '1';
        }
        cout << res << "\n";
    }
}