首页 > 代码库 > NYOJ 139 我排第几个 康托展开式
NYOJ 139 我排第几个 康托展开式
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=139
思路：康托展开式的典型应用，康托展开式是什么呢，举个例子。1，2，3这三个数的全排列共有六种，那么按照字典的顺序，『3，2，1』 这个序列是在第几个呢。康托是这样想的：
首先从第一位3开始看，比3小的有2，1，那么也就是说如果第一位是1或者2都在这个序列的前面，那么以1或者2开头的序列有多少呢，答案为2*2!。为什么是这个答案呢？因为符合 要求的第一位共有1和2两个数，然后第二位和第三位组成的排列总数为2！，所以，学过排列组合的都知道，乘起来就可以了(康托展开式本来就是组合数学里面的...)。
好了，既然我们明白了康托展开式是什么，下面就可以写代码了。
代码如下：
#include <iostream>#include <cstring>using namespace std;int jc[]={1,2,6,24,120,720,5040,40320,362880,3628800,39916800};//阶乘数组，记录我们要用到的阶乘 int book[12]={0};//标记数组，标记有没有用过 int main(){ string temp;//测试数据 int num; int now;//仅仅作为一个中间变量用 int res;//结果 int x;//比当前元素小且没有被用过的数量 cin>>num; while(num--) { memset(book,0,sizeof(book)); //初始化结果最小为1 res = 1; cin>>temp; for(int i=0;i<12;i++) { x = 0; now = temp[i]-97; //标记当前的temp[i]已经用过 book[now] = 1; //开始找比当前的temp[i]小的元素且没有用过的元素有几个 for(int j=0;j<11;j++) { if(book[j]==0&&now>j) x++; } //找出来的结果 进行相加 res += jc[10-i]*x; } cout<<res<<endl; } return 0;}
代码解释的很全。个人感觉这种题只是考一个模板，我也不知道康托展开式在算法比赛中有啥用。。希望高手可以告诉我康托展开式可以做啥～
NYOJ 139 我排第几个 康托展开式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。