SPOJ LEONARDO Leonardo Notebook

2023-11-07 20:19

文章标签 notebook spoj leonardo

本文主要是介绍SPOJ LEONARDO Leonardo Notebook，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

— 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:
QWERTYUIOPASDFGHJKLZXCVBNM 
— 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.

找规律可以发现，如果循环 $A$ 的长度 $n$ 为奇数，那么 $A^2$ 还是一个长度为 $n$ 的循环，如果是偶数， $A^2$ 就是两个长度为 $n\over 2$ 的循环的乘积。
所以长度为奇数的循环可以单独出现，但是长度为偶数的循环一定是成对出现的。只需要统计 B <script type="math/tex" id="MathJax-Element-360">B</script>中偶数长度的循环的个数，任意长度的循环必须恰好有偶数个。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int n=26;
char s[30];
int cnt[30],vis[30];
bool solve()
{int i,p,now;scanf("%s",s+1);memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(cnt));for (i=1;i<=n;i++)if (!vis[i]){p=s[i]-'A'+1;vis[p]=1;now=1;while (p!=i){p=s[p]-'A'+1;vis[p]=1;now++;}cnt[now]++;}for (i=2;i<=n;i+=2)if (cnt[i]&1) return 0;return 1;
}
int main()
{int T;scanf("%d",&T);while (T--)if (solve()) printf("Yes\n");else printf("No\n");
}