题意：
给出两个6行5列的字母矩阵，一个密码满足：密码的第i个字母在两个字母矩阵的第i列均出现。
然后找出字典序为k的密码，如果不存在输出NO
分析：
我们先统计分别在每一列均在两个矩阵出现的字母，然后从小到大排好序。
对于第一个样例来说，我们得到ACDW、BOP、GMOX、AP、GSU
则一共有4×3×4×2×3=288种密码，我们先计算这个数列的后缀积：288、72、24、6、3、1
要确定第一个字母，如果1≤k≤72，则是A；如果73≤k≤144，则是C，以此类推。
确定第二个字母是类似的，用k%72+1与24去比较。
代码实现中，字典序是从0开始的。
//#define DEBUG
#include <cstdio>
#include <cstring> char G[][][], ans[], select[][];
int vis[][], hehe[], cnt[]; int main()
{
//freopen("in.txt", "r", stdin); int T;
scanf("%d", &T);
hehe[] = ;
while(T--)
{
memset(cnt, , sizeof(cnt));
int k;
scanf("%d", &k);
k--; //字典序标号从0开始
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
scanf("%s", G[i][j]); for(int i = ; i < ; ++i)
{
memset(vis, , sizeof(vis));
for(int j = ; j < ; ++j)
for(int k = ; k < ; ++k)
vis[j][G[j][k][i]-'A'] = ;
for(int j = ; j < ; ++j)
if(vis[][j] && vis[][j])
select[i][cnt[i]++] = 'A' + j;
} #ifdef DEBUG
for(int i = ; i < ; ++i)
{
for(int j = ; j < select[i].size(); ++j)
printf("%c", select[i][j]);
puts("");
}
#endif // DEBUG for(int i = ; i >= ; --i)
hehe[i] = cnt[i] * hehe[i+];
if(k >= hehe[])
{
puts("NO");
continue;
}
for(int i = ; i < ; ++i)
{
int m = k / hehe[i+];
ans[i] = select[i][m];
k = k % hehe[i+];
}
ans[] = '\0'; printf("%s\n", ans);
} return ;
}
代码君一
解法二：
因为密码最多有65 = 7776种，所以可以按字典序从小到大枚举。
思维难度小，写起来更快更对。
#include <cstdio>
#include <cstring> int k, cnt;
char G[][][], ans[]; bool dfs(int col)
{
if(col == )
{
if(++cnt == k)
{
ans[col] = '\0';
printf("%s\n", ans);
return true;
}
return false;
} bool vis[][];
memset(vis, false, sizeof(vis));
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
vis[i][G[i][j][col] - 'A'] = ;
for(int i = ; i < ; ++i)
if(vis[][i] && vis[][i])
{
ans[col] = i + 'A';
if(dfs(col+)) return true;
}
return false;
} int main()
{
//freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &k);
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
scanf("%s", G[i][j]); cnt = ;
if(!dfs()) puts("NO");
} return ;
}
代码君二