[CQOI2012]编号-题解

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

思路：参考他人的题解。就直接暴力枚举所有情况，但是处理冲突的方法比较厉害（妙蛙）。开一个数组记录之前某五位出现abcde的情况，如果有五位和之前相同，那么这种情况就和之前的产生冲突，直接continue。如果是合法的情况，就把所有的五位标记为1.
代码：

#include <bits/stdc++.h>
using namespace std;
int f[30][16][16][16][16][16];
void out(int w)
{
    if(w<=9&&w>=0)printf("%d",w);
    else printf("%c",'a'+w-10);
}
int main()
{
    int k;
    scanf("%d",&k);
    for(int a=0;a<16;a++)
    for(int b=0;b<16;b++)
    for(int c=0;c<16;c++)
    for(int d=0;d<16;d++)
    for(int e=0;e<16;e++)
    for(int g=0;g<16;g++)
    for(int h=0;h<16;h++){
        if(f[1][a][b][c][d][e]||f[2][a][b][c][d][g]||f[3][a][b][c][d][h]) continue;
        if(f[4][a][b][c][e][g]||f[5][a][b][c][e][h]||f[6][a][b][c][g][h]) continue;
        if(f[7][a][b][d][e][g]||f[8][a][b][d][e][h]||f[9][a][b][d][g][h]) continue;
        if(f[10][a][b][e][g][h]||f[11][a][c][d][e][g]||f[12][a][c][d][e][h]) continue;
        if(f[13][a][c][d][g][h]||f[14][a][c][e][g][h]||f[15][a][d][e][g][h]) continue;
        if(f[16][b][c][d][e][g]||f[17][b][c][d][e][h]||f[18][b][c][d][g][h]) continue;
        if(f[19][b][c][e][g][h]||f[20][b][d][e][g][h]||f[21][c][d][e][g][h]) continue;
        k--;
        if(k==0){
            out(a);
            out(b);
            out(c);
            out(d);
            out(e);
            out(g);
            out(h);
            printf("\n");
            return 0;
        }
        f[1][a][b][c][d][e]=f[2][a][b][c][d][g]=f[3][a][b][c][d][h]=1;
        f[4][a][b][c][e][g]=f[5][a][b][c][e][h]=f[6][a][b][c][g][h]=1;
        f[7][a][b][d][e][g]=f[8][a][b][d][e][h]=f[9][a][b][d][g][h]=1;
        f[10][a][b][e][g][h]=f[11][a][c][d][e][g]=f[12][a][c][d][e][h]=1;
        f[13][a][c][d][g][h]=f[14][a][c][e][g][h]=f[15][a][d][e][g][h]=1;
        f[16][b][c][d][e][g]=f[17][b][c][d][e][h]=f[18][b][c][d][g][h]=1;
        f[19][b][c][e][g][h]=f[20][b][d][e][g][h]=f[21][c][d][e][g][h]=1;
    }
    return 0;
}