【ACM】nyoj_139_我排第几个_201308062046
我排第几个
时间限制:1000 ms | 内存限制:65535 KB
难度:3
描述
现在有"abcdefghijkl”12个字符,将其所有的排列中按字典序排列,给出任意一种排列,说出这个排列在所有的排列中是第几小的?
输入
第一行有一个整数n(0<n<=10000);
随后有n行,每行是一个排列;
输出
输出一个整数m,占一行,m表示排列是第几位;
样例输入
3
abcdefghijkl
hgebkflacdji
gfkedhjblcia样例输出
1
302715242
260726926
#include <stdio.h>
#include <string.h>
int JC(int n)
{
int i,sum=1;
for(i=1;i<=n;i++)
sum*=i;
return sum;
}
int main()
{
int N;
scanf("%d",&N);
while(N--)
{
int a[15];
char s[15];
int i,j,k,t,len,sum,ss;
scanf("%s",s);
t=len=strlen(s);
sum=ss=0;
memset(a,0,sizeof(a));
for(i=0;i<len;i++)
{
for(k=0,j=i+1;j<len;j++)
{
if(s[j]<s[i])
k++;
}
a[--t]=k;
}
for(i=len-1;i>=0;i--)
{
ss=JC(i);
sum+=a[i]*ss;
}
printf("%d\n",sum+1);
}
return 0;
}
组合数学之康拓展开:
公式描述:
把一个整数X展开成如下形式
X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中,a为整数,并且0<=ai<i(1<=i<=n)。
应用:
求一个排列中在全排列中排第几:
例:
321是{1,2,3}全排列中第几个大的数
解析:
第一位是3,当第一位的数小于3时,那排列数小于321 如 123、 213 ,小于3的数有1、2 。所以有2*2!个。再看小于第二位2的:小于2的数只有一个就是1 ,所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个?
再举个例子:1324是{1,2,3,4}排列数中第几个大的数
第一位是1小于1的数没有,是0个 0*3! 第二位是3小于3的数有1和2,但1已经在第一位了,所以只有一个数2 1*2! 。第三位是2小于2的数是1,但1在第一位,所以?有0个数 0*1! ,所以比1324小的排列有0*3!+1*2!+0*1!=2个,1324是第三个大数。
最新文章
- Android浮动小球与开机自启动
- Integer对象
- ubuntu下PHP支持cURL
- lightoj 1018 dp
- Python之数据序列化(json、pickle、shelve)
- c# Invoke和Begininvoke区别
- 【一天一道LeetCode】#32. Longest Valid Parentheses
- capwap学习笔记——初识capwap(三)(转)
- Javascript高级编程学习笔记(31)—— BOM(5)screen、history对象
- MySQL配置说明
- Linux下安装Anaconda
- C++学习(二十五)(C语言部分)之 结构体2
- win10编译caffe跑faster-rcnn(cuda7.5)
- Java编程的逻辑 (28) - 剖析包装类 (下)
- SDUT 1269-走迷宫(DFS打印路径)
- STM32中TIMx的映射及其通道
- mysql5.6常用查询sql
- NIS &; Kerberos配置
- Jmeter----请求的reponse结果中的某个参数作为JDBC Request的查询条件
- C++中const使用注意要点(二)