UVA

UVA - 1262

题意：

有两个6*5 的大写字母组成的矩阵，需要找出满足条件的字典序第k小的密码：密码中每个字母在两个矩阵的对应的同一列中都出现过

代码：

// 先处理出来每一列可以取的字母，例如：{A,B,C,D},{W,F,T},{R,T},{E,P,K},{V,M} 那么k最大不超过
// 4*3*2*3*2=144，当k<=3*2*3*2=36 时第一个字母一定是‘A’，当 36<k<=72 时第一个字母一定是‘B’，如此来
// 确定每一位字母。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,k,nu[8],sum[8][8];
bool a[8][30],s[8][30];
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d",&k);
        memset(a,0,sizeof(a));
        memset(s,0,sizeof(s));
        memset(nu,0,sizeof(nu));
        char str[10];
        int ans[8];
        for(int i=1;i<=6;i++){
            scanf("%s",str);
            for(int j=0;j<5;j++)
                a[j+1][str[j]-'A']=1;
        }
        for(int i=1;i<=6;i++){
            scanf("%s",str);
            for(int j=0;j<5;j++){
                if(a[j+1][str[j]-'A'])
                    s[j+1][str[j]-'A']=1;
            }
        }
        for(int i=1;i<=5;i++){
            int p=0;
            for(int j=0;j<26;j++){
                if(s[i][j]) sum[i][++p]=j;
            }
            nu[i]=p;
        }
        int x=nu[1];
        for(int i=2;i<=5;i++) x*=nu[i];
        if(k>x) printf("NO
");
        else{
            int l=1;
            while(l<=5){
                x/=nu[l];
                for(int i=1;i<=nu[l];i++){
                    int y=i*x;
                    if(k<=y){
                        k-=(y-x);
                        ans[l]=i;
                        break;
                    }
                }
                l++;
            }
            for(int i=1;i<=5;i++)
                printf("%c",'A'+sum[i][ans[i]]);
            printf("
");
        }
    }
    return 0;
}