题意:昨晚做的时候,这题读的不是很清晰,感觉有点懵,三个人寻宝,到达了目的地,但是不知道宝藏应该属于谁,就给了三个彩段的字符串,区分大小写,表示不同的颜色,最美的彩段就是子序列(字母)出现最多的,宝藏归最美彩段的人所有,这句. 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. 理解出来的和样例给出的感觉天差地别,翻译出来的就更不能看了,通过有那么一些英语基础,可以知道必须改变n次颜色,每次改变的颜色不同于未改变的颜色。当时这句话,对着样例去看,顿时感觉没读题,懵了...
题解:贪心 看别人代码后,我觉得题意,描述的还是有些问题的。扫面每个字符串,把每个字符串找出里面单独字母出现最多的个数。然后判断
改变次数n如果为1次,并且当前字符串全是一样的,改变一次后,最大的长度为n-1。其余就是max+n和len取最小值。因为如果n的次数大于字符的长度后,肯定输出draw,就不需要必须去算当前每个字符串的具体长度,那样又要考虑很多,脑壳痛....就把它赋值为len。当然也适合那种小于len的。一石二鸟。
#include<bits/stdc++.h>
using namespace std;
map<char,int>x,y,z;
int n,max1,max2,max3,len;
int main()
{
string a,b,c;
cin>>n;
cin>>a>>b>>c;
len=a.size();
for(int i=0; i<len; i++)
{
x[a[i]]++,max1=max(x[a[i]],max1); ///记录每个字符出现最大次数
y[b[i]]++,max2=max(y[b[i]],max2);
z[c[i]]++,max3=max(z[c[i]],max3);
}
if(n==1&&max1==len) max1--; ///特判n==1和max==len的特殊情况
else max1=min(max1+n,len);
if(n==1&&max2==len) max2--;
else max2=min(max2+n,len);
if(n==1&&max3==len) max3--;
else max3=min(max3+n,len);
if(max1>max2&&max1>max3)
puts("Kuro");
else if(max2>max1&&max2>max3)
puts("Shiro");
else if(max3>max1&&max3>max2)
puts("Katie");
else puts("Draw");
return 0;
}