CF1916C题解_代码007

本文介绍: 所以先手的策略为：选择两个奇偶性相同的数相加，如果有两个以上的奇数就会选两个奇数（因为先手做一次操作会产生一个偶数，而先手肯定想要后手操作次数尽可能的少，且后手做一次操作要一奇一偶，但偶数数量已经不能减少（先手自己要操作），所以只能让奇数变少）。可以得知后手策略为：选择两个奇偶性不同的数相加，否则任选两数相加。，则剩下的一个奇数还会跟偶数操作一次所以还要减。可以发现如果两数奇偶性相同则。即为减一的个数，注意如果。我们可以发现一轮操作需要。个奇数，而且总和会减。，所以可以前缀奇数个数。，但如果奇偶性不同则。

分析

可以发现如果两数奇偶性相同则

⌊

⌋

⋅

lfloor frac{a_i + a_j}{2} rfloorcdot2

$⌊ \frac{a _{i} + a _{j}}{2} ⌋ \cdot 2$ 等于

a_i+a_j

$a_{i} + a_{j}$ ，但如果奇偶性不同则

⌊

⌋

⋅

lfloor frac{a_i + a_j}{2} rfloorcdot2

$⌊ \frac{a _{i} + a _{j}}{2} ⌋ \cdot 2$ 等于

−

a_i+a_j-1

$a_{i} + a_{j} - 1$ 。

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

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

我们可以发现一轮操作需要

$3$ 个奇数，而且总和会减

$1$ ，所以可以前缀奇数个数

cnt

$c n t$ 和前缀和

pre

$p re$ ，

cntdiv3

$c n t \div 3$ 即为减一的个数，注意如果

cnt

$c n t$ 模

$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;
}