UVa 1262 - Password（组合数）

发表于 分类于 ， Disqus：

给出两个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博客，格式可能有所偏差。 **

相关文章