Codeforces Round #482 (Div. 2) B、Treasure Hunt（模拟+贪心）979B

大致题意

n表示要进行n次操作，接着给出三个字符串，表示三个人初始拥有的串。每次操作要替换字符串中的字母，询问最后在游戏中曾出现过的相同的子串谁最多。

思路

（1）讨论最多的子串，肯定是全部转换成单个的字母是最优的，这样就把子串转换成了讨论出现过最多的字母的问题。接下来只需要模拟，先将初始串中有的最多的字母数统计出来，然后考虑一下剩下的字符数和n的关系就可以了。需要注意的是，初始的字符串是不计入统计的，也就是说，至少在经过一次操作后我们才对它们的最大长度进行比较。

（2）显然只需关注字符而非子串。

枚举每个字符，尽力使其他字符变成它。

只有一种情况需要注意！如果字符a的出现次数等于len，并且n=1，那么你不得不将一个字符a变为其他的字符，最终最多只能有len-1个a.

AC代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<map>

#include<string.h>

using namespace std;

map<char,int>mp;

char s[];

int n;

int so()

{

    int ans=-;

    mp.clear();

    cin>>s;

    int len=strlen(s);

    for(int i= ; i<len ; i++)

    {

        mp[s[i]]++;

        ans=max(ans,mp[s[i]]);

    }

    if(ans==len&&n==)

        return len-;

    else if(ans+n<=len)

        return ans+n;

    else

        return len;

}

int main( )

{

    int max1,max2,max3;

    scanf("%d",&n);

    max1=so();

    max2=so();

    max3=so();

    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");

}

巴特西

Codeforces Round #482 (Div. 2) B、Treasure Hunt（模拟+贪心）979B

大致题意

最新文章

热门文章