编号 number
【题目描述】
你需要给一批商品编号，其中每个编号都是一个7位16进制数（由0~9，a~f组成）。为了防止在人工处理时不小心把编号弄错，要求任意两个编号至少由三个位置对应的数字不相同。第一个编号为0000000，第二个编号为不违反上述规定的前提下最小的编号，……，每次分配一个新编号时，总是选择不和前面编号冲突的最小编号（注意编号都是16进制数，可以比较大小）。按此规律，前面若干编号分别是：0000000,0000111,0000222，……，0000fff，0001012,0001103,0001230,0001321,0001456，……
输入k，你的任务时求出第k小的编号。
【输入】
第一行为整数k。
【输出】
输出第k小的编号（字母必须输出小写）。输入保证这个编号存在。
【样例】
number.in
20
number.out
0001321
【数据规模】
1-3数据点：k<=200
4-7数据点：k<=10000
8-10数据点：k<=200000
---------------------------------------------------------------------------------------------------------------------------------------------------
【题解】
今天做了去年的重庆省选题，第二次做还是跪了。（虽说去年lz是个猹。。）感冒了，调不出来程序，顺便就写个简单的题解吧。下面进入正题。。。
一道很简单的数位排列问题。本题是一个7位的16进制数排列，但可以简化为五维。题目中说至少有三位不相同，那么可以确定两个不相同数位。如果两个数位的位置不同，那么即使其它五个数都相同，也至少有三位不同。
废话不多说，直接上代码。。
1 /* 2 PROG:bzoj1805 3 ID:waiting 4 TYPE:数学 5 POINT: 6 { 7 排列组合。 8 本题是一个7位的16进制数排列，但可以简化为五位。 9 题目中说至少有三位不相同，那么可以确定两个不相同数位。如果两个数位的位置不同，那么即使其它五个数都相同，也至少有三位不同。 10 以下表示出排列： 11 --00000 12 -0-0000 13 -00-000 14 -000-00 15 -0000-0 16 -00000- 17 0--0000 18 0-0-000 19 0-00-00 20 0-000-0 21 0-0000- 22 00--000 23 00-0-00 24 00-00-0 25 00-000- 26 000--00 27 000-0-0 28 000-00- 29 0000--0 30 0000-0- 31 00000-- 32 ('0'表示可以相同的数字，'-'表示不同位) 33 根据排列组合C(7,2)=21，共有21种排列。 34 规定：a[i][a1][a2][a3][a4][a5]为第i种排列方式下除去不同位后剩下的五个数位分别a1、a2、a3、a4、a5。 35 } 36 */ 37 #include 38 #include 39 using namespace std; 40 #define MAXN 20 41 int k; 42 bool a[30][MAXN][MAXN][MAXN][MAXN][MAXN]; 43 int main() 44 { 45 scanf("%d",&k); 46 int a1,a2,a3,a4,a5,a6,a7; 47 for(a1=0;a1<=15;a1++) 48 for(a2=0;a2<=15;a2++) 49 for(a3=0;a3<=15;a3++) 50 for(a4=0;a4<=15;a4++) 51 for(a5=0;a5<=15;a5++) 52 for(a6=0;a6<=15;a6++) 53 for(a7=0;a7<=15;a7++) 54 { 55 if(!a[0][a3][a4][a5][a6][a7] 56 &&!a[1][a2][a4][a5][a6][a7] 57 &&!a[2][a2][a3][a5][a6][a7] 58 &&!a[3][a2][a3][a4][a6][a7] 59 &&!a[4][a2][a3][a4][a5][a7] 60 &&!a[5][a2][a3][a4][a5][a6] 61 &&!a[6][a1][a4][a5][a6][a7] 62 &&!a[7][a1][a3][a5][a6][a7] 63 &&!a[8][a1][a3][a4][a6][a7] 64 &&!a[9][a1][a3][a4][a5][a7] 65 &&!a[10][a1][a3][a4][a5][a6] 66 &&!a[11][a1][a2][a5][a6][a7] 67 &&!a[12][a1][a2][a4][a6][a7] 68 &&!a[13][a1][a2][a4][a5][a7] 69 &&!a[14][a1][a2][a4][a5][a6] 70 &&!a[15][a1][a2][a3][a6][a7] 71 &&!a[16][a1][a2][a3][a5][a7] 72 &&!a[17][a1][a2][a3][a5][a6] 73 &&!a[18][a1][a2][a3][a4][a7] 74 &&!a[19][a1][a2][a3][a4][a6] 75 &&!a[20][a1][a2][a3][a4][a5]) 76 { 77 k--; 78 if(!k) 79 { 80 printf("%x%x%x%x%x%x%x\n",a1,a2,a3,a4,a5,a6,a7); 81 return 0; 82 } 83 a[0][a3][a4][a5][a6][a7]=true; 84 a[1][a2][a4][a5][a6][a7]=true; 85 a[2][a2][a3][a5][a6][a7]=true; 86 a[3][a2][a3][a4][a6][a7]=true; 87 a[4][a2][a3][a4][a5][a7]=true; 88 a[5][a2][a3][a4][a5][a6]=true; 89 a[6][a1][a4][a5][a6][a7]=true; 90 a[7][a1][a3][a5][a6][a7]=true; 91 a[8][a1][a3][a4][a6][a7]=true; 92 a[9][a1][a3][a4][a5][a7]=true; 93 a[10][a1][a3][a4][a5][a6]=true; 94 a[11][a1][a2][a5][a6][a7]=true; 95 a[12][a1][a2][a4][a6][a7]=true; 96 a[13][a1][a2][a4][a5][a7]=true; 97 a[14][a1][a2][a4][a5][a6]=true; 98 a[15][a1][a2][a3][a6][a7]=true; 99 a[16][a1][a2][a3][a5][a7]=true; 100 a[17][a1][a2][a3][a5][a6]=true; 101 a[18][a1][a2][a3][a4][a7]=true; 102 a[19][a1][a2][a3][a4][a6]=true; 103 a[20][a1][a2][a3][a4][a5]=true; 104 } 105 } 106 return 0; 107 } 写得有点冗余，当时直接写了个小程序打出来的>_< 实在不想手码。。