题目链接: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(置换),布布扣,bubuko.com
uva 12103 - Leonardo's Notebook(置换)
原文:http://blog.csdn.net/keshuai19940722/article/details/38533327