本文主要是介绍poj 3128 Leonardo's Notebook（置换的幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=3128
大致题意：输入一串含26个大写字母的字符串，可以把它看做一个置换，判断这个置换是否是某个置换的平方。
思路：详解可参考置换群快速幂运算 研究与探讨。
可以先正着考虑一个置换的平方出现什么情况。对于置换中的循环，若其长度为偶数，平方以后一定分成了两个长度相等的循环，若长度是奇数，平方以后仍是一个循环，长度不变。因此，考虑当前置换，若某个循环的长度为偶数，那么它一定是原始置换平方得来的，而且等长度的循环一定有偶数个。对于长度为奇数的循环，它可能是原始置换某个长度为偶数的循环平方得到的，也可能是长度为奇数的循环平方得来的。所以，判定当前置换是否是某个置换的平方等价于判断当前置换 长度为偶数的循环个数是否为偶数个。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;const int maxn = 1010;
const int INF = 0x3f3f3f3f;int a[30];
char s[30];
int vis[30];
int num[30];bool solve()
{memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));int i;while(1){for(i = 1; i <= 26; i++)if(!vis[a[i]])break;if(i > 26)break;int cnt = 1;vis[i] = 1; //不要忘记标记iint t = a[i];vis[t] = 1;while(t != i){vis[t] = 1;t = a[t];cnt++;}if(cnt % 2 == 0) //是偶数，对应循环个数就加1num[cnt]++;}int flag = 1;for(int i = 2; i <= 26; i += 2){if(num[i] % 2 != 0){flag = 0;break;}}if(flag == 1)return true;return false;
}int main()
{int test;scanf("%d",&test);while(test--){scanf("%s",s+1);for(int i = 1; i <= 26; i++)a[i] = s[i]-'A' + 1;if(solve())printf("Yes\n");else printf("No\n");}return 0;
}
这篇关于poj 3128 Leonardo's Notebook（置换的幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
