题目
题目大意
给两个\(6\)行\(5\)列的字母矩阵, 找出满足如下条件的"密码":
密码中的每个字母在两个矩阵的对应列中均出现。
给定\(k\)(\(k ≤ 7777\)), 你的任务是找出字典序第\(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
38
39
40
41
42
43
44
| #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] = '\0';
printf("%s\n", 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;
}
|