洛谷P1246编码问题-排列组合，分类讨论

题意就是a，b，c.....ab.....编码，给你一个字符串，输出这是第几个；

这里可以用暴力枚举，但也可以用组合数学的高超知识；

既然这样我就说一下排列组合的方法，如果要弄一个各位数字递增的三位数，只需要在一个有序数列里面取三个数字，此时就无需关注顺序，因为顺序只能是升序的。比如0 1 2 3 4 5 6 7 8 9。取得9 5 8 那么他的顺序就只能是589。总数就是C(x,y)，x代表位数，y代表可供选择的数的长度，

就像例子中是c(3,10)。对于字母排列，道理也是一样。只需要注意一下y的大小，然后从左到右一步一步推下去就好。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

using namespace std;

int f[][];

int d[];

string str;

int main(){

    ios::sync_with_stdio();

    cin.tie();

    cout.tie();

    cin>>str;

    f[][] = ;

    for(int i=;i<=;i++)                //用打表的方式做组合C的计算

    {

        for(int j=;j<=;j++)

            f[i][j] = f[i-][j-] + f[i-][j];

    }

    int l = str.length();

    for(int i=; i<l; i++)

    {

        d[i] = str[i] -'a' + ;

        if(i> && d[i]<=d[i-]){cout<<<<endl;return ;}        //特判不存在的情况

    }

    if(l==){cout<<<<endl;return ;}

    if(l==){cout<<d[]<<endl;return ;}

    //累加长度小于L的可能性；

    int sum = ;

    for(int i=; i<l; i++)

    {

        sum+= f[][i];//i 代表数的位数；

    }

    //下面是求l位数的前面； 如：BDF 先计数A*的个数 再BC*的个数 再BD

    for(int i=;i<l-;i++)

    {

        if(i==)

        {

            for(int j=; j<d[i]; j++)

            {

                sum+=f[-j][l-i-];

                //cout<<f[26-j][l-i-1]<<endl;

            }

        }

        else

        {

            for(int j=d[i-]+; j<d[i]; j++)            //一开始这个j的界限想了比较久，后来想明白了，确实和前一个有关系，

            {                                            //因为规定后一个数比前一个数大；所以后一个数是从前个数+1开始；

                sum+=f[-j][l-i-];

            }

        }

    }

    sum+=d[l-]-d[l-];   //比如BDE到BDF有2个，这个需要加上去。

    cout<<sum<<endl;

    return ;

}

巴特西

洛谷P1246编码问题-排列组合，分类讨论

最新文章

热门文章