[CQOI2012]编号

• 前言

  1. 一开始想枚举，发现如果要枚举出来，是 16的7次方，还要比较每个位上的数，会超时，于是得换种方法

• 分析

  1. 题目中说至少三个不同，也就是说不能出现五个相同的，那就可以用数组记录一下每一个合法编号的能构成的五位数，因为要从7位中选出5位，组合数是C(7,5)=21中情况。

• 代码

#include<bits/stdc++.h>

using namespace std;

const int N=17;

char ch[20]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

int k;
bool f[25][N][N][N][N][N];
//表示一个编号的任意五位数字 
int main()
{
    cin>>k;//第k小 
    memset(f,0,sizeof(f));
    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)
        {
            cout<<ch[a]<<ch[b]<<ch[c]<<ch[d]<<ch[e]<<ch[g]<<ch[h]<<"\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;
}

• 注意事项

  1. 因为情况数有21种，要尽量避免重复与漏算，可以提前写在纸上。提供一种枚举方法，用深搜的思路枚举，并
     且每一位从上一项之后枚举，你可以写个程序实现。这里把它贴出来。

     #include<bits/stdc++.h>
     using namespace std;
     const int N=10;
     int a[20],ans;
     char ch[20]={"abcdegh"};
     inline void dfs(int now,int t)
     {
     if(now>5)
     {
        for (int i=1;i<=5;i++)
            cout<<ch[a[i]];
        puts("");
        ans++;
        return ;
     }
     
     for (int i=t;i<=7;i++)
        a[now]=i-1,dfs(now+1,i+1);
     }
     int main()
     {
     dfs(1,1);
     
     printf("一共的情况数 : %d\n",ans);
     
     return 0;
     }

  2. 最终运行结果：