poj1850（组合数）

以你之姓@ 2021-12-21 01:05 240阅读 0赞

题目链接：http://poj.org/problem;jsessionid=B0D9A01EC0F1043088A37454B6CED469?id=1850

题意：给字符串编号，该字符串必须满足由小写英文字母组成且按字典序升序排列，a编号为1，ab编号为27，输入一字符串，如果满足前面的要求则输出其编号，否则输出0。

思路：简单组合数的题，为了方便我将输入的字符串转换成了整型数组，len表示其长度，当不满足题目要求时输出0。否则，先初始化组合数数组C，然后计算其编号也就是比它小的数的个数+1，比它小的数有两种可能：长度小于len，长度等于len，分别处理即可。

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    
    int a[15],len,ans,flag=1,C[27][27];
    
    void init(){
        C[0][0]=1;
        for(int i=1;i<=26;++i){
            C[i][0]=1;
            for(int j=1;j<=i-1;++j)
                C[i][j]=C[i-1][j-1]+C[i-1][j];
            C[i][i]=1;
        }
    }
    
    int main(){
        char s[15];
        scanf("%s",s);
        len=strlen(s);
        a[0]=0;
        for(int i=0;i<len;++i)
            a[i+1]=s[i]-'a'+1;
        for(int i=1;i<=len;++i){
            for(int j=i+1;j<=len;++j)
                if(a[j]<=a[i]){
                    flag=0;
                    break;
                }
            if(!flag) break;
        }
        if(flag){
            init();
            for(int i=1;i<len;++i)
                for(int j=1;j<=26-i+1;++j)
                    ans+=C[26-j][i-1];
            for(int i=1;i<=len;++i)
                for(int j=a[i-1]+1;j<a[i];++j)
                    ans+=C[26-j][len-i];
            printf("%d\n",ans+1);
        }
        else
            printf("0\n");
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/10685851.html