UVa1262 - Password（解码问题）

题目链接

简介：

给出两个6行5列的字母矩阵，一个密码满足：密码的第i个字母在两个字母矩阵的第i列均出现

然后找出字典序为k的密码，如果不存在输出NO

分析：

本题是一道经典的解码问题

我们先统计每一个位置上能放哪些字符：

对于第一个样例来说，我们得到ACDW、BOP、GMOX、AP、GSU

要确定第一个字母，如果1≤k≤72，则是A；如果73≤k≤144，则是C，以此类推

当然这道题还有一个投机取巧的方法：

因为密码最多有65 = 7776种，所以可以按字典序从小到大枚举

思维难度小，写起来更快更对

tip

但是我这个zz果断选择了第一种方法

这就导致我debug的时间大大增加

之后和暴力对拍，一开始拍出来一个一组

好像是无解的判断出了问题，但是也没找出什么问题

之后又拍，这次真的是什么都拍不出来了，但是交上去就是WA

我能怎么办呢，我也很绝望啊。。。

//这里写代码片
#include<cstdio>
#include<cstring>
#include<cstring>
#include<algorithm>

using namespace std;

int mp1[][],mp2[][];
int z[][],k,cnt[],ans[];
char s[];

void pre()
{
    int i,j,l;
    memset(z,,sizeof(z));
    memset(cnt,,sizeof(cnt));
    for (i=;i<=;i++)
    {
        for (j=;j<=;j++)
            for (l=;l<=;l++)
                if (mp1[j][i]==mp2[l][i])
                {
                    z[i][++cnt[i]]=mp1[j][i];
                    break;
                }
        sort(z[i]+,z[i]++cnt[i]); 
    }
}

int solve()
{
    int i,j;
    int mul[];
    memset(ans,,sizeof(ans));

    mul[]=;
    for (i=;i>=;i--) mul[i]=mul[i+]*cnt[i+];
    if (mul[]*cnt[]<k) return ;

    for (i=;i<=;i++)
    {
        j=;
        while (j*mul[i]<k) j++;
        if (k<=mul[i]*j) 
        {
            ans[i]=z[i][j];
            k-=mul[i]*(j-);
        }
    }
    return ;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&k);

        for (int i=;i<=;i++)
        {
            scanf("%s",&s);
            for (int j=;j<;j++)
                mp1[i][j+]=s[j]-'A';
        }
        for (int i=;i<=;i++)
        {
            scanf("%s",&s);
            for (int j=;j<;j++)
                mp2[i][j+]=s[j]-'A';
        }

        pre();

        if (solve())
           for (int i=;i<=;i++) printf("%c",'A'+ans[i]);
        else printf("NO");
        printf("\n");
    }
    return ;
}