B. Treasure Hunt(思维)

https://codeforces.com/problemset/problem/979/B

---

题意翻译

在一场盛大的生日派对后，Katie（以下简称Ka）仍然想和Shiro(以下简称S）去找更多的乐子。不一会，她就想到了一个游戏，叫做寻宝。当然，她邀请了她最好的朋友Kuro（以下简称Ku）和S和她一起玩。 三个朋友都很聪明所以他们很快的通过了所有挑战并且终于到达了终点。但是宝藏只能属于一只猫（主角们都是猫），所以他们开始想个决定宝藏归属的法子。很快的，Ku带着一些丝带前来。 每只猫都被发放了一条随机颜色，鲜艳的丝带。每一种丝带的颜色都可以用大写字母或小写字母表示。我们定义：一种颜色的字母表达式内的一段连续子序列既是丝带中的一段子丝带。丝带美丽的程度由它的子丝带出现次数的最大值决定。越多子丝带，这条丝带就越美丽，比如说，aaaaaaa色的丝带有美丽值7，因为它的子序列出现了7次，abcdabc有美丽值2，因为它的子序列abc出现了两次。 规则很简单。游戏将会进行n轮，每一轮每一只猫都必须对自己的丝带改变严格的“一种”颜色（在自己的回合），使之变成不同于之前的随机颜色。比如说,aaab可以在一回合内变成acab。n轮游戏后美丽值最大的丝带的主人赢得比赛。

输入：

第一行包含一个整数n,代表回合数。 接下来的三行包含Ku,S，Ka的三条丝带，一条丝带各自占一行。每一条丝带都是一个字符串，包含不超过1e5的大小写字母组合而且不是空字符串。为了公平，保证三条丝带长度相同。注意大小写字母被认为表示了不同的颜色。

输出：

输出赢家的名字 ("Kuro", "Shiro" 或是 "Katie")，如果至少两只猫的丝带有相同的美丽值，那么输出“Draw（平局）”。

输入输出样例

输入 #1复制

3
Kuroo
Shiro
Katie

输出 #1复制

Kuro

输入 #2复制

7
treasurehunt
threefriends
hiCodeforces

输出 #2复制

Shiro

输入 #3复制

1
abcabc
cbabac
ababca

输出 #3复制

Katie

输入 #4复制

15
foPaErcvJ
mZaxowpbt
mkuOlaHRE

输出 #4复制

Draw

说明/提示

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.

---

写这题的时候有点秀逗，导致wa86.

思路：贪心去想，从当前串中拿到最大的字母去构造。然后比如aaaaa,n=4的时候可以把最后一位变成c,d,e...最后再变成a。一定可以满足。比如aaaac,n=4的时候，同理也可以满足。这样就发现只有刚好等于串长度并且n==1的时候必须是少一个的。

剩下的如果长了就能满足，不然就是n+最大字符个数。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5;
typedef long long LL;
map<char,LL>map1;
LL n;
LL cal(string k){
	map1.clear();
	for(LL i=0;i<k.size();i++){
		map1[k[i]]++;
	}
	LL ans=0;
	for(map<char,LL>:: iterator it=map1.begin();it!=map1.end();it++){
		ans=max(ans,it->second);
	}
	if(ans+n<=k.length()) return ans+n;
	else{
		if(n==1) return k.length()-1;
		else return k.length();
	}
}
int main(void)
{
  cin>>n;
  string a,b,c;cin>>a>>b>>c;
  LL sum1=cal(a);
  LL sum2=cal(b);
  LL sum3=cal(c);
  if(sum1>sum2&&sum1>sum3){
  	cout<<"Kuro"<<endl;
  }
  else if(sum2>sum1&&sum2>sum3){
  	cout<<"Shiro"<<endl;
  }
  else if(sum3>sum1&&sum3>sum2){
  	cout<<"Katie"<<endl;
  }
  else if(sum1==sum2||sum1==sum3||sum2==sum3){
  	cout<<"Draw"<<endl;
  }
return 0;
}