codeforces 1916C

构造题确实练思维
题目链接

题目大意

给定大小为$n$的数组$a$，两位玩家在自己回合进行以下操作

• 如果数组内仅有一个元素，则游戏结束
• 否则任选两个索引$i,j$，删除$a[i],a[j]$，并向数组内添加$(a[i]+a[j])/2?2$
  先手玩家希望最大化最后值，后手玩家希望最小化
  假定两人操作均为最佳方案，问最后值是多少

思路

索引对象为一奇一偶时，对最终答案的贡献是$?1$（操作后会变成两个偶数，让总和减少$1$），所以后手玩家最优选为一奇一偶，而先手玩家最优为消除所有的奇数
综上，每轮操作之后，总和减少$1$，同时减少三个奇数，所有操作之后总和减少$n奇数/3$
又最终奇数可能剩下$0,1,2$个，$0$和$2$对答案无贡献，$1$贡献为$?1$

ACcode

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;cin >> n;
    vector<int>a(n + 3);
    for (int i = 1;i <= n;i++)cin >> a[i];
    ll sum = a[1];
    int odd = 0, even = 0;
    if (a[1] % 2)odd++;
    else even++;
    cout << sum << ' ';
    for (int i = 2;i <= n;i++) {
        sum += a[i];
        if (a[i] % 2)odd++;
        else even++;
        if (odd % 3 == 1)cout << sum - 1 - odd / 3 << ' ';
        else cout << sum - odd / 3 << ' ';
    }
    cout << '\n';
}

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