[ACM] poj 1496 Word Index（组合计数）

Description

    a -> 1

    b -> 2

    .

    .

    z -> 26

    ab -> 27

    ac -> 28

    .

    .

    az -> 51

    bc -> 52

    .

    .

    vwxyz -> 83681

Input

Output

Sample Input

z
a
cat
vwxyz

Sample Output

26
1
0
83681

Source

题目中所输入的串必须严格上升是很关键的一点，在26个字母中随便选5个字母，则这5个字母只有一个排列（满足严格上升），所以根据此来计数。

比如要求   c  e   h 这个字典序是多少。该串长3 ，所以先把串长1和2的情况加上，即sum+=c (26,1) + c(26,2) , 该串为3了，注意到第一个字母最初应该从‘a‘开始,a->b 剩下两位随便在25->24个数里选 ,即 sum+=c (2 5,2) + c( 24 ,2) ，注意第一个字母不能到达 c，否则获得的串可能会比c e h大。给出的串第二个字母最初不能从a开始，因为要严格上升，要从原串上一个字母的下一个字母开始，第一个字母为c，所以第二个字母要从d开始计数, sum+=c( 24 , 1) ,最后一个字母也一样。这样最后所得的sum为 ceg的字典序，再加上1就是ceh的字典序了。 对于ceh 有  s+=c[26][1]+c[26][2]+c[25][2]+c[24][2]+c[22][1]+2+1;

代码：

#include <iostream>
#include <string.h>
using namespace std;

int c[30][30];

void C()//求组合数
{
    for(int i=0;i<=26;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];
        }
    }
}

int main()
{
    string s;
    C();
    while(cin>>s)
    {
        int len=s.length();
        int i;
        for(i=1;i<len;i++)
        {
            if(s[i]<=s[i-1])
                break;
        }
        if(i<len)
        {
            cout<<0<<endl;
            continue;
        }
        int sum=0;
        for(i=1;i<len;i++)
            sum+=c[26][i];//长度比该串短的先加上

        for(i=0;i<len;i++)//从高位进行处理对于每一位处理到该位的前一个，比如该位为‘d‘，就处理到c
        {
            char ch=i==0?‘a‘:(s[i-1]+1);
            for(char j=ch;j<s[i];j++)
                sum+=c[‘z‘-j][len-1-i];
        }
        cout<<sum+1<<endl;//加上串本身
    }
    return 0;
}

[ACM] poj 1496 Word Index（组合计数）,布布扣,bubuko.com

[ACM] poj 1496 Word Index（组合计数）

原文：http://blog.csdn.net/sr_19930829/article/details/23127741