Moorbles (USACO Silver 2024 February)

每一步如果选 Even 或 Odd，分别都可以计算出最坏情况下的结果：如果 $E$ 选择 Even/Odd，而 $K$ 个 $B$ 可能出的数字中有 Odd/Even 的，那么最坏结果就是最大的 Odd/Even 值的相反数（负值，也就是这时 $E$ 最坏情况是输）。如果没有，那么最坏结果就是最小的 Even/Odd 的值（正值，也就是这时 $E$ 最坏情况也是赢）。用 $v[i][c]$ 来表示第 $i$ 轮选择 $c$ （ $c=0$ 或 $1$ ）时的最坏结果净值。同时，令 $u[i] = \max(v[i][0], v[i][1])$ ，表示第 $i$ 轮的最坏结果中较好的那个。

我们可以用贪心（Greedy）的策略，按时间顺序决定每个 move 应该怎么选：

如果以下条件成立，即在第 $i$ 轮时， $E$ 应该选择 Even：当选择 Even 的时候，根据当前 move 的最坏结果（可能赚也可能亏），然后保证在未来所有时间，每个步骤选择 Even/Odd 的两个最坏结果中的较好的情况下，没有发生直接输掉的情况。如果这个不满足，但选 Odd 的时候满足，那就选 Odd。否则就直接输出 $-1$ 。

所以剩下的问题，就是怎样 $\mathcal{O}(\log n)$ 计算“在未来所有时间，每个步骤选择Even/Odd的两个最坏结果中的较好的情况下，是否发生直接输掉的情况”。这个是u[i]的从i+1开始的prefix sum最小值问题。

for (int i=m-1; i>=0; i--)
    min_psum[i] = min(0, min_psum[i+1]+u[i]);

这个意思是prefix sum的非正的最小值每次往前加一个u[i]，可以用这样的递推的方式求出来。我们理解一下这是递推的思路：假设min_psum[i+1]是正确的，那么min_psum[i]有两种情况，一个是min_psum[i+1]+u[i] < 0，那么它就是新的最小前缀和，另一种情况就是这个数>0，那么u[i]一定是正的，所以新的min_psum[i]就是0（空的前缀和）。试一些不同的情况（u[i]是正，负，min_psum是正负、零，可以验证这个计算方法是对的）。

然后就是：if (n + v[i][0] + min_psum[i+1] > 0)用来判断当前选择even是否可行。

所以，总体上是一个prefix sum + greedy的解法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t,n,m,k;
int v[300005][2], u[300005];
long long min_psum[300005];
int ans[300005];
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d", &n, &m, &k);
        // compute v[i][0] and v[i][1] from input
        min_psum[m] = 0;
        for (int i = 0; i < m; i++) {
            bool odd = false, even = false;
            int min_odd = 1e9, min_even = 1e9;
            int max_odd = -1e9, max_even = -1e9;
            for (int j = 0; j < k; j++) {
                int a;
                scanf("%d", &a);
                if (a & 1) {
                    odd = true;
                    min_odd = min(min_odd, a);
                    max_odd = max(max_odd, a);
                } else {
                    even = true;
                    min_even = min(min_even, a);
                    max_even = max(max_even, a);
                }
            }
            v[i][0] = odd ? -max_odd : min_even;
            v[i][1] = even ? -max_even : min_odd;
            u[i] = max(v[i][0], v[i][1]);
        }
 
        for (int i = m-1; i >= 0; i--)
            min_psum[i] = min(0LL, min_psum[i+1]+u[i]);
 
        // compute answer greedily with post sum
        bool ok = true;
        for (int i = 0; i < m; i++) {
            if (n + v[i][0] > 0 && n + v[i][0] + min_psum[i+1] > 0) {
                ans[i] = 0;
                n += v[i][0];
            } else if (n + v[i][1] > 0 && n + v[i][1] + min_psum[i+1] > 0) {
                ans[i] = 1;
                n += v[i][1];
            } else {
                ok = false;
                break;
            }
        }
        if (ok) {
            for (int i = 0; i < m; i++) {
                if (i) printf(" ");
                printf("%s", ans[i] ? "Odd" : "Even");
            }
            printf("\n");
        } else {
            printf("-1\n");
        }
    }
 
    return 0;
}