LA 3641 Leonardo's Notebook / 置换

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

给出26个大写字母组成 字符串B问是否存在一个置换A使得A^2 = B

书上的证明结论

2个长度为n的相同循环相乘 n为奇数时结果为1个长度为n的循环 n为偶数时分裂成2个长度为n/2的循环

倒过来

对于一个长度为n为奇数的循环B都能找到一个长度为n的循环A使得A^2 = B 对应任意2个长度为n的不相交循环B,C 都能找到一个长度为2n的循环A 使得A^2 = BC

所以对于B=(1,3,4)(2,5)(6,9)(7,8)输出No 因为长度为偶数的循环有奇数个

以上白书有介绍

对于输入的B 算出所有循环的长度 在判断一下 长度为偶数的是否有偶数个

#include <cstdio>
#include <cstring>
using namespace std;int main()
{char s[30];int vis[30], cnt[30], T;scanf("%d", &T);while(T--){scanf("%s", s);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 = s[j] - 'A';n++;}while(j != i);cnt[n]++;}}int ok = 1;for(int i = 2; i <= 26; i += 2)if(cnt[i]%2)ok = 0;if(ok)puts("Yes");elseputs("No");}return 0;
}

 

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

---