[CSP-S 2024] 擂台游戏

GitHub 跳转原题关系图返回列表

把赛程看成满二叉树，预处理确定赢家与自由前缀，再用差分统计每个叶子可能夺冠的前缀区间。

OJ: luogu

题目 ID: P11234

难度:省选/NOI-

标签:树形结构动态规划

日期: 2026-06-22 18:45

题意

有 n 位已报名选手，第 i 位选手编号为 i，能力为 a_i。对某个前缀 c，只收到前 c 位选手，需要补充最少的人，使总人数变成 2 的幂。

比赛是固定赛程的淘汰赛。每场比赛会指定左边或右边的胜者作为擂主。若擂主能力至少为当前轮次，擂主获胜；否则另一方获胜。

补充选手能力可以任意选择。如果补充选手可能成为冠军，也要计入答案。对每个询问 c_i，求所有可能冠军编号之和，最后按题目要求输出加权 xor。

思路

先看一个小数据暴力：对补充选手枚举能力值，再模拟整棵比赛树，收集所有可能冠军。

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n, m, max_k;
int base_ability[MAXN], current_ability[MAXN], query_c[MAXN];
int draw_round[10][MAXN];
set<int> possible_winner;

int ceil_power_log(int x) {
    int k = 0;
    while ((1 << k) < x) {
        k++;
    }
    return k;
}

int simulate_tournament(int total_players, int k, int ability[]) {
    vector<int> player;
    for (int i = 1; i <= total_players; i++) {
        player.push_back(i);
    }

    for (int round_id = 1; round_id <= k; round_id++) {
        vector<int> next_player;
        int games = (int)player.size() / 2;
        for (int g = 1; g <= games; g++) {
            int left = player[(g - 1) * 2];
            int right = player[(g - 1) * 2 + 1];
            int lord, other;

            if (draw_round[round_id][g] == 0) {
                lord = left;
                other = right;
            } else {
                lord = right;
                other = left;
            }

            if (ability[lord] >= round_id) {
                next_player.push_back(lord);
            } else {
                next_player.push_back(other);
            }
        }
        player = next_player;
    }

    return player[0];
}

void enumerate_unknown(int pos, int total_players, int known_count, int k, int ability[]) {
    if (pos > total_players) {
        possible_winner.insert(simulate_tournament(total_players, k, ability));
        return;
    }

    if (pos <= known_count) {
        enumerate_unknown(pos + 1, total_players, known_count, k, ability);
        return;
    }

    // 补充选手只需要枚举 0..k，能力超过 k 与 k 等价。
    for (int value = 0; value <= k; value++) {
        ability[pos] = value;
        enumerate_unknown(pos + 1, total_players, known_count, k, ability);
    }
}

long long champion_sum_for_prefix(int prefix_len) {
    int k = ceil_power_log(prefix_len);
    int total_players = 1 << k;
    int ability[MAXN];

    for (int i = 1; i <= total_players; i++) {
        if (i <= prefix_len) {
            ability[i] = current_ability[i];
        } else {
            ability[i] = 0;
        }
    }

    possible_winner.clear();
    enumerate_unknown(1, total_players, prefix_len, k, ability);

    long long sum = 0;
    for (set<int>::iterator it = possible_winner.begin(); it != possible_winner.end(); ++it) {
        sum += *it;
    }
    return sum;
}

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

    cin >> n >> m;
    max_k = ceil_power_log(n);

    for (int i = 1; i <= n; i++) {
        cin >> base_ability[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> query_c[i];
    }

    for (int round_id = 1; round_id <= max_k; round_id++) {
        string s;
        cin >> s;
        for (int j = 0; j < (int)s.size(); j++) {
            draw_round[round_id][j + 1] = s[j] - '0';
        }
    }

    int test_count;
    cin >> test_count;
    while (test_count--) {
        int mask_value[4];
        for (int i = 0; i < 4; i++) {
            cin >> mask_value[i];
        }

        for (int i = 1; i <= n; i++) {
            current_ability[i] = base_ability[i] ^ mask_value[i & 3];
        }

        long long ans = 0;
        for (int i = 1; i <= m; i++) {
            ans ^= 1LL * i * champion_sum_for_prefix(query_c[i]);
        }

        cout << ans << '\n';
    }

    return 0;
}

补充选手能力超过总轮数 K 后没有区别，所以暴力只枚举 0..K。但补充人数可能很多，仍然是指数级。

正解把赛程看成一棵满二叉树。叶子是选手编号，内部结点是一场比赛。对某个前缀 c，前 c 个叶子是已知选手，后面的叶子是补充选手。

我们希望反过来统计：每个叶子在哪些前缀长度下可能成为冠军。若一个编号 id 能在前缀区间 [l,r] 中成为冠军，就把 id 加到这个区间上。最后对差分数组做前缀和，就得到每个 c 的答案。

需要维护几个树上信息：

变量	含义
`fixed_winner[u]`	子树 `u` 完全确定时，最终赢家的能力
`free_time[u]`	子树 `u` 最后仍可能受补充选手影响的前缀位置
`known_limit[leaf]`	已知选手能力能支持它通过的最高补齐层级
`front_limit[leaf]`	从根往下看，这个叶子不被确定赢家挡住的最大前缀

fixed_winner 和 free_time 可以自底向上计算。叶子如果是已知选手，它在前缀达到自己之前还不可用，所以自由时刻是 pos - 1；补充叶子一直可以自由选择能力。

known_limit 处理的是已知选手自身能力够不够。沿着叶子到根的路径，如果它所在的一侧被抽为擂主，就必须满足对应轮次的能力要求。

front_limit 处理的是“会不会被对面确定赢家挡住”。对每个补齐规模 2^W，从对应子树根向下传播限制：若某一侧确定赢家已经足够赢当前轮，就会压缩另一侧叶子的可行前缀范围。

最后枚举补齐规模 W 和叶子：

如果叶子是已知选手，且 known_limit 支持它打到这一层，就把它能成为冠军的前缀区间加入差分；
如果叶子是补充选手，只要它所在位置在当前前缀之后，且没有被 front_limit 挡住，也把它的前缀区间加入差分。

对差分数组做前缀和后，answer_prefix[c] 就是前缀 c 的可能冠军编号和。

代码

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXNODE = 300005;

int n, m, max_k, base_size;
int ability[MAXN], query_c[MAXN];
int draw_side[MAXNODE];       // 内部结点抽到 0/1，0 表示左边为擂主
int log_floor_value[MAXNODE]; // 堆编号的 floor(log2)
int fixed_winner[MAXNODE];    // 子树完全确定时，赢家的能力值
int free_time[MAXNODE];       // 子树最后仍可能自由变化的前缀时刻
int father_need[MAXNODE];     // 从当前结点往上，选手作为擂主需要满足的最高轮次
int known_limit[MAXNODE];     // 已知选手能力能通过的祖先限制
int front_limit[MAXNODE];     // 从上往下 DP 得到的可贡献前缀上界
long long answer_prefix[MAXN + 5];

int min_int(int x, int y) {
    return x < y ? x : y;
}

int max_int(int x, int y) {
    return x > y ? x : y;
}

void prepare_tree_info() {
    base_size = 1 << max_k;

    for (int i = 2; i < base_size * 2; i++) {
        log_floor_value[i] = log_floor_value[i >> 1] + 1;
    }

    father_need[1] = max_k;
    for (int i = 2; i < base_size * 2; i++) {
        int parent = i >> 1;
        int is_right_child = i & 1;

        // 如果这个孩子所在的半区是擂主，记录跳到这里后还需要满足的层级限制。
        if (is_right_child == draw_side[parent]) {
            father_need[i] = max_k - log_floor_value[i];
        } else {
            father_need[i] = father_need[parent];
        }
    }
}

void build_fixed_winner() {
    for (int pos = 1; pos <= base_size; pos++) {
        int node = base_size + pos - 1;
        if (pos <= n) {
            free_time[node] = pos - 1;
            fixed_winner[node] = ability[pos];
        } else {
            free_time[node] = base_size;
            fixed_winner[node] = 0;
        }
    }

    for (int pos = 1; pos <= n; pos++) {
        int node = base_size + pos - 1;
        int climb = ability[pos] < max_k ? ability[pos] : max_k;
        known_limit[node] = father_need[node >> climb];
    }

    for (int node = base_size - 1; node >= 1; node--) {
        int left = node << 1;
        int right = left | 1;
        int round_id = max_k - log_floor_value[node];

        if (draw_side[node] == 0) {
            if (fixed_winner[left] < round_id) {
                free_time[node] = free_time[right];
                fixed_winner[node] = fixed_winner[right];
            } else {
                free_time[node] = free_time[left];
                fixed_winner[node] = fixed_winner[left];
            }
        } else {
            // 右边是擂主。自由性来自右边擂主是否能跨过当前轮，所以始终继承右子树的自由时刻。
            free_time[node] = free_time[right];
            if (fixed_winner[right] >= round_id) {
                fixed_winner[node] = fixed_winner[right];
            } else {
                fixed_winner[node] = fixed_winner[left];
            }
        }
    }
}

void solve_current_abilities() {
    for (int i = 0; i <= n + 2; i++) {
        answer_prefix[i] = 0;
    }

    build_fixed_winner();

    // W 表示当前前缀补齐到 2^W 人。
    for (int W = 0; W <= max_k; W++) {
        int lower_bound_prefix = (W == 0) ? 0 : (1 << (W - 1));
        int root_offset = (1 << (max_k - W)) - 1;

        front_limit[root_offset + 1] = base_size;

        for (int id = 1; id < (1 << W); id++) {
            int node = (root_offset << log_floor_value[id]) + id;
            int left = node << 1;
            int right = left | 1;
            int round_id = max_k - log_floor_value[node];

            front_limit[left] = front_limit[node];
            front_limit[right] = front_limit[node];

            if (draw_side[node] == 0) {
                if (fixed_winner[left] >= round_id) {
                    front_limit[right] = min_int(front_limit[right], free_time[node]);
                } else {
                    front_limit[left] = min_int(front_limit[left], free_time[left]);
                }
            } else {
                if (fixed_winner[right] >= round_id) {
                    front_limit[left] = min_int(front_limit[left], free_time[node]);
                } else {
                    front_limit[right] = min_int(front_limit[right], free_time[right]);
                }
            }
        }

        for (int i = 0; i < (1 << W); i++) {
            int player_id = i + 1;
            int leaf = base_size + i;

            // 已知选手成为冠军的前缀区间。
            if (player_id <= n && known_limit[leaf] >= W && front_limit[leaf] >= player_id &&
                front_limit[leaf] >= lower_bound_prefix + 1) {
                int left = max_int(player_id, lower_bound_prefix + 1);
                int right = min_int(front_limit[leaf], 1 << W);
                if (left <= right && left <= n) {
                    right = min_int(right, n);
                    answer_prefix[left] += player_id;
                    answer_prefix[right + 1] -= player_id;
                }
            }

            // 补充选手成为冠军的前缀区间。
            if (W > 0 && i > lower_bound_prefix && front_limit[leaf] >= lower_bound_prefix) {
                int left = lower_bound_prefix + 1;
                int right = min_int(i, front_limit[leaf]);
                if (left <= right && left <= n) {
                    right = min_int(right, n);
                    answer_prefix[left] += player_id;
                    answer_prefix[right + 1] -= player_id;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        answer_prefix[i] += answer_prefix[i - 1];
    }
}

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

    cin >> n >> m;
    while ((1 << max_k) < n) {
        max_k++;
    }
    base_size = 1 << max_k;

    for (int i = 1; i <= n; i++) {
        cin >> ability[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> query_c[i];
    }

    for (int round_id = 1; round_id <= max_k; round_id++) {
        string s;
        cin >> s;
        int start = 1 << (max_k - round_id);
        for (int j = 0; j < (int)s.size(); j++) {
            draw_side[start + j] = s[j] - '0';
        }
    }

    prepare_tree_info();

    int test_count;
    cin >> test_count;
    while (test_count--) {
        int mask_value[4];
        for (int i = 0; i < 4; i++) {
            cin >> mask_value[i];
        }

        for (int i = 1; i <= n; i++) {
            ability[i] ^= mask_value[i & 3];
        }

        solve_current_abilities();

        long long ans = 0;
        for (int i = 1; i <= m; i++) {
            ans ^= 1LL * i * answer_prefix[query_c[i]];
        }

        for (int i = 1; i <= n; i++) {
            ability[i] ^= mask_value[i & 3];
        }

        cout << ans << '\n';
    }

    return 0;
}

复杂度

设 K = ceil(log2 n)。每组 xor 测试数据的复杂度为 $O(n log n)$ ，空间复杂度为 $O(n)$ 。

总结

这题难点不是模拟比赛，而是同时处理所有前缀。核心做法是把“某个选手能否夺冠”转成“某个叶子在哪些前缀中可行”，再用差分统一统计。

树上自底向上的 fixed_winner/free_time 负责确定子树信息，自顶向下的 front_limit 负责传播阻挡条件。两部分合起来，就能得到每个叶子的可行前缀区间。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P11234 [CSP-S 2024] 擂台游戏

题目描述

小 S 想要举办一场擂台游戏，如果共有 $2^k$ 名选手参加，那么游戏分为 $k$ 轮进行：

第一轮编号为 $1, 2$ 的选手进行一次对局，编号为 $3, 4$ 的选手进行一次对局，以此类推，编号为 $2^k - 1, 2^k$ 的选手进行一次对局。
第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
以此类推，第 $k - 1$ 轮在只保留第 $k - 2$ 轮的 $4$ 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
第 $k$ 轮即为半决赛两位胜者的决赛。

确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 $a_1, a_2, \dots , a_{2^k}$ ，能力值为 $[0,2^{31}-1]$ 之内的整数。对于每场比赛，会先抽签决定一个数 $0/1$ ，我们将第 $R$ 轮的第 $G$ 场比赛抽到的数记为 $d_{R,G}$ 。抽到 $0$ 则表示表示编号小的选手为擂主，抽到 $1$ 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 $a\geq R$ 。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。

现在，小 S 先后陆续收到了 $n$ 位选手的报名信息，他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 $1, 2, \dots, n$ 。小 S 关心的是，补充尽量少的选手使总人数为 $2$ 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和是多少。

形式化地，设 $k$ 是最小的非负整数使得 $2^k\geq n$ ，那么应当补充 $(2^k-n)$ 名选手，且补充的选手的能力值可以任取 $[0,2^{31}-1]$ 之内的整数。如果补充的选手有可能取胜，也应当计入答案中。

当然小 S 觉得这个问题还是太简单了，所以他给了你 $m$ 个询问 $c_1,c_2,\dots,c_m$ 。小 S 希望你帮忙对于每个 $c_i$ 求出，在只收到前 $c_i$ 位选手的报名信息时，这个问题的答案是多少。

输入格式

本题的测试点包含有多组测试数据。 但不同测试数据只是通过修改 $a_1, a_2, \dots , a_n$ 得到，其他内容均保持不变，请参考以下格式。其中 $\oplus$ 代表异或运算符， $a \bmod b$ 代表 $a$ 除以 $b$ 的余数。

输入的第一行包含两个正整数 $n, m$ ，表示报名的选手数量和询问的数量。

输入的第二行包含 $n$ 个非负整数 $a'_1,a'_2,\dots,a'_n$ ，这列数将用来计算真正的能力值。

输入的第三行包含 $m$ 个正整数 $c_1, c_2, \dots , c_m$ ，表示询问。

设 $K$ 是使得 $2^K \geq n$ 的最小的非负整数，接下来的 $K$ 行当中，第 $R$ 行包含 $2^{K-R}$ 个数（无空格），其中第 $G$ 个数表示第 $R$ 轮的第 $G$ 场比赛抽签得到的 $d_{R,G}=0/1$ 。

注意，由于询问只是将人数凑齐到 $2^k\geq c_i$ ，这里的 $k\leq K$ ，因此你未必会用到全部的输入值。

接下来一行包含一个正整数 $T$ ，表示有 $T$ 组测试数据。

接下来共 $T$ 行，每行描述一组数据，包含 $4$ 个非负整数 $X_0,X_1,X_2,X_3$ ，该组数据的能力值 $a_i=a'_i \oplus X_{i\bmod 4}$ ，其中 $1\leq i\leq n$ 。

输出格式

共输出 $T$ 行，对于每组数据，设 $A_i$ 为第 $i$ （ $1 \leq i \leq m$ ）组询问的答案，你只需要输出一行包含一个整数，表示 $(1\times A_1) \oplus (2\times A_2) \oplus \dots \oplus (m\times A_m)$ 的结果。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例 1 解释】

共有 $T = 4$ 组数据，这里只解释第一组。 $5$ 名选手的真实能力值为 $[1, 0, 0, 2, 1]$ 。 $5$ 组询问分别是对长度为 $5, 4, 1, 2, 3$ 的前缀进行的。

对于长度为 $1$ 的前缀，由于只有 $1$ 号一个人，因此答案为 $1$ 。
对于长度为 $2$ 的前缀，由于 $2$ 个人已经是 $2$ 的幂次，因此不需要进行扩充。根据抽签 $d_{1,1} = 1$ 可知 $2$ 号为擂主，由于 $a_2 < 1$ ，因此 $1$ 号获胜，答案为 $1$ 。
对于长度为 $3$ 的前缀，首先 $1$ 号、 $2$ 号比赛是 $1$ 号获胜（因为 $d_{1,1} = 1$ ，故 $2$ 号为擂主， $a_2 < 1$ ），然后虽然 $4$ 号能力值还不知道，但 $3$ 号、 $4$ 号比赛一定是 $4$ 号获胜（因为 $d_{1,2} = 0$ ，故 $3$ 号为擂主， $a_3 < 1$ ），而决赛 $1$ 号、 $4$ 号谁获胜都有可能（因为 $d_{2,1} = 1$ ，故 $4$ 号为擂主，如果 $a_4 < 2$ 则 $1$ 号获胜， $a_4 \geq 2$ 则 $4$ 号获胜）。综上所述，答案为 $1 + 4 = 5$ 。
对于长度为 $4$ 的前缀，我们根据上一条的分析得知，由于 $a_4 \geq 2$ ，所以决赛获胜的是 $4$ 号。
对于长度为 $5$ 的前缀，可以证明，可能获胜的选手包括 $4$ 号、 $7$ 号、 $8$ 号，答案为 $19$ 。

因此，该组测试数据的答案为 $(1 \times 19) \oplus (2 \times 4) \oplus (3 \times 1) \oplus (4 \times 1) \oplus (5 \times 5) = 5$ 。

【样例 2】

见选手目录下的 arena/arena2.in 与 arena/arena2.ans。

这组样例满足特殊性质 A。

【样例 3】

见选手目录下的 arena/arena3.in 与 arena/arena3.ans。

这组样例满足特殊性质 B。

【样例 4】

见选手目录下的 arena/arena4.in 与 arena/arena4.ans。

【样例 5】

见选手目录下的 arena/arena5.in 与 arena/arena5.ans。

【数据范围】

对于所有测试数据，保证： $2 \leq n, m \leq 10^5$ ， $0 \leq a_i, X_j < 2^{31}$ ， $1 \leq c_i \leq n$ ， $1 \leq T \leq 256$ 。

::cute-table{tuack}

测试点	$T=$	$n,m\leq$	特殊性质 A	特殊性质 B
$1\sim 3$	$1$	$8$	否	否
$4,5$	^	$500$	是	^
$6\sim 8$	^	^	否	是
$9,10$	^	$5000$	^	否
$11,12$	^	$10^5$	是	^
$13\sim 15$	^	^	否	是
$16,17$	$4$	^	^	否
$18,19$	$16$	^	^	^
$20,21$	$64$	^	^	^
$22,23$	$128$	^	^	^
$24,25$	$256$	^	^	^

特殊性质 A：保证询问的 $c_i$ 均为 $2$ 的幂次。

特殊性质 B：保证所有的 $d_{R,G} = 0$ 。