[Poj3128]Leonardo's Notebook
标签： 置换
题意
给你一个置换(B)，让你判断是否有一个置换(A)使得(B=A^2)。
题解
置换可以写成循环的形式，所以我们不妨来研究循环平方的特性。
对于一个奇数长度的循环[(a_1 a_2 a_3 a_4 ...... a_{2n+1})，(a_1 a_2 a_3 a_4 ...... a_{2n+1})(a_1 a_2 a_3 a_4 ...... a_{2n+1})=（a_1 a_3 a_5 ...... a_{2n+1} a_2 a_4 ...... a_{2n}）]
平方之后仍是一个奇数长度的循环。
而偶数长度的循环平方之后则会分成两个长度相等的循环。
所以本题就很容易解决了。把置换写成循环的形式后，奇数长度的循环可以写成一个奇数长度循环的平方。对于偶数长度的循环只可能是一个偶数长度循环的平方。
我们只需要判断每一个偶数长度的循环的个数是不是偶数就行了。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<vector>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
int sum=0,p=1;char ch=getchar();
while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
if(ch=='-')p=-1,ch=getchar();
while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
return sum*p;
}
const int maxn=30;
int a[maxn],cnt[maxn];
int vis[maxn];
void init()
{
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
char s[maxn];
cin>>s;
REP(i,1,26)a[i]=s[i-1]-'A'+1;
}
void doing()
{
REP(i,1,26)
{
if(vis[i])continue;
int j=a[i],sum=1;
vis[i]=1;
while(j!=i)
{
vis[j]=1;
j=a[j];
sum++;
}
cnt[sum]++;
}
int flag=1;
REP(i,1,13)
{
if(cnt[i*2] & 1)
{
flag = 0;
break;
}
}
if(flag)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main()
{
int t=read();
while(t)
{
t--;
init();
doing();
}
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
