装饰围栏

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 339 阅读时长 ≈ 1 分钟

考点

  • 计数DP
  • 试填法

题解

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 50, maxm = 1e5 + 50;
typedef long long ll;
int n, t;
ll C, f[21][21][2];

void prework() {
  // f[i][j][k]：i个不同高度的模板，从小到大以第j个开头，且它的状态是k(0作为低1作为高)
  f[1][1][0] = f[1][1][1] = 1;
  for (int i = 2; i <= 20; ++i) {
    for (int j = 1; j <= i; ++j) {
      for (int k = j; k < i; ++k) {
        f[i][j][0] += f[i - 1][k][1];
      }
      for (int k = 1; k < j; ++k) {
        f[i][j][1] += f[i - 1][k][0];
      }
    }
  }
}

int main() {
  prework();
  cin >> t;
  while (t--) {
    bool used[21];
    memset(used, 0, sizeof(used));
    cin >> n >> C;
    int idx, state;
    // 先处理第一块木板，先0后1
    for (int i = 1; i <= n; ++i) {
      if (f[n][i][1] >= C) {
        idx = i, state = 1;
        break;
      } else {
        C -= f[n][i][1];
      }
      if (f[n][i][0] >= C) {
        idx = i, state = 0;
        break;
      } else {
        C -= f[n][i][0];
      }
    }
    used[idx] = 1;
    cout << idx << " ";
    for (int i = 2; i <= n; ++i) {
      state ^= 1;
      int j = 0;
      // 从小到大，找第一个符合条件的、没用的木块，以保证字典序最小
      // j记录在n - i + 1里的，相对大小
      // len是真实长度
      for (int len = 1; len <= n; ++len) {
        if (used[len]) continue;
        j++;
        if (state == 0 && len < idx || state == 1 && len > idx) {
          if (f[n - i + 1][j][state] >= C) {
            idx = len;
            break;
          } else {
            C -= f[n - i + 1][j][state];
          }
        }
      }
      used[idx] = 1;
      cout << idx << " ";
    }
    puts("");
  }
  return 0;
}

思路

这是计数DP的模板题，请参考李煜东书的P370