首页 > 代码库 > UVA - 12103 Leonardo's Notebook
UVA - 12103 Leonardo's Notebook
题目:链接
题意:给出26个大写字母的置换B,问是否存在一个置换A,使得A^2 = B
思路:总结一个规律:两个长度为n的相同循环相乘,当n为奇数时结果也是一个长度为n的循环;当n为偶数的时候分裂成两个长度为n/2的循环,所以对于一个长度为n的奇数循环都能找到一个长度为n的循环使得A^2=B,对于两个长度都为n的不相交的循环(不要求是偶数)B和C,都能找到一个长度为2n的循环A,使得A^2=BC,那么也就是说我们只要保证长度为偶数的循环,个数也为偶数就行了,至于一个循环分解,我们可以通过顺着有向边走来构成一个环
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { char B[30]; int vis[30], cnt[30], t; scanf("%d", &t); while (t--) { scanf("%s", B); memset(vis, 0, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < 26; i++) if (!vis[i]) { int j = i, n = 0; do { vis[j] = 1; j = B[j] - 'A'; n++; } while (j != i); cnt[n]++; } int flag = 1; for (int i = 2; i <= 26; i += 2) if (cnt[i] % 2 == 1) flag = 0; if (flag) printf("Yes\n"); else printf("No\n"); } return 0; }
UVA - 12103 Leonardo's Notebook
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。