uva 12103 - Leonardo's Notebook(置换)

本文主要是介绍uva 12103 - Leonardo's Notebook(置换)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 12103 - Leonardo's Notebook

题目大意：给出26个字母的置换，问是否存在一个置换A，使得A2=B

解题思路：将给定置换分解成若干个不相干的循环，当循环的长度n为奇数时，可以由两个循环长度为n的循环的乘积得来，也可以由两个循环长度为2n的拆分而来；对于长度n为偶数的，只能由两个循环长度为2n的拆分而来，所以判断是否存在有循环长度为偶数的个数是奇数个即可。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 30;int main () {char s[maxn];int cas, v[maxn], c[maxn];scanf("%d", &cas);while (cas--) {memset(v, 0, sizeof(v));memset(c, 0, sizeof(c));scanf("%s", s);for (int i = 0; i < 26; i++) {if (v[i])continue;int j = i, ret = 0;do {v[j] = 1;j = s[j] - 'A';ret++;} while (i != j);c[ret]++;}bool flag = true;for (int i = 2; i < 26; i += 2)if (c[i]&1)flag = false;printf("%s\n", flag ? "Yes" : "No");}return 0;
}

这篇关于uva 12103 - Leonardo's Notebook(置换)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---