Moorbles

题意

Elsie 每轮要猜 Bessie 取出的弹珠数 $A$ 是偶数还是奇数。

如果猜对，Elsie 从 Bessie 那里赢得 $A$ 个弹珠；如果猜错，Elsie 输掉 $A$ 个弹珠。某个玩家弹珠数变成 $0$ 时失败。

现在已知接下来每一轮 Bessie 只会从给定的 $K$ 个数中选择一个。要求输出一个字典序最小的 $Even/Odd$ 序列，使得无论 Bessie 每轮怎么选，Elsie 都不会输。如果不存在，输出 -1。

思路

先看小数据暴力：把每一轮看成一次二选一，递归枚举完整的 $Even/Odd$ 序列，再检查它是否安全。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 21:05
 * update_at: 2026-07-11 21:06
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 25;
const long long INF = (1LL << 60);

long long n;
int m, k;
long long change_val[MAXM][2];
int choose_seq[MAXM];
int answer_seq[MAXM];
bool found;

bool check_sequence() {
    long long cur = n;
    for (int i = 0; i < m; i++) {
        cur += change_val[i][choose_seq[i]];
        if (cur <= 0) return false;
    }
    return true;
}

// 按字典序生成完整的 Even/Odd 选择序列，再在叶子节点检查。
void dfs_choose(int dep) {
    if (found) return;

    if (dep == m) {
        if (check_sequence()) {
            found = true;
            for (int i = 0; i < m; i++) {
                answer_seq[i] = choose_seq[i];
            }
        }
        return;
    }

    for (int p = 0; p <= 1; p++) {
        choose_seq[dep] = p;
        dfs_choose(dep + 1);
        if (found) return;
    }
}

void solve_one() {
    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        change_val[i][0] = INF;
        change_val[i][1] = INF;

        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            int parity = x & 1;
            if (change_val[i][parity] > x) change_val[i][parity] = x;
            if (change_val[i][parity ^ 1] > -x) change_val[i][parity ^ 1] = -x;
        }
    }

    found = false;
    dfs_choose(0);

    if (!found) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 0; i < m; i++) {
        if (i) cout << ' ';
        if (answer_seq[i] == 0) {
            cout << "Even";
        } else {
            cout << "Odd";
        }
    }
    cout << '\n';
}

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

    int T;
    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

暴力能直接体现字典序：每一层先选 Even，再选 Odd。但序列数量是 $2^M$ ，必须优化。

先把每一轮压成两个“最坏变化量”：

数组	含义
`change[i][0]`	第 `i` 轮猜 `Even` 时，Bessie 最坏选择下 Elsie 的弹珠变化
`change[i][1]`	第 `i` 轮猜 `Odd` 时，Bessie 最坏选择下 Elsie 的弹珠变化

猜对时，Bessie 会让 Elsie 赢得尽量少；猜错时，Bessie 会让 Elsie 输得尽量多。

接下来倒着计算安全线：

text

1need[i] = 第 i 轮开始前，弹珠数必须严格大于多少，才存在后续不输策略

结束后不需要额外弹珠，所以：

text

1need[M] = 0

第 i 轮如果只考虑“后面还能活下去”，Elsie 会选择两个变化量中更好的一个。因此：

text

1need[i] = max(0, need[i+1] - max(change[i][0], change[i][1]))

这里要注意是“严格大于 need[i]”才安全，因为弹珠数等于 $0$ 已经输了。

有了 need 后，从前往后构造答案。每一轮先尝试字典序更小的 Even：

text

1
2如果 current + change[i][0] > need[i+1]，选 Even
否则选 Odd

如果 Even 后仍然高于下一轮安全线，说明后面一定存在安全策略，所以可以放心选 Even；否则所有以这个前缀接 Even 的方案都不可能安全，只能选 Odd。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 21:05
 * update_at: 2026-07-11 21:06
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 300005;
const long long INF = (1LL << 60);

long long n;
int m, k;
long long change_val[MAXM][2]; // 第 i 轮猜 0/1 时，Elsie 在最坏情况下的弹珠变化。
long long need[MAXM];          // need[i] 表示第 i 轮开始前，弹珠数必须严格大于它。
int answer[MAXM];

void solve_one() {
    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        change_val[i][0] = INF;
        change_val[i][1] = INF;

        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            int parity = x & 1;

            // 猜对时，Bessie 会让 Elsie 赢得尽量少。
            if (change_val[i][parity] > x) {
                change_val[i][parity] = x;
            }
            // 猜错时，Bessie 会让 Elsie 输得尽量多。
            if (change_val[i][parity ^ 1] > -x) {
                change_val[i][parity ^ 1] = -x;
            }
        }
    }

    need[m] = 0;
    for (int i = m - 1; i >= 0; i--) {
        long long best_change = max(change_val[i][0], change_val[i][1]);
        need[i] = need[i + 1] - best_change;
        if (need[i] < 0) need[i] = 0;
    }

    if (n <= need[0]) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 0; i < m; i++) {
        // Even 字典序更小，能保证后续安全就优先选 Even。
        if (n + change_val[i][0] > need[i + 1]) {
            answer[i] = 0;
            n += change_val[i][0];
        } else {
            answer[i] = 1;
            n += change_val[i][1];
        }
    }

    for (int i = 0; i < m; i++) {
        if (i) cout << ' ';
        if (answer[i] == 0) {
            cout << "Even";
        } else {
            cout << "Odd";
        }
    }
    cout << '\n';
}

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

    int T;
    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

每轮只处理 $K$ 个可能值，并维护两个变化量。

时间复杂度为 $O(MK)$ 。

空间复杂度为 $O(M)$ 。

总结

本题的关键是先把 Bessie 的所有选择压成“最坏情况下的变化量”，再倒推后缀安全线。

字典序最小不是最后排序出来的，而是在每一轮用安全线判断：能选 Even 就立刻选 Even，不能选才选 Odd。

目录

题意

思路

代码

复杂度

总结