首页 > 代码库 > POJ1850 组合数学

POJ1850 组合数学

2024-07-16 12:33:28   231人阅读

POJ1850

问题重述：

用26个小写字母进行编码，编码规则如下：

1）每个编码中前一个字母必须小于后一个字母

2）编码按照长度从小到大排列，相同长度按字典序进行排列

输入一个字母串，求解该编码对应的数值。

问题分析：

该问题等价于求解小于输入编码的编码的数目。

对于编码X = x1,x2,x3,...xk, 小于X的编码可以分为两个部分

1）位数小于k的编码。

　　这部分编码的数目 = C[26][1] + C[26][1] + ... + C[26][k - 1]

2）长度为k，且小于X的编码。

　　假设Y为满足该条件的编码，现只需确定Y的数目。从左到右遍历编码X： i = 1 to k，假设X和Y的前i - 1位均相等且 yi != xi，那么 yi 必须满足 xi-1 = yi - 1 < yi < xi。

　　对于yi的每一种取值， yi, yi + 1, ... yk只需满足递增关系即可, 共有C[26][25 - (yi - ‘a‘)]种编码。

根据以上分析，即可求出结果。

AC代码：

 1 //Memory: 204K        Time: 0MS 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7  8 using namespace std; 9 10 string s, ss;11 int c[27][27];12 13 void init()14 {15     for (int i = 0; i <= 26; i++) 16         c[i][0] = c[i][i] = 1;17 18     for (int i = 1; i <= 26; i++)19         for (int j = 0; j < i; j++)20             c[i][j] = c[i - 1][j] + c[i - 1][j - 1];21 }22 23 int main()24 {25     cin >> s;26         27     int len = s.size();28     for (int i = 0; i < len - 1; i++) {29         if (s[i] > s[i + 1] || s[i] == s[i + 1]){30             cout << 0 << endl;31             return 0;32         }33     }34 35     init();36     int ans = 0;37     for (int i = 1; i <= len - 1; i++) {38         ans += c[26][i];39     }40 41     for (int i = 0; i < s[0] - ‘a‘; i++) {42         ans += c[25 - i][len - 1];43     }44 45     for (int i = 1; i < len; i++) {46         for (int j = s[i - 1] - ‘a‘ + 1; j < s[i] - ‘a‘; j++)47             ans += c[25 - j][len -1 - i];48     }49     cout << ans + 1 << endl;50     51     return 0;52 }

 


联系
我们