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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---