【每日一题】8月28日题目精讲 编号
链接：https://ac.nowcoder.com/acm/problem/19925
来源：牛客网

题目描述

你需要给一批商品编号，其中每个编号都是一个7位16进制数（由0~9,
a-f组成）。为了防止在人工处理时不小心把编号弄错，要求任意两个编号至少有三个位置对应的数字不相同。第一个编号为0000000，第二个编号为不违反上述规定的前提下最小的编号，…，每次分配一个新编号时，总是选择不和前面编号冲突的最小编号（注意编号都是16进制数，可以比较大小）。
按此规律，前面若干编号分别是：0000000, 0000111, 0000222, …, 0000fff, 0001012,
0001103,0001230,0001321,0001456,… 输入k，你的任务是求出第k小的编号。

输入描述:
第一行为整数k。
输出描述:
输出第k小的编号（字母必须输出小写）。输入保证这个编号存在。
示例1
输入
复制

20

输出
复制

0001321

备注:
对于30%的数据，k≤200；
对于70%的数据，k≤10000；
对于100%的数据，k≤200000。

题解：

暴力出奇迹。。。
题目要求至少有三个位置对应的数字不相同
一个七个数，所以存五个数的信息就行，因为如果五个数一样那肯定不符合要求
七个选五个一共是21种方案
dp[i][a][b][c][d][e]表示第i个位置，5个位置的数是a,b,c,d,e
如果一个数可行也就是21种位置上的数都没被排除

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 10
#define for10(x) for (x=0;x<16;(x)++)

int a[30][16][16][16][16][16];
int main() {
        /////freopen("loop05.in","r",stdin);
        //freopen("loop05.out","w",stdout);
    int a1,a2,a3,a4,a5,a6,a7,k,s=0;
    cin>>k;
    for10(a1)
    for10(a2)
    for10(a3)
    for10(a4)
    for10(a5)
    for10(a6)
    for10(a7) {
        if(!a[0][a3][a4][a5][a6][a7]
                &&!a[1][a2][a4][a5][a6][a7]
                &&!a[2][a2][a3][a5][a6][a7]
                &&!a[3][a2][a3][a4][a6][a7]
                &&!a[4][a2][a3][a4][a5][a7]
                &&!a[5][a2][a3][a4][a5][a6]
                &&!a[6][a1][a4][a5][a6][a7]
                &&!a[7][a1][a3][a5][a6][a7]
                &&!a[8][a1][a3][a4][a6][a7]
                &&!a[9][a1][a3][a4][a5][a7]
                &&!a[10][a1][a3][a4][a5][a6]
                &&!a[11][a1][a2][a5][a6][a7]
                &&!a[12][a1][a2][a4][a6][a7]
                &&!a[13][a1][a2][a4][a5][a7]
                &&!a[14][a1][a2][a4][a5][a6]
                &&!a[15][a1][a2][a3][a6][a7]
                &&!a[16][a1][a2][a3][a5][a7]
                &&!a[17][a1][a2][a3][a5][a6]
                &&!a[18][a1][a2][a3][a4][a7]
                &&!a[19][a1][a2][a3][a4][a6]
                &&!a[20][a1][a2][a3][a4][a5]) {
            k--;
            if(!k) {
                printf("%x%x%x%x%x%x%x\n",a1,a2,a3,a4,a5,a6,a7);
                return 0;
            }
            a[0][a3][a4][a5][a6][a7]=true;
            a[1][a2][a4][a5][a6][a7]=true;
            a[2][a2][a3][a5][a6][a7]=true;
            a[3][a2][a3][a4][a6][a7]=true;
            a[4][a2][a3][a4][a5][a7]=true;
            a[5][a2][a3][a4][a5][a6]=true;
            a[6][a1][a4][a5][a6][a7]=true;
            a[7][a1][a3][a5][a6][a7]=true;
            a[8][a1][a3][a4][a6][a7]=true;
            a[9][a1][a3][a4][a5][a7]=true;
            a[10][a1][a3][a4][a5][a6]=true;
            a[11][a1][a2][a5][a6][a7]=true;
            a[12][a1][a2][a4][a6][a7]=true;
            a[13][a1][a2][a4][a5][a7]=true;
            a[14][a1][a2][a4][a5][a6]=true;
            a[15][a1][a2][a3][a6][a7]=true;
            a[16][a1][a2][a3][a5][a7]=true;
            a[17][a1][a2][a3][a5][a6]=true;
            a[18][a1][a2][a3][a4][a7]=true;
            a[19][a1][a2][a3][a4][a6]=true;
            a[20][a1][a2][a3][a4][a5]=true;
        }
    }
    return 0;
}