程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVALA 3641 Leonardo’s Notebook

UVALA 3641 Leonardo’s Notebook

編輯：C++入門知識

UVALA 3641 Leonardo’s Notebook

Polya定理應用:

題意：給出一個置換B，問有沒有一個置換A，使得A^2=B。

思路：對於置換的循環節，比如(a1,a2,a3)和(b1,b2,b3,b4)，那麼對於奇數長度的循環節，發現進行兩次乘法以後還是奇數長度，偶數長度的循環節分解為兩個長度相同的循環節。那麼就可以對B中的循環節進行判斷，奇數長度的不同管，這個總能找到滿足要求的，偶數循環節的數量也要是偶數，這樣才能兩兩配對。

3641 Leonardo’s Notebook

— I just bought Leonardo’s secret notebook! Rare object collector
Stan Ucker was really agitated but his friend, special
investigator Sarah Keptic was unimpressed.
— How do you know it is genuine?
— Oh, it must be, at that price. And it is written in the da
Vinci code. Sarah browsed a few of the pages. It was obvious
to her that the code was a substitution cipher, where each
letter of the alphabet had been substituted by another letter.
— Leonardo would have written the plain-text and left it to
his assistant to encrypt, she said. And he must have supplied
the substitution alphabet to be used. If we are lucky, we can
find it on the back cover!
She turned up the last page and, lo and behold, there was
a single line of all 26 letters of the alphabet:
QW ERT Y UIOP ASDF GHJKLZXCV BNM
— This may be Leonardo’s instructions meaning that each A in the plain-text was to be replaced
by Q, each B with W, etcetera. Let us see…
To their disappointment, they soon saw that this could not be the substitution that was used in the
book. Suddenly, Stan brightened.
— Maybe Leonardo really wrote the substitution alphabet on the last page, and by mistake his
assistant coded that line as he had coded the rest of the book. So the line we have here is the result of
applying some permutation TWICE to the ordinary alphabet!
Sarah took out her laptop computer and coded fiercely for a few minutes. Then she turned to Stan
with a sympathetic expression.
— No, that couldn’t be it. I am afraid that you have been duped again, my friend. In all probability,
the book is a fake.
Write a program that takes a permutation of the English alphabet as input and decides if it may
be the result of performing some permutation twice.
Input
The input begins with a positive number on a line of its own telling the number of test cases (at most
500). Then for each test case there is one line containing a permutation of the 26 capital letters of the
English alphabet.
Output
For each test case, output one line containing ‘Yes’ if the given permutation can result from applying
some permutation twice on the original alphabet string ABC…XYZ, otherwise output ‘No’.
ACM-ICPC Live Archive: 3641 – Leonardo’s Notebook 2/2
Sample Input
2
QWERTYUIOPASDFGHJKLZXCVBNM
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Sample Output
No
Yes

/* ***********************************************
Author        :CKboss
Created Time  :2015年05月06日 星期三 21時01分41秒
File Name     :UVALA3641.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

char str[30];
bool vis[30];
int len[50];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%s",str);

        memset(vis,0,sizeof(vis));
        memset(len,0,sizeof(len));

        for(int i=0;i<26;i++)
        {
            int id=str[i]-'A';
            if(vis[id]==true) continue;
            int loop=0;
            do
            {
                loop++;
                vis[id]=true;
                id=str[id]-'A';
            }while(vis[id]==false);

            len[loop]++;
        }

        bool flag=true;
        for(int i=2;i<=40&&flag;i+=2)
        {
            if(len[i]%2!=0) flag=false; 
        }

        if(flag) puts("Yes");
        else puts("No");
    }

    return 0;
}