CATALAN - Dãy số Catalan

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 50;
using namespace std;
int n, kth;
int a[N], f[N][N];

int cnt;
void naive(int i) {
    if (i > n) {
        if (a[n] == 1) {
            cout << ++cnt << "  ";
            REP(i, 1, n) cout << a[i] << ' ';
            cout << endl;
        }
        return;
    }
    if (a[i - 1] >= 1) {
        a[i] = a[i - 1] - 1;
        naive(i + 1);
    }
    a[i] = a[i - 1] + 1;
    naive(i + 1);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n; n <<= 1;
    REP(i, 0, n) cin >> a[i];
    cin >> kth;
    n--;
    f[n][1] = 1;
    REPD(i, n, 2) REP(j, 0, n) if (f[i][j]) {
        //cout << i << ' ' << j << ' ' << f[i][j] << endl;
        f[i - 1][j + 1] += f[i][j];
        if (j) f[i - 1][j - 1] += f[i][j];
    }
    int ans = 0;
    REP(i, 1, n) {
        FOR(j, 0, a[i])
        if (abs(a[i - 1] - j) == 1)
            ans += f[i][j];
    }
    cout << ans + 1 << endl;
    a[1] = 1;
    //naive(2);
    REP(i, 2, n) {
        if (a[i - 1] == 0) {
            a[i] = 1;
            continue;
        }
        if (f[i][a[i - 1] - 1] < kth) {
            kth -= f[i][a[i - 1] - 1];
            a[i] = a[i - 1] + 1;
        }
        else a[i] = a[i - 1] - 1;
    }
    REP(i, 0, n + 1) cout << a[i] << ' ';
    return 0;
}

Download