UVa 1262 - Password(组合数)

给出两个6*5矩阵,有一个5位的密码,密码的第i位必须在两个矩阵的第i列都出现过,问输出字典序第k大的满足条件的密码,无解输出“NO”。
预处理出每一位满足条件的字母,然后计算后几位密码可行的种数。对k进行判断后输出,具体细节见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
char s[2][7][6];
bool has[2][6][27];
vector<char> ok[5];
int main(){
int t;scanf("%d",&t);
while(t--){
fill(ok,ok+5,vector<char>());
memset(has,0,sizeof has);
int k;scanf("%d",&k);
for(int i=0;i<2;++i)
for(int j=0;j<6;++j)
scanf("%s",s[i][j]);
for(int i=0;i<5;++i)
for(int j=0;j<6;++j){
has[0][i][s[0][j][i]-'A']=true;
has[1][i][s[1][j][i]-'A']=true;
}
for(int i=0;i<5;++i)
for(int j=0;j<26;++j)
if(has[0][i][j]&&has[1][i][j])
ok[i].push_back(j+'A');
int a[6];a[5]=1;
for(int i=4;i>=0;--i) a[i]=a[i+1]*int(ok[i].size());
if(k>a[0]){puts("NO");continue;}
--k;
for(int i=0;i<5;++i){
putchar(ok[i][k/a[i+1]]);
k%=a[i+1];
}
putchar('\n');
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。