前言
- 一开始想枚举,发现如果要枚举出来,是 16的7次方,还要比较每个位上的数,会超时,于是得换种方法
分析
- 题目中说至少三个不同,也就是说不能出现五个相同的,那就可以用数组记录一下每一个合法编号的能构成的五位数,因为要从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; }
注意事项
因为情况数有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; }
最终运行结果: