题目大意

给定一个长度为 $n$ 的数组 $a$。玛莎（先手）和奥莉娅（后手）轮流进行操作，规则如下：

• 若数组长度为 $1$，游戏结束。
• 当前玩家选择两个不同下标 $i, j$，删除 $a_i, a_j$，并插入一个新数：$$\left\lfloor \frac{a_i + a_j}{2} \right\rfloor \cdot 2 $$即：先求和，除以 $2$ 向下取整，再乘以 $2$。

玛莎希望最终剩下的数尽可能大，奥莉娅希望尽可能小。双方均采取最优策略。

对于每个 $k = 1, 2, \dots, n$，求只使用数组前 $k$ 个元素进行游戏时，最终剩下的数。

---

操作性质分析

设两个被选中的数为 $x$ 和 $y$，考虑操作结果的奇偶性：

• 若 $x$ 与 $y$ 同奇偶（即同为奇数或同为偶数），则 $x+y$ 为偶数，$$\left\lfloor \frac{x+y}{2} \right\rfloor = \frac{x+y}{2} $$乘以 $2$ 后结果恰好为 $x+y$。此时操作相当于将两数直接替换为它们的和。
• 若 $x$ 与 $y$ 一奇一偶，则 $x+y$ 为奇数，$$\left\lfloor \frac{x+y}{2} \right\rfloor = \frac{x+y-1}{2} $$乘以 $2$ 后结果为 $x+y-1$。此时操作相当于将两数替换为它们的和减 $1$。

因此，每一步操作要么保持总和不变（同奇偶），要么使总和减少 $1$（一奇一偶）。

由于玛莎希望总和尽可能大，她会尽量避免总和减少，即优先选择同奇偶的数进行操作，尤其是选择两个奇数（因为两个奇数合并后变为偶数，总和不变）。奥莉娅希望总和尽可能小，她会尽量选择一奇一偶的数进行操作，使得总和减少 $1$。

---

最优策略下的变化规律

观察数组中的奇数个数 $C$ 的变化：

• 选择两个奇数操作：两个奇数被移除，产生一个偶数（因为奇数+奇数=偶数）。此时奇数个数减少 $2$。
• 选择一奇一偶操作：移除一个奇数和一个偶数，产生一个偶数（奇+偶=奇，向下取整乘 $2$ 得偶数）。此时奇数个数减少 $1$。
• 选择两个偶数操作：移除两个偶数，产生一个偶数。奇数个数不变。

可见，奇数的个数只会减少或不变，不会增加。

玛莎作为先手，希望总和不变，因此她会优先选择两个奇数。如果当前奇数个数 $\ge 2$，她一定会这么做。奥莉娅后手，希望总和减少，她会尽量选择一奇一偶。注意，由于玛莎每次选择两个奇数会产生一个偶数，所以奥莉娅在行动时总能找到至少一个偶数（除非数组长度为 $1$）。

因此，游戏过程可以描述为：

• 只要奇数个数 $\ge 2$，玛莎就会消耗两个奇数，使奇数个数减少 $2$，总和不变。
• 随后奥莉娅消耗一个奇数和一个偶数，使奇数个数再减少 $1$，总和减少 $1$。
• 如此一轮（玛莎一步 + 奥莉娅一步）下来，奇数个数减少 $3$，总和减少 $1$。

当奇数个数不足 $2$ 时，玛莎无法再保持总和不变，只能选择两个偶数或一奇一偶，此后总和会进一步减少。但我们可以直接根据最终奇数的余数情况推导结果。

---

最终结果的推导

设前 $k$ 个元素的总和为 $S$，奇数个数为 $C$。考虑在最优策略下，最终剩下的唯一数值。

注意到每一步一奇一偶的操作会使总和减少 $1$，而总和减少的次数恰好等于奥莉娅执行这种操作的次数（玛莎偶尔也可能被迫执行，但根据最优策略，她会尽量避免）。通过分析奇数的变化规律，可以得到一个简洁的公式。

根据题解思路，结论如下：

• 当 $k = 1$ 时，游戏无法进行，答案为 $a_1$。
• 当 $k > 1$ 时：
  • 若 $C \bmod 3 = 0$，答案为 $S - \dfrac{C}{3}$；
  • 若 $C \bmod 3 = 1$，答案为 $S - \left\lfloor \dfrac{C}{3} \right\rfloor - 1$；
  • 若 $C \bmod 3 = 2$，答案为 $S - \left\lfloor \dfrac{C}{3} \right\rfloor$。

用数学语言统一表示为：

$$\text{Ans} = S - \left\lfloor \frac{C}{3} \right\rfloor - [C \bmod 3 = 1] \quad (k > 1) $$

其中 $[C \bmod 3 = 1]$ 为艾佛森括号，当余数为 $1$ 时值为 $1$，否则为 $0$。

公式解释：每一组完整的 $3$ 个奇数（玛莎消耗两个，奥莉娅消耗一个）会使总和减少 $1$，对应 $\lfloor C/3 \rfloor$ 次减少。若余数为 $1$，说明最后剩一个奇数，奥莉娅还有一次机会将其与一个偶数配对，使总和再减少 $1$；若余数为 $2$，则玛莎的最后一步会直接合并这两个奇数，总和不再减少。

---

算法步骤

1. 读入测试用例数 $t$。
2. 对于每个测试用例：
   • 读入 $n$ 和数组 $a$。
   • 初始化前缀和 $S = 0$，奇数个数 $C = 0$。
   • 遍历 $k = 0$ 到 $n-1$：
     • $S \gets S + a_k$；
     • 若 $a_k$ 为奇数，$C \gets C + 1$；
     • 若 $k = 0$，输出 $S$（即 $a_1$）；
     • 否则计算 $\text{Ans} = S - \lfloor C/3 \rfloor$，若 $C \bmod 3 = 1$ 则 $\text{Ans} \gets \text{Ans} - 1$，并输出。
   • 换行。

---

复杂度分析

• 时间复杂度：每个测试用例只需一趟线性扫描，计算前缀和并更新答案，复杂度为 $O(n)$。所有测试用例总 $n$ 不超过 $10^5$，完全可行。
• 空间复杂度：存储数组 $a$ 需要 $O(n)$ 空间，也可边读入边处理以优化至 $O(1)$ 额外空间。

---

C++ 代码（标程）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];

        ll sum = 0;
        int cnt = 0;
        for (int k = 0; k < n; ++k) {
            sum += a[k];
            if (a[k] % 2 == 1) ++cnt;

            if (k == 0) {
                cout << sum << " ";
            } else {
                ll ans = sum - cnt / 3;
                if (cnt % 3 == 1) ans -= 1;
                cout << ans << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

---

补充说明

• 该解法利用了“奇数个数减少 $3$ 对应总和减少 $1$”的规律，避免了复杂的状态模拟。
• 证明过程涉及对双方最优决策的博弈分析，核心在于玛莎总是能优先合并两个奇数，而奥莉娅总能找到偶数来搭配奇数，从而使得游戏按照固定节奏进行。
• 对于 $k=1$ 的特殊处理是因为此时无法操作，直接输出原数。