poj 1715 Hexadecimal Numbers 排列组合

 1 /**
 2 大意： 给定16进制数的16个字母，，求第k大的数，，要求数的长度最大为8.，并且每个数互不相同。
 3 思路： 从高到低挨个枚举，每一位能组成的排列数 ，拿最高位来说，能做成的排列数为15*A（15，len-i）
 4           第二位 A（14，len-2）。。这样就可以找到k大的数的长度
 5 接下来 。找第k大的数。同上理 ，挨个枚举每一位即可。。若加上该位的排列数大于k，则该位就是这个数，继续枚举下一位
 6 **/
 7 
 8 /**  大神思路
 9 首先确定数字串的长度Len：从大到小枚举Len，每个Len下有15*P(15, Len-1)个数字串。每次用这个个数扣除输入的序数Count，直到序数Count将扣为负数时停止，就确定了长度Len。
10  
11 然后从高位到低位，从大到小确定每位数字：设当前确定的数字为第i位，则第i位的任何一个取值，都有P(16 - (Len - i + 1), i - 1)个数字串将已确定的第1到i位作为前缀。每次用这个个数扣除输入的序数Count，直到序数Count将扣为负数时停止，就确定了当前位的数字。
12  
13 注意不能有前导0。
14 **/
15 #include <iostream>
16 
17 using namespace std;
18 char num[16]={‘0‘,‘1‘,‘2‘,‘3‘,‘4‘,‘5‘,‘6‘,‘7‘,‘8‘,‘9‘,‘A‘,‘B‘,‘C‘,‘D‘,‘E‘,‘F‘};
19 int ans[10];
20 
21 int Axy(int x,int y){
22     int res =1;
23     if(y==0)
24         return 1;
25     while(y--){
26         res *= x;
27         x--;
28     }
29     return res;
30 }
31 
32 void solve(int count){
33     bool vis[16]={0},head = false;
34     int uselen = 0,countv;
35     for(int i=1;i<=8;i++){
36         int cnt = 15;
37         while(cnt){
38             if(!vis[cnt]){
39                 if((countv = Axy(16-1-uselen,8-i))<count){
40                     count -= countv;
41                 }else{
42                     vis[cnt] = true;
43                     break;
44                 }
45             }
46             cnt--;
47         }
48         ans[i] = num[cnt];
49         if(head||ans[i]!=‘0‘) uselen++;
50         if(ans[i]!=‘0‘) head = true;
51     }
52 }
53 
54 int main()
55 {
56     int cnt;
57     while(cin>>cnt){
58         bool head = false;
59         solve(cnt);
60         for(int i=1;i<=8;i++){     
61             if(head||ans[i]!=‘0‘){     //去除前导0
62                 cout<<(char)ans[i];
63                 head = true;
64             }
65         }
66         if(!head)     // 若全为0 ，则输出0
67             cout<<0;
68         cout<<endl;
69     }
70     return 0;
71 }