P1246. 编码

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

考点

  • 排列组合

题解

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
#include <bits/stdc++.h>
using namespace std;
const int LEN = 27;
string str;
int ans, c[LEN][LEN];

void init() {
  for (int i = 0; i < LEN; ++i) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
  }
}

bool judge() {
  int len = str.length();
  if (len < 1 || len > 6) return false;
  for (int i = 0; i < len - 1; ++i) {
    if (str[i] >= str[i + 1]) return false;
  }
  return true;
}

int main() {
  init();
  cin >> str;
  if (!judge()) {
    cout << 0;
    return 0;
  }
  for (int i = 1, len = str.length(); i < len; ++i) ans += c[26][i];
  for (int pre = 96, i = 0, len = str.length(); i < len; ++i) {
    for (int j = pre + 1; j < str[i]; ++j) {
      ans += c[26 - (j - 'a' + 1)][len - (i + 1)];
    }
    pre = str[i];
  }
  cout << ans + 1;
  return 0;
}

思路

具体思路参照https://www.luogu.com.cn/blog/AlexWei/solution-p1246

这里主要讲一下精髓，以abc为例

第2个位置的可能性下意识认为是\(C_{25}^{1}\)，第3个位置的可能性下意识认为是\(C_{24}^{1}\)

所以结果是\(C_{25}^{1}\times C_{24}^{1}\)吗？错误的！因为这样并不能保证第3个位置绝对大于第2个位置

但是将后面两个位置视为整体，用\(C_{25}^{2}\)同时取就能保证有序了：

  1. 绝对不会重复
  2. 组合数是无序的，或者说，任意顺序！自然可以视作升序方式排列