• 前言

    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. 最终运行结果:
      图片说明