此文章可以使用目录功能哟↑(点击上方[+])
Kattis <Cryptographer's Conundrum>
Accept: 0 Submit: 0
Time Limit: 2 seconds Memory Limit : 1024 MB
Problem Description
The walls of the corridors at the Theoretical Computer Science group (TCS) at KTH are all but covered with whiteboards. Some of the faculty members are cryptographers, and like to write cryptographic puzzles on the whiteboards. A new puzzle is added whenever someone discovers a solution to the previous one.
When Per walked in the corridor two weeks ago, he saw that the newest puzzle read “GuvfVfNGrfg”. After arriving at his computer, he quickly figured out that this was a simple ROT13 encryption of “ThisIsATest”.
The series of lousy puzzles continued next week, when a new puzzle read “VmkgdGFyIHPDpGtlcmhldGVuIHDDpSBzdMO2cnN0YSBhbGx2YXIK”. This was just base64-encoded text! “Enough with these pranks”, Per thought; “I’m going to show you!”
Now Per has come up with a secret plan: every day he will erase one letter of the cipher text and replace it with a different letter, so that, in the end, the whole text reads “PerPerPerPerPerPerPer”. Since Per will change one letter each day, he hopes that people will not notice.
Per would like to know how many days it will take to transform a given cipher text into a text only containing his name, assuming he substitutes one letter each day. You may assume that the length of the original cipher text is a multiple of 3.
For simplicity, you can ignore the case of the letters, and instead assume that all letters are upper-case.
Input
The first and only line of input contains the cipher text on the whiteboard. It consists of at most 300 upper-case characters, and its length is a multiple of 3.
Output
Output the number of days needed to change the cipher text to a string containing only Per’s name.
Sample Input
Sample Output
Problem Idea
解题思路:
【题意】
给你一个长度为3的倍数的仅有大写字母构成的字符串
每天可以修改一个字符
问至少需要多少天可以使字符串转变为"PERPERPER……PER"的形式
【类型】
暴力
【分析】
显然,字符串最终要变成"PERPERPER……PER"的形式
那对应不上的位肯定要替换
所有只需要遍历一遍,看有多少位对应不上,就至少需要多少天才能转变为"PERPERPER……PER"的形式
【时间复杂度&&优化】
O(strlen(s))
题目链接→Kattis <Cryptographer's Conundrum>
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 305;
const int M = 100005;
const int inf = 1000000007;
const int mod = 10007;
char s[N],ch[5]="PER";
int main()
{int i,ans;while(~scanf("%s",s)){ans=0;for(i=0;s[i]!='\0';i++)if(s[i]!=ch[i%3])ans++;printf("%d\n",ans);}return 0;
}