题目
题目大意
给两个(6)行(5)列的字母矩阵, 找出满足如下条件的"密码": 密码中的每个字母在两个矩阵的对应列中均出现。
给定(k)((k ≤ 7777)), 你的任务是找出字典序第(k)小的密码。如果不存在, 输出NO。
题解
通过观察, 我们发现(k)较小, 直接暴搜就行了。
代码
#include <cstdio>
#include <cstring>
long long T;
int n, countt;
char matrix[2][6][10], ans[10];
inline bool DepthFirstSearch(const int &column) {
if (column == 5) {
if (++countt == n) {
ans[5] = ' ';
printf("%s
", ans);
return true;
} else return false;
} else {
register bool vis[2][26];
memset(vis, 0 ,sizeof(vis));
for (register int i(0); i <= 1; ++i) {
for (register int j(0); j <= 5; ++j) {
vis[i][matrix[i][j][column] - 'A'] = true;
}
}
for (register int i(0); i <= 25; ++i) {
if (vis[0][i]==true && vis[1][i] == true) {
ans[column] = i + 'A';
if (DepthFirstSearch(column + 1)) return true;
}
}
}
return false;
}
int main(int argc, char const *argv[]) {
while (~scanf("%d", &T)) {
for (register int cases(1); cases <= T; ++cases) {
scanf("%d", &n);
for (register int i(0); i <= 1; ++i) {
for (register int j(0); j <= 5; ++j) {
scanf("%s", &matrix[i][j]);
}
}
countt = 0;
if (!DepthFirstSearch(0)) puts("NO");
}
}
return 0;
}