首页 > ACM题库 > HDU-杭电 > hdu 1975 Leonardo’s Notebook-数论应用-[解题报告]C++
2013
12-26

hdu 1975 Leonardo’s Notebook-数论应用-[解题报告]C++

Leonardo’s Notebook

问题描述 :

―I just bought Leonardo’s secret notebook! Rare object collector Stan Ucker was really agitated but his friend, special investigator Sarah Kepticwas 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:

QWERTYUIOPASDFGHJKLZXCVBNM

― This may be Leonardo’s instructions meaning that each A in the plain-text was to be replaced by Q, each B withW, 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.

输入:

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.

输出:

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.

样例输入:

2
QWERTYUIOPASDFGHJKLZXCVBNM
ABCDEFGHIJKLMNOPQRSTUVWXYZ

样例输出:

No
Yes

#include <iostream>
#include <string.h>
using namespace std;
int c[30],vis[30];
char a[30];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int i,j,k,t,flag=0;
        cin>>a;
        memset(c,0,sizeof(c));
        memset(vis,0,sizeof(vis));
        for(i=0;i<26;i++)
        {
            if(vis[i])continue;
            t=1;
            vis[i]=1;
            j=i;
            while(a[j]-'A'!=i)
            {
                t++;
                j=a[j]-'A';
                vis[j]=1;
            }
            c[t]++;
        }
        for(i=2;i<=26;i+=2)
        if(c[i]%2==1){flag=1;break;}
        if(flag)cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}
/*
(a1,a2,a3)就是a1->a2,a2->a3,a3->a1
(a1,a2,a3)*(a1,a2,a3)就是a1->a2->a3,a2->a3->a1,a3->a1->a2=(a1,a3,a2)

(b1,b2,b3,b4)*(b1,b2,b3,b4)就是b1->b2->b3,b2->b3->b4,b3->b4->b1,b4->b1->b2=(b1,b3)(b2,b4)

    本题求得是是否存在A*A=B,B为输入的置换
    通过研究我们可以得出,奇数长度相同循环相乘还是奇数循环,
偶数长度n相同循环相乘会分裂成两个长度为n/2的循环
    所以本题本题我们只要找B中偶数循环中是否出现奇数个,出现就是No,否则Yes。
因为奇数循环可以由相同长的奇数循环相乘得到,而偶数循环只能是成对的,由偶数循环相乘分裂得到。
*/

解题转自:http://blog.csdn.net/a601025382s/article/details/9817917


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。