牛客周赛129比赛实况及题解

¶比赛实况

在轻松解决前$3$题之后，$D$题开始卡了很久，不过看榜发现很多人$E$题骗了不少分，于是我也去做$E$题。在思考过程中，手玩两组样例发现一个神秘规律直接一发通过，最后花了很长时间，在结束前$3$分钟才做出$D$题。总体看来，这场的难度相对较低，当然本人对于树上问题之类的相对较弱，加上结合了概率论的知识，所以$F$题还是在赛时和赛后补题都给我造成了很大的麻烦，所以还是需要加强树上问题以及$DFS$相关问题的练习。

¶题解

¶A.小红的大小判断

语法题，只需要比较两个数字大小即可。

¶B.小红的大小再判断

语法题，只需要比较两个字符串大小即可。

¶C.小红的肥鹅健身房

简单模拟题。题目要求把两个相同的数字合并成比它大$1$的数字，如果合成的数字大于$k$可以得到$1$个金币，问最多可以合并多少次，以及最多能得到多少金币。由于值域较大，可以用$map$来存每个数字出现的次数，然后枚举$map$里的元素个数，数字$m$的合并次数$x=\frac{mp[m]}{2}$，如果$m+1\geq k$，就让金币数加上$x$。如果合并次数大于$0$（如果没判断是否大于$0$，会导致产生很多无用的键值对，从而导致超时），那么就让$mp[m+1]$加上$x$，最后输出合并的总次数和最多的金币数即可。虽然值域是$10^9$，但是最多产生的元素个数也是$O(n)$级别的，加上$map$的操作，总时间复杂度为$O(nlogn)$。

附上代码：

void moth()
{
    int n, m, s;
    cin >> n >> m >> s;
    map<int, int> mp;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int x;
            cin >> x;
            if (x)
                mp[x]++;
        }
    }
    int t = 0, ans = 0;
    for (auto [k, v] : mp)
    {
        int x = v / 2;
        t += x;
        if (x)
        {
            if (k + 1 >= s)
                ans += x;
            if (mp.find(k + 1) == mp.end())
                mp.insert({k + 1, x});
            else
                mp[k + 1] += x;
        }
    }
    cout << t << ' ' << ans << '\n';
}