Codeforces979B、Treasure Hunt（模拟）
B. Treasure Hunt
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
After the big birthday party, Katie still wanted Shiro to have some more fun. Later, she came up with a game called treasure hunt. Of course, she invited her best friends Kuro and Shiro to play with her.
The three friends are very smart so they passed all the challenges very quickly and finally reached the destination. But the treasure can only belong to one cat so they started to think of something which can determine who is worthy of the treasure. Instantly, Kuro came up with some ribbons.
A random colorful ribbon is given to each of the cats. Each color of the ribbon can be represented as an uppercase or lowercase Latin letter. Let's call a consecutive subsequence of colors that appears in the ribbon a subribbon. The beauty of a ribbon is defined as the maximum number of times one of its subribbon appears in the ribbon. The more the subribbon appears, the more beautiful is the ribbon. For example, the ribbon aaaaaaa has the beauty of 77 because its subribbon a appears 77 times, and the ribbon abcdabc has the beauty of 22 because its subribbon abc appears twice.
The rules are simple. The game will have nn turns. Every turn, each of the cats must change strictly one color (at one position) in his/her ribbon to an arbitrary color which is different from the unchanged one. For example, a ribbon aaab can be changed into acab in one turn. The one having the most beautiful ribbon after nn turns wins the treasure.
Could you find out who is going to be the winner if they all play optimally?
Input
The first line contains an integer nn (0≤n≤1090≤n≤109) — the number of turns.
Next 3 lines contain 3 ribbons of Kuro, Shiro and Katie one per line, respectively. Each ribbon is a string which contains no more than 105105 uppercase and lowercase Latin letters and is not empty. It is guaranteed that the length of all ribbons are equal for the purpose of fairness. Note that uppercase and lowercase letters are considered different colors.
Output
Print the name of the winner ("Kuro", "Shiro" or "Katie"). If there are at least two cats that share the maximum beauty, print "Draw".
Examples
input
Copy
3
Kuroo
Shiro
Katie
output
Copy
Kuro
input
Copy
7
treasurehunt
threefriends
hiCodeforces
output
Copy
Shiro
input
Copy
1
abcabc
cbabac
ababca
output
Copy
Katie
input
Copy
15
foPaErcvJ
mZaxowpbt
mkuOlaHRE
output
Copy
Draw
Note
In the first example, after 33 turns, Kuro can change his ribbon into ooooo, which has the beauty of 55, while reaching such beauty for Shiro and Katie is impossible (both Shiro and Katie can reach the beauty of at most 44, for example by changing Shiro's ribbon into SSiSS and changing Katie's ribbon into Kaaaa). Therefore, the winner is Kuro.
In the fourth example, since the length of each of the string is 99 and the number of turn is 1515, everyone can change their ribbons in some way to reach the maximal beauty of 99 by changing their strings into zzzzzzzzz after 9 turns, and repeatedly change their strings into azzzzzzzz and then into zzzzzzzzz thrice. Therefore, the game ends in a draw.
一、原题地址
二、大致题意
n表示要进行n次操作，接着给出三个字符串，表示三个人初始拥有的串。每次操作要替换字符串中的字母，询问最后在游戏中曾出现过的相同的子串谁最多。
三、思路
讨论最多的子串，肯定是全部转换成单个的字母是最优的，这样就把子串转换成了讨论出现过最多的字母的问题。接下来只需要模拟，先将初始串中有的最多的字母数统计出来，然后考虑一下剩下的字符数和n的关系就可以了。需要注意的是，初始的字符串是不计入统计的，也就是说，至少在经过一次操作后我们才对它们的最大长度进行比较。
四、代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int inf=0x3f3f3f3f;
int n;
int len;
int max1,max2,max3;
void print()
{
if(max1>max2&&max1>max3)
{
cout<<"Kuro"<<endl;
}
else if(max2>max1&&max2>max3)
{
cout<<"Shiro"<<endl;
}
else if(max3>max1&&max3>max2)
{
cout<<"Katie"<<endl;
}
else
cout<<"Draw"<<endl;
}
int work()
{
char s[200005];
int cnt[300];
memset(cnt,0,sizeof(cnt));
int ans=-1;
scanf("%s",s);
int len=strlen(s);
for(int i=0;i<len;i++)
{
cnt[s[i]]++;
ans=max(ans,cnt[s[i]]);
}
if(ans==len&&n==1)
return len-1;
else if(len-ans>=n)
return ans+n;
else
return len;
}
int main()
{
scanf("%d",&n);
max1=work();
max2=work();
max3=work();
print();
getchar();
getchar();
}