【Codeforces Round #482 (Div. 2) B】Treasure Hunt

在这里输入题意

【题解】

我们考虑每个字符串中出现最多的字母出现的次数cnt[3]
对于这3个cnt的值。
如果cnt+n但是如果cnt+n>s[i].size()

那就有问题了。

因为每次变换的字母不能和原来的一样。

因此全都变成某个字母之后。接下来肯定会破坏这个全都一样的性质。

所以我们可以这样。

贪心地全都变成这个出现次数最多的字母。

直到只剩下一个字母不为这个字母,也即"xxxaxxxx"中的a

然后我们设剩余轮数为cnt,那么我们再用cnt次操作把这个a一直变换,变成a,b,c,...然后在最后一次把它变成x

这样就能保证最大了。

但是有一种情况例外。

就是n1,然后cnt[i]s[i].size()

这种情况只能变换一次。

显然是变不回来的。

(也就是说全都是这个出现次数最多的字母

所以最大值是s[i].size()-1;

【代码】

#include <bits/stdc++.h>

#define ll long long

#define pb push_back

#define inf 0x3f3f3f3f

#define pll pair<ll,ll>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep1(i,a,b) for(int i=a;i>=b;i--)

#define rson rt<<1|1,m+1,r

#define lson rt<<1,l,m

using namespace std;

const int N=1e5+100;

int n,cnt[3],rest[3];

string s[3];

map<char,int> mmap[3];

struct abc{

    string s;

    int num;

}b[3];

bool cmp(abc a,abc b){

    return a.num>b.num;

}

int main()

{

    ios::sync_with_stdio(false),cin.tie(0);

    cin>>n;

    rep(i,0,2) cin >> s[i];

    rep(i,0,2){

        rep(j,0,(int)s[i].size()-1){

            mmap[i][s[i][j]]++;

            cnt[i] = max(cnt[i],mmap[i][s[i][j]]);

        }

    }

    b[0].s = "Kuro";

    b[1].s = "Shiro";

    b[2].s = "Katie";

    rep(i,0,2) {

        if (cnt[i]+n>(int)s[i].size()){

            if (cnt[i]==(int)s[i].size() && n==1) cnt[i] = (int)s[i].size()-1;

            else cnt[i] = (int)s[i].size();

        }else cnt[i] = cnt[i]+n;

        b[i].num = cnt[i];

    }

    sort(b+0,b+0+3,cmp);

    if (b[0].num==b[1].num){

        cout<<"Draw"<<endl;

    }else{

        cout<<b[0].s<<endl;

    }

    return 0;

}

巴特西

【Codeforces Round #482 (Div. 2) B】Treasure Hunt

最新文章

热门文章