题目链接

题意: Alice 和 Bob 玩游戏, 可以轮流对序列进行如下操作: 选择序列 a 中的某个数字 x, 然后:

1.对于a中每个x, 当前操作玩家获得1分.

2.序列a中所有x变为 x - 1

如果两人均希望最大化得分, 输出最终两人的分数.

稍微思考一下, 如果所有数字都是偶数, 那么后手可以通过复制先手的行动, 获得和先手完全一样的分数.

如果有多个奇数, 对于每个奇数其实只用考虑第一次拿, 拿完以后就会变成必然可以平分的偶数.

所以两者会贪心地把数目最多的奇数依次变成偶数, 并在所有数都变成偶数后平分剩下的分数.

代码:


#include <bits/stdc++.h>
#define int long long
using namespace std;

struct solve {
    int n, ansa = 0, ansb = 0, anss = 0;
    vector<int> a;
    map<int, int> mp;
    vector<pair<int, int>> vec;
    solve() {
        cin >> n;
        a.resize(n + 1);
        for (int i = 1; i <= n; i++) 
            cin >> a[i], mp[a[i]]++; 
    }
    void run() {
        for (auto [t, num] : mp) {
            vec.push_back({-num, t});
        }
        sort(vec.begin(), vec.end());
        int nm = 0;
        for (auto [num, t] : vec) {
            num = -num;
            if (t % 2 == 1) {
                nm++;
                if (nm % 2 == 1) {
                    ansa += num;
                } else {
                    ansb += num;
                }
                anss += (t - 1) * num;
            } else {
                anss += t * num;
            }
        }
        cout << ansa + (anss / 2) << ' ' << ansb + (anss / 2) << '\n';
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) {
        solve sl;
        sl.run();
    }
    return 0;
}

此题给我们的启示是, 博弈题可以从小的情况开始推理, 口胡一些看起来很对的做法, 然后就ac了()

当然, 我们也可以先进行搜索, 以找到规律: