uva1262Password

解码，暴力。

恬不知耻地把暴力题解放了上来，因为k比较小，直接暴力找到字符串第k大就可以了。

编码解码就是根据组合数学公式算出来它到底在哪。

dfs返回bool就能使得找到字典序第k大字符串以后退出dfs，节省时间。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxl = 30;

char s[3][maxl][maxl];

int ok[3][maxl][maxl];

int cnt[maxl],a[maxl][maxl];

int res,num,last;

int p[maxl];

bool dfs(int n) {

    if(n==6) {

        num++;

        if(num==last) {

            for(int i=1;i<=5;i++) printf("%c",p[i]+'A');

            printf("\n");

            return true;

        }

        return false;

    }

    for(int i=1;i<=cnt[n];i++) {

        p[n]=a[n][i];

        if(dfs(n+1)) return true;

    }

    return false;

}

int main() {

    int T;

    scanf("%d",&T);

    while(T--) {

        scanf("%d",&last);

        memset(ok,0,sizeof(ok));

        memset(cnt,0,sizeof(cnt));

        for(int k=1;k<=2;k++)

        for(int i=1;i<=6;i++) {

            scanf("%s",s[k][i]+1);

            for(int j=1;j<=5;j++)

                ok[k][j][s[k][i][j]-'A']=1;

        }

        for(int i=1;i<=5;i++)

        for(int j=0;j<26;j++)

            if(ok[1][i][j]&&ok[2][i][j])

                a[i][++cnt[i]]=j;

        res=1; num=0;

        for(int i=1;i<=5;i++) res*=cnt[i];

        if(res<last) printf("NO\n");

        else dfs(1);

    }

    return 0;

}