首页 > 代码库 > 【LA 3641】 Leonardo's Notebook (置换群)

【LA 3641】 Leonardo's Notebook (置换群)

【题意】

  给出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。

 

 

技术分享
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 30
 8 
 9 int a[Maxn],ans[Maxn];
10 bool vis[Maxn];
11 
12 char s[Maxn];
13 
14 int main()
15 {
16     int T;
17     scanf("%d",&T);
18     while(T--)
19     {
20         scanf("%s",s);
21         for(int i=0;i<=26;i++) a[i+1]=s[i]-A+1;
22         memset(vis,0,sizeof(vis));
23         memset(ans,0,sizeof(ans));
24         for(int i=1;i<=26;i++) if(!vis[i])
25         {
26             int cnt=0,x=i;
27             while(vis[x]==0)
28             {
29                 cnt++;
30                 vis[x]=1;
31                 x=a[x];
32             }
33             ans[cnt]++;
34         }
35         bool ok=1;
36         for(int i=2;i<=26;i+=2)
37         {
38             if(ans[i]%2==1) ok=0;
39         }
40         if(ok) printf("Yes\n");
41         else printf("No\n");
42     }
43     return 0;
44 }
View Code

 

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

代码也很简单。。

 

2017-01-11 16:49:20

 

【LA 3641】 Leonardo's Notebook (置换群)