【题意】

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

【分析】

   

  然后分析一下这题。

   假设A置换是(a1,a2,a3)(b1,b2,b3,b4)   【这里用循环表示

   那么A*A=(a1,a2,a3)(b1,b2,b3,b4)(a1,a2,a3)(b1,b2,b3,b4)

   不相交的循环满足交换律,so

   A*A=(a1,a2,a3)(a1,a2,a3)(b1,b2,b3,b4)(b1,b2,b3,b4)

   满足结合律 A*A=( (a1,a2,a3)(a1,a2,a3)) * ((b1,b2,b3,b4)(b1,b2,b3,b4))

  (a1,a2,a3)(a1,a2,a3)=(a1,a3,a2)

  (b1,b2,b3,b4)(b1,b2,b3,b4)=(b1,b3)(b2,b4)

  分析到这里可以考虑B了,先把B分成若干个不相交的循环,对于长度为n奇循环来说,他可以是两个长度为n的循环乘出来的,也可能是两个长度为2n的循环分裂成的。

  而对于长度为n偶循环来说,他只能是两个长度为2n的循环分裂成的。所以偶循环必须要长度相等的两两配对。

  也就是说如果有奇数个长度相同的偶循环,就输出NO,否则一定可以找到一个合法的A。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 30 int a[Maxn],ans[Maxn];
bool vis[Maxn]; char s[Maxn]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
for(int i=;i<=;i++) a[i+]=s[i]-'A'+;
memset(vis,,sizeof(vis));
memset(ans,,sizeof(ans));
for(int i=;i<=;i++) if(!vis[i])
{
int cnt=,x=i;
while(vis[x]==)
{
cnt++;
vis[x]=;
x=a[x];
}
ans[cnt]++;
}
bool ok=;
for(int i=;i<=;i+=)
{
if(ans[i]%==) ok=;
}
if(ok) printf("Yes\n");
else printf("No\n");
}
return ;
}

好机智哦,这样一看也不是很难啦。。

代码也很简单。。

2017-01-11 16:49:20

05-11 11:15