POJ1850

news/2025/2/21 23:43:36/

题目链接：https://vjudge.net/problem/POJ-1850

AC思路：

　　可以把一个字符串S(设其长度为len) 所对应的数字看成排在其前面的所有字符串的个数加一。

　　对于S，排在其前面的字符串可以分成两类：

　　1、长度小于len 的所有字符串；

　　2、长度等于len 并且排在S前面的字符串。

　　对于第1类，我们可以先推出求长度为 t 的所有字符串的个数的公式：其实对于构造一个长度为 t 的字符串，就是从26个字母中取出 t 个字母，由于一定要升序排列，故该字符串在字母取出的同时便被确定了。所以, 长度为 t 的所有字符串的个数 = C(26,t)。有了这条公式，第一类字符串的总个数就不难求出了。

　　对于第2类，我们可以从头到尾遍历S，对于每一个位置 i，尝试放置大于S[i-1]（如果是第一位则从 ‘a' 取起）且小于S[i] 的字母，由于在位置 i 的字母已经放置了（设为C），则其后可以出现的字母数便为 ’z'-C，我们需要从这 'z'-C 个字母中取出 len-i-1 个来填满位置 i 之后的所有位置，由于有了求第1类的经验，我们已经知道：“字符串在字母取出的同时便被确定了”，故只需在代表答案的 ans 变量上加上组合数 C['z'-ch][len-i-1] 就可以了。

　　至于求组合数的方法，上次好像已经提到过了，就是做POJ3252的时候好像已经提到过了，就是利用公式 C(i,j)=C(i-1,j-1)+C(i-1,j)，打表即可。

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int C[30][30];
 6 void init(){
 7     C[0][0]=0;
 8     C[1][0]=C[1][1]=1;
 9     for(int i=2;i<30;i++){//qian
10         C[i][0]=C[i][i]=1;
11         for(int j=1;j<i;j++)
12             C[i][j]=C[i-1][j-1]+C[i-1][j];
13     }
14 }
15 int main(){
16     init();
17     char word[14];
18     scanf("%s",word);
19     int len=strlen(word);
20     for(int i=1;i<len;i++){
21         if(word[i]<=word[i-1]){
22             printf("0\n");
23             return 0;
24         }
25     }
26     long long ans=1;
27     for(int i=1;i<len;i++)
28         ans+=C[26][i];
29     for(int i=0;i<len;i++){
30         char ch;
31         if(!i)  ch='a';
32         else    ch=word[i-1]+1; 
33 
34         while(ch<word[i]){
35             ans+=C['z'-ch][len-i-1];
36             ch++;
37         }
38     }
39     printf("%d\n",ans);
40     return 0;
41 }