UVA12103 贪心+置换

题意：给出26个大写字母的置换B，问是否存在一个置换A，舍得A^2=B，如果存在输出Yes，否则输出No

题解：

　　研究一下置换A与A^2关系。

　　假设A=（a1 a2 a3）（b1 b2 b3 b4）

　　A^2=（a1 a2 a3）（b1 b2 b3 b4）（a1 a2 a3）（b1 b2 b3 b4）

　　不相交的循环乘法满足交换律。

　　A^2=（a1 a2 a3）（a1 a2 a3）（b1 b2 b3 b4）（b1 b2 b3 b4）

　　奇数的两个合并一定是奇数

　　偶数二个变两个。

　　所以：两个长度为n的相同循环相乘，当n为奇数结果也是一个长度为n的循环。

　　当n为偶数，分裂分为两个长度为n/2的循环。

　　对于n为奇数，可以找到两个奇数循环，使得A^2=B

　　因为n为偶数的循环只能是两个长度为2n的循环分裂而成的。所以对于任意偶数长度，

　　循环个数必须是偶数才能配对。

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int vis[],cnt[];

 char b[];

 int main()

 {

     int cas;scanf("%d",&cas);

     while(cas--)

     {

         scanf("%s",b);

         memset(vis,,sizeof(vis));

         memset(cnt,,sizeof(cnt));

         for (int i=;i<;i++)

             if (!vis[i])

              {

                  int j=i,n=;

                  do{

                      vis[j]=;

                      j=b[j]-'A';

                      n++;

                  }while(j!=i);

                  cnt[n]++;

             }

         int flag=;

         for (int i=;i<=;i+=)

             if (cnt[i]%==) flag=;

         if (flag) printf("Yes\n");

         else printf("No\n");

     }

 }

巴特西

UVA12103 贪心+置换

最新文章

热门文章