題目鏈接
紫書P323
題意：兩個6*5的字母矩陣，兩個矩陣每列相同的字母，每列取一個，求按照字典序第k小的序列
分析：
對于第一個樣例來說，我們得到{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就是第一個集合中的第幾個元素
求第二個集合的時候，k = k % 72 ...
還有一些處理的細節，在代碼中
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; int k; char G[2][10][10]; //一個三維的數組存儲兩個矩陣 int vis[2][30],cnt[10],he[10]; //vis[i][j]表示第i個矩陣第j個字母是否訪問，cnt是每一列的總數，he是后綴積 char Select[10][10],ans[10]; //select[i][j]表示第i行第j個字母 int main() {int test;scanf("%d", &test);while(test--){scanf("%d", &k);for(int i = 0; i < 2; i++){for(int j = 0; j < 6; j++)scanf("%s", G[i][j]);}memset(cnt, 0, sizeof(cnt));for(int i = 0; i < 5; i++) //找兩個矩陣對應的列中相同的元素處理的很好，對每一列對兩個矩陣一行一行的查找 {memset(vis, 0, sizeof(vis));for(int j = 0; j < 2; j++) {for(int m = 0; m < 6; m++)vis[j][ G[j][m][i] - 'A' ] = 1;}for(int j = 0; j < 26; j++){if(vis[0][j] && vis[1][j]) //兩個矩陣同一列都訪問過了Select[i][ ++cnt[i] ] = 'A' + j; //第i列第cnt[i]個放入這個字母 }}he[5] = 1;for(int i = 4; i >= 0; i--){he[i] = cnt[i] * he[i + 1];}if(k > he[0]){printf("NO\n");continue;}k--; //因為考慮到k == 1的情況for(int i = 0; i < 5; i++){int t = k / he[i + 1];ans[i] = Select[i][t + 1]; //對于每一個字母都是從1開始標號的，整除之后取下一個，就像k = 1時，每一列都得取第一個，對于最后一列的時候 t = 1，那就取第二個了，所以k--k = k % he[i + 1];}ans[5] = '\0';printf("%s\n", ans);}return 0; }
?
