组合的字典序问题

妖狐艹你老母 2022-06-09 13:40 164阅读 0赞

## ``  题目来自：[http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1202][http_acm.njupt.edu.cn_acmhome_problemdetail.do_method_showdetail_id_1202] ##

## **字典序问题** ##

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte  
总提交:168            测试通过:10

描述

在数据加密和数据压缩中常需要对特殊的字符串进行编码，给定的字母表A由26个小写英文字母组成A=\{a,b,…,z\}。该字母表产生的升序字符串是指字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每一个字符最多出现1次。例如，a,b,ab,bc,xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升序字符串按照字典序并编码如下：

1  2  ... 26  27  28  ...

a  b  ...  z  ab  ac  ...

对于任意长度不超过6的升序字符串，编程计算出它在上述字典中的编码。

输入

输入的第1行是一个正整数k，表示接下来共有k行。在接下来的k行中，每行给出一个字符串。

输出

输出共有k行，每行对应一个字符串的编码。

样例输入

2  
a  
b

样例输出

1  
2

题目来源

算法设计与实验题解

主要思路：

1，计算位数k

C（1,26）+ C(2,26)+.....+C(k-1,26)

2，对于每个字母求总数即可

#include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    //求c（k，n）
    int combin(int k, int n)
    {
    	if( k == 0 )
    		return 1;
    
    	long demo = 1, num=1;
    	
    	for( int j=0; j<k; j++ )
    	{
    		num *= n-j;
    		demo *= j+1;
    	}
    
    	return (int) num/demo;
    }
    
    int main()
    {
    	int N=0;
    	cin >> N;
    	vector<string> vstr(N);
    	for( int i=0; i<N;i++)
    		cin >> vstr[i];
    
    	for( int i=0; i<N; i++)
    	{
    		string str = vstr[i];
    		
    		int K = str.length();
    
    
    	long total =0;
    
    	for(int i=1; i<=K-1; i++ )
    	{
    		total += combin( i, 26 );
    	}
    
    	//计算每一位
    	for( int k=0; k<K; k++)
    	{
    		int before=0; //记录前一位
    
    		if( k== 0 ) before =0;
    		else before = str[k-1] -'a'+ 1;
    		int m = str[k] - 'a' +1;
    
    		for (int i=before+1; i <= m-1; i++)
    		{
    			total += combin( K-k-1, 26-i);
    		}
    	}
    
    		std::cout << total+1 <<endl;
    	}
    
    	return 0;
    }

和网上大部分的程序运行结果都一样，却在那个鸟平台上通不过，郁闷。

[http_acm.njupt.edu.cn_acmhome_problemdetail.do_method_showdetail_id_1202]: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1202