CF1916C题解

洛谷题目链接

vjudge题目链接

Codeforces题目链接

分析

可以发现如果两数奇偶性相同则 $?\frac{a_i+a_j}{2}??2$ 等于 $a_i+a_j$，但如果奇偶性不同则 $?\frac{a_i+a_j}{2}??2$ 等于 $a_i+a_j?1$。

可以得知后手策略为：选择两个奇偶性不同的数相加，否则任选两数相加。

所以先手的策略为：选择两个奇偶性相同的数相加，如果有两个以上的奇数就会选两个奇数（因为先手做一次操作会产生一个偶数，而先手肯定想要后手操作次数尽可能的少，且后手做一次操作要一奇一偶，但偶数数量已经不能减少（先手自己要操作），所以只能让奇数变少）。

我们可以发现一轮操作需要 $3$ 个奇数，而且总和会减 $1$，所以可以前缀奇数个数 $cnt$ 和前缀和 $pre$，$cnt÷3$ 即为减一的个数，注意如果 $cnt$ 模 $3$ 等于 $1$，则剩下的一个奇数还会跟偶数操作一次所以还要减 $1$。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 5;
int T, n, a[N];

signed main(){
	for(cin >> T; T; T --){
		cin >> n;
		for(int i = 1; i <= n; i ++){
			cin >> a[i];
		}
		int pre = a[1], _ = a[1] & 1;
		cout << a[1] << " ";
		for(int i = 2; i <= n; i ++){
			pre += a[i];
			if(a[i] & 1){
				_ ++;
			}
			cout << pre - _ / 3 - (_ % 3 == 1) << " ";
		}
		cout << "\n";
	}
	return 0;
}