題干：

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character).?

The coding system works like this:?
? The words are arranged in the increasing order of their length.?
? The words with the same length are arranged in lexicographical order (the order from the dictionary).?
? We codify these words by their numbering, starting with a, as follows:?
a - 1?
b - 2?
...?
z - 26?
ab - 27?
...?
az - 51?
bc - 52?
...?
vwxyz - 83681?
...?

Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code.?

Input

The only line contains a word. There are some constraints:?
? The word is maximum 10 letters length?
? The English alphabet has 26 characters.?

Output

The output will contain the code of the given word, or 0 if the word can not be codified.

Sample Input

bf

Sample Output

55

題目大意：

按一定規(guī)則編纂了字典序：

字典中的各字符串中的字母保證嚴格按升序排列。 長度小的一定在長度大的前面，長度相同時，按照真正的字典序。
給出一個字符串，求該字符串在字典中的編號，若字典中沒有（字母不按升序排）則輸出0。?

解題報告：

一個題解：

對于不同的小寫字母，嚴格升序組成的一組序列，分別代表從1~n的數(shù)值。

這題關(guān)鍵是求組合的數(shù)值C。對于方法，并不是太難，分兩種情況

1.當長度小于給出的字符串L時，對于字符串長度為1的字符串總共代表的數(shù)字的量就是C(26,1)，對于長度為2的字符串總共代表的數(shù)字的量就是C(26,2)，一次類推，直到C(26,L-1)。

2.對于長度等于L的，從最開頭的字符s[0]開始，對于比這個字符嚴格小的，如果有一個，我們可以有C('z'-s[0], L-1)個，'z'-s[0] 是因為題意已經(jīng)說明該字符串每個位置是嚴格遞增的。如果在這個位置，還能找到別s[0]嚴格小的，則再加上。

再遍歷到后面的字符s[i],對于比這個字符嚴格小的，我們依然可以找到C('z'-s[0], L-i-1)個。一直到最后一個字符，這樣，所有結(jié)果的總和，就是結(jié)果。

對于1中的原理如下：

以兩位的串為例，有ab~az,bc~cz,……那么有組合數(shù)

遞推出這個公式，需要結(jié)合組合里的一個很常用的式子

后面的依此類推。有大佬也指出，既然你是升序，那么只要你有幾位，你就選幾個出來，那么它的嚴格升序排列只有一種，所以就是C(26,L),就是在長度為L下的所有組合數(shù)。

然后利用上面的式子進行遞推，求出所有的26以內(nèi)的所有組合數(shù)，再直接利用求結(jié)果即可。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll C[33][33]; ll n,ans; char s[33]; int main() {C[0][0]=1;for(int i = 1; i<=30; i++) {C[i][0] = 1;for(int j = 1; j<=30; j++) {C[i][j] = C[i-1][j] + C[i-1][j-1];}}while(~scanf("%s",s)) {ll ans = 0;int len = strlen(s);bool flag = 1;for(int i = 0; i<len-1; i++) {if(s[i] >= s[i+1]) {flag = 0;break;}}if(flag == 0) {puts("0");continue;}//之前長度的 for(int i = 1; i<len; i++) {ans += C[26][i];}//當前字符開始計算 for(int i = 0; i<len; i++) {char cur;if(!i) cur = 'a';else cur = s[i-1]+1;while(cur < s[i]) {ans += C[26-(cur-'a')-1][len-i-1];cur++;} }printf("%lld\n",ans+1); }return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【POJ - 1850】Code （组合数学，字符串另类排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。