首页 > 代码库 > UVa 1262 (第k字典序) Password
UVa 1262 (第k字典序) Password
题意：
给出两个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开始的。
1 //#define DEBUG 2 #include <cstdio> 3 #include <cstring> 4 5 char G[2][6][5], ans[6], select[6][5]; 6 int vis[2][26], hehe[6], cnt[5]; 7 8 int main() 9 {10 //freopen("in.txt", "r", stdin);11 12 int T;13 scanf("%d", &T);14 hehe[5] = 1;15 while(T--)16 {17 memset(cnt, 0, sizeof(cnt));18 int k;19 scanf("%d", &k);20 k--; //字典序标号从0开始21 for(int i = 0; i < 2; ++i)22 for(int j = 0; j < 6; ++j)23 scanf("%s", G[i][j]);24 25 for(int i = 0; i < 5; ++i)26 {27 memset(vis, 0, sizeof(vis));28 for(int j = 0; j < 2; ++j)29 for(int k = 0; k < 6; ++k)30 vis[j][G[j][k][i]-‘A‘] = 1;31 for(int j = 0; j < 26; ++j)32 if(vis[0][j] && vis[1][j])33 select[i][cnt[i]++] = ‘A‘ + j;34 }35 36 #ifdef DEBUG37 for(int i = 0; i < 5; ++i)38 {39 for(int j = 0; j < select[i].size(); ++j)40 printf("%c", select[i][j]);41 puts("");42 }43 #endif // DEBUG44 45 for(int i = 4; i >= 0; --i)46 hehe[i] = cnt[i] * hehe[i+1];47 if(k >= hehe[0])48 {49 puts("NO");50 continue;51 }52 for(int i = 0; i < 5; ++i)53 {54 int m = k / hehe[i+1];55 ans[i] = select[i][m];56 k = k % hehe[i+1];57 }58 ans[5] = ‘\0‘;59 60 printf("%s\n", ans);61 }62 63 return 0;64 }
解法二：
因为密码最多有65 = 7776种，所以可以按字典序从小到大枚举。
思维难度小，写起来更快更对。
1 #include <cstdio> 2 #include <cstring> 3 4 int k, cnt; 5 char G[2][6][5], ans[6]; 6 7 bool dfs(int col) 8 { 9 if(col == 5)10 {11 if(++cnt == k)12 {13 ans[col] = ‘\0‘;14 printf("%s\n", ans);15 return true;16 }17 return false;18 }19 20 bool vis[2][26];21 memset(vis, false, sizeof(vis));22 for(int i = 0; i < 2; ++i)23 for(int j = 0; j < 6; ++j)24 vis[i][G[i][j][col] - ‘A‘] = 1;25 for(int i = 0; i < 26; ++i)26 if(vis[0][i] && vis[1][i])27 {28 ans[col] = i + ‘A‘;29 if(dfs(col+1)) return true;30 }31 return false;32 }33 34 int main()35 {36 //freopen("in.txt", "r", stdin);37 int T;38 scanf("%d", &T);39 while(T--)40 {41 scanf("%d", &k);42 for(int i = 0; i < 2; ++i)43 for(int j = 0; j < 6; ++j)44 scanf("%s", G[i][j]);45 46 cnt = 0;47 if(!dfs(0)) puts("NO");48 }49 50 return 0;51 }
UVa 1262 (第k字典序) Password
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。