「IXOI R3」帮助她玩游戏

利用兑换门槛不超过 20，把可达钱数拆成低状态和统一平移的高状态，特殊机器再合并至多三份集合。

OJ: luogu

题目 ID: P17415

难度:提高

标签:数据结构集合Treap状态压缩

日期: 2026-09-06 19:06

形式化题目

依次经过若干台兑换机，初始钱数为 $x$ 。普通机器在钱数至少为 $a_i$ 时强制把钱数变为 $v-a_i+b_i$ ；特殊机器在满足门槛时可以跳过，或随机变为 $v-a_i+b_i$ 、 $v-a_i+c_i$ 。求所有选择与随机结果下最终可达的钱数集合，并回答若干个存在性查询。

解法路线

直接枚举每台特殊机器的三种选择会形成至多 $3^k$ 条分支。先把相同钱数合并成集合，可以通过 $n \leqslant 10$ 或 $k \leqslant 4$ 的子任务；正解继续利用 $a_i \leqslant 20$ ，让大量高状态不再逐个转移。正式主解位于最后的正解章节，对应 main.cpp。

暴力解法

思路

沿机器顺序递归。普通机器的下一状态唯一；特殊机器可产生跳过和两种兑换结果。枚举所有完整分支后，把最终钱数加入集合，再回答询问。

代码

不单独给出递归版本，因为下面的集合模拟使用完全相同的转移，并会自动合并到达同一钱数的重复分支。

复杂度与瓶颈

特殊机器最多产生三条分支，时间复杂度上界为 $O(n3^k)$ 。完整数据中 $k \leqslant 30$ ，不能枚举所有分支。

子任务解法： $n \leqslant 10$ 或 $k \leqslant 4$

适用范围

集合模拟直接覆盖 $n \leqslant 10$ 的小数据；当 $k \leqslant 4$ 时，可达状态数也很小，即使普通机器很多仍可逐状态转移。

思路

用集合保存当前所有可达钱数。经过普通机器时，每个状态只有一个后继；经过特殊机器时，加入跳过以及两种可能兑换得到的状态。集合会自动去除重复钱数。

代码

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/**
 * 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-09-06 19:06
 * update_at: 2026-09-07 15:18
 */
// brute.cpp：小数据暴力解，逐台维护所有可达钱数，用来辅助对拍。
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    long long x;
    cin >> n >> x >> q;
    set<long long> states;
    states.insert(x);
    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;
        set<long long> next_states;
        if (type == 0) {
            int a, b;
            cin >> a >> b;
            for (long long value : states) {
                if (value >= a) {
                    next_states.insert(value - a + b);
                } else {
                    next_states.insert(value);
                }
            }
        } else {
            int a, b, c;
            cin >> a >> b >> c;
            for (long long value : states) {
                next_states.insert(value);
                if (value >= a) {
                    next_states.insert(value - a + b);
                    next_states.insert(value - a + c);
                }
            }
        }
        states.swap(next_states);
    }
    while (q--) {
        long long y;
        cin >> y;
        cout << (states.count(y) ? 1 : 0) << '\n';
    }
    return 0;
}

复杂度与瓶颈

设过程中最多有 $S$ 个可达钱数，使用有序集合时复杂度约为 $O(nS \log S)$ 。虽然合并重复状态优于直接枚举分支，但完整数据中普通机器可达 $2.5 \times 10^5$ 台，不能让每台机器都扫描整个集合。

正解

关键观察

先看普通机器。所有门槛 $a_i \leqslant 20$ ，所以当前钱数 $v \geqslant 20$ 时一定会使用机器，整个高状态集合都只增加同一个 $b_i-a_i$ ；只有 $1 \dots 19$ 的低状态需要逐个判断。

思路

维护两部分：

low_mask：所有小于 $20$ 的可达钱数，直接用 20 位掩码保存；
高状态集合：保存去掉统一偏移 global_add 后的有序键。普通机器只需修改偏移、切出跌回低区间的键，再把低状态产生的新高状态插入。

特殊机器会让高状态集合变成三份有序集合：不使用、得到 $b_i$ 、得到 $c_i$ 。由于特殊机器最多 $30$ 台，把三份有序序列线性归并去重即可。低状态只有 $19$ 个，也直接枚举其三种结果。

高状态集合用 Treap 维护有序键，普通机器的每次操作是 $O(\log S)$ 加上常数个低状态处理；每台特殊机器只需线性扫描当前集合一次。

代码

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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356/**
 * 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-09-06 19:06
 * update_at: 2026-09-06 19:32
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct TreapNode {
    int left;
    int right;
    int size;
    ll key;
    unsigned int priority;
};

vector<TreapNode> tree(1);
vector<int> recycled;
int root = 0;
unsigned int random_seed = 712367821u;
ll global_add = 0;
int low_mask = 0; // 当前所有小于 20 的可达钱数。

unsigned int next_random() {
    random_seed ^= random_seed << 13;
    random_seed ^= random_seed >> 17;
    random_seed ^= random_seed << 5;
    return random_seed;
}

int node_size(int node) {
    return node == 0 ? 0 : tree[node].size;
}

void pull(int node) {
    if (node != 0) {
        tree[node].size = node_size(tree[node].left)
            + node_size(tree[node].right) + 1;
    }
}

int new_node(ll key) {
    int id;
    if (recycled.empty()) {
        TreapNode node;
        node.left = node.right = 0;
        node.size = 1;
        node.key = key;
        node.priority = next_random();
        tree.push_back(node);
        id = (int)tree.size() - 1;
    } else {
        id = recycled.back();
        recycled.pop_back();
        tree[id].left = tree[id].right = 0;
        tree[id].size = 1;
        tree[id].key = key;
        tree[id].priority = next_random();
    }
    return id;
}

void release_tree(int node) {
    if (node == 0) {
        return;
    }
    vector<int> stack;
    stack.push_back(node);
    while (!stack.empty()) {
        int current = stack.back();
        stack.pop_back();
        if (tree[current].left != 0) {
            stack.push_back(tree[current].left);
        }
        if (tree[current].right != 0) {
            stack.push_back(tree[current].right);
        }
        recycled.push_back(current);
    }
}

// 按 key 切分：左树中的 key < key，右树中的 key >= key。
void split_tree(int current, ll key, int &left_tree, int &right_tree) {
    if (current == 0) {
        left_tree = right_tree = 0;
        return;
    }
    if (tree[current].key < key) {
        left_tree = current;
        split_tree(tree[current].right, key, tree[current].right, right_tree);
        pull(current);
    } else {
        right_tree = current;
        split_tree(tree[current].left, key, left_tree, tree[current].left);
        pull(current);
    }
}

bool contains_key(int current, ll key) {
    while (current != 0) {
        if (tree[current].key == key) {
            return true;
        }
        if (key < tree[current].key) {
            current = tree[current].left;
        } else {
            current = tree[current].right;
        }
    }
    return false;
}

int insert_node(int current, int node) {
    if (current == 0) {
        return node;
    }
    if (tree[node].priority > tree[current].priority) {
        split_tree(current, tree[node].key, tree[node].left, tree[node].right);
        pull(node);
        return node;
    }
    if (tree[node].key < tree[current].key) {
        tree[current].left = insert_node(tree[current].left, node);
    } else {
        tree[current].right = insert_node(tree[current].right, node);
    }
    pull(current);
    return current;
}

void insert_key(ll key) {
    if (contains_key(root, key)) {
        return;
    }
    root = insert_node(root, new_node(key));
}

void collect_values(int current, ll add, vector<ll> &values) {
    vector<int> stack;
    int p = current;
    while (p != 0 || !stack.empty()) {
        while (p != 0) {
            stack.push_back(p);
            p = tree[p].left;
        }
        p = stack.back();
        stack.pop_back();
        values.push_back(tree[p].key + add);
        p = tree[p].right;
    }
}

int build_from_sorted(const vector<ll> &values) {
    if (values.empty()) {
        return 0;
    }
    vector<int> stack;
    for (ll value : values) {
        int current = new_node(value);
        int last = 0;
        while (!stack.empty()
               && tree[stack.back()].priority < tree[current].priority) {
            last = stack.back();
            stack.pop_back();
        }
        tree[current].left = last;
        if (!stack.empty()) {
            tree[stack.back()].right = current;
        }
        stack.push_back(current);
    }
    int new_root = stack.front();
    vector<int> order;
    order.push_back(new_root);
    for (size_t i = 0; i < order.size(); i++) {
        int current = order[i];
        if (tree[current].left != 0) {
            order.push_back(tree[current].left);
        }
        if (tree[current].right != 0) {
            order.push_back(tree[current].right);
        }
    }
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        pull(order[i]);
    }
    return new_root;
}

void apply_ordinary(int a, int b) {
    int old_low = low_mask;
    low_mask = 0;
    vector<int> high_outputs;
    for (int value = 1; value < 20; value++) {
        if ((old_low & (1 << value)) == 0) {
            continue;
        }
        int output = value;
        if (value >= a) {
            output = value - a + b;
        }
        if (output < 20) {
            low_mask |= 1 << output;
        } else {
            high_outputs.push_back(output);
        }
    }

    global_add += (ll)b - a;
    int fallen = 0;
    split_tree(root, 20 - global_add, fallen, root);
    vector<ll> fallen_values;
    collect_values(fallen, global_add, fallen_values);
    for (ll value : fallen_values) {
        if (value >= 0 && value < 20) {
            low_mask |= 1 << (int)value;
        }
    }
    release_tree(fallen);

    for (int output : high_outputs) {
        insert_key((ll)output - global_add);
    }
}

void apply_special(int a, int b, int c) {
    ll delta_b = (ll)b - a;
    ll delta_c = (ll)c - a;
    vector<ll> high_values;
    collect_values(root, global_add, high_values);

    // 三个有序序列分别对应“不使用、使用并得到 b、使用并得到 c”。
    vector<ll> merged_high;
    size_t p0 = 0, p1 = 0, p2 = 0;
    while (p0 < high_values.size() || p1 < high_values.size()
           || p2 < high_values.size()) {
        ll next_value = LLONG_MAX;
        if (p0 < high_values.size()) {
            next_value = min(next_value, high_values[p0]);
        }
        if (p1 < high_values.size()) {
            next_value = min(next_value, high_values[p1] + delta_b);
        }
        if (p2 < high_values.size()) {
            next_value = min(next_value, high_values[p2] + delta_c);
        }
        merged_high.push_back(next_value);
        while (p0 < high_values.size() && high_values[p0] == next_value) {
            p0++;
        }
        while (p1 < high_values.size()
               && high_values[p1] + delta_b == next_value) {
            p1++;
        }
        while (p2 < high_values.size()
               && high_values[p2] + delta_c == next_value) {
            p2++;
        }
    }

    vector<ll> small_outputs;
    for (int value = 1; value < 20; value++) {
        if ((low_mask & (1 << value)) == 0) {
            continue;
        }
        small_outputs.push_back(value); // 不使用特殊机器。
        if (value >= a) {
            small_outputs.push_back(value + delta_b);
            small_outputs.push_back(value + delta_c);
        }
    }
    sort(small_outputs.begin(), small_outputs.end());
    small_outputs.erase(unique(small_outputs.begin(), small_outputs.end()),
                        small_outputs.end());

    vector<ll> all_values;
    size_t i = 0, j = 0;
    while (i < merged_high.size() || j < small_outputs.size()) {
        ll value;
        if (j == small_outputs.size()
            || (i < merged_high.size() && merged_high[i] < small_outputs[j])) {
            value = merged_high[i++];
        } else if (i == merged_high.size()
                   || small_outputs[j] < merged_high[i]) {
            value = small_outputs[j++];
        } else {
            value = merged_high[i];
            i++;
            j++;
        }
        if (all_values.empty() || all_values.back() != value) {
            all_values.push_back(value);
        }
    }

    release_tree(root);
    root = 0;
    global_add = 0;
    low_mask = 0;
    vector<ll> high_after;
    for (ll value : all_values) {
        if (value < 20) {
            low_mask |= 1 << (int)value;
        } else {
            high_after.push_back(value);
        }
    }
    root = build_from_sorted(high_after);
}

bool reachable(ll value) {
    if (value >= 0 && value < 20) {
        return (low_mask & (1 << (int)value)) != 0;
    }
    return contains_key(root, value - global_add);
}

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

    int n, x, q;
    cin >> n >> x >> q;
    tree.reserve(600000);

    // 初始状态单独放入集合；题目保证 x>=1。
    if (x < 20) {
        low_mask |= 1 << x;
    } else {
        insert_key(x);
    }

    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;
        if (type == 0) {
            int a, b;
            cin >> a >> b;
            apply_ordinary(a, b);
        } else {
            int a, b, c;
            cin >> a >> b >> c;
            apply_special(a, b, c);
        }
    }

    while (q--) {
        ll y;
        cin >> y;
        cout << (reachable(y) ? 1 : 0) << '\n';
    }
    return 0;
}

复杂度

设 $S$ 是可达钱数集合的大小，所有钱数都不超过 $x+\sum \max(b_i,c_i)$ 。普通机器总复杂度为 $O(n \log S)$ ；每台特殊机器扫描一次集合，额外为 $O(kS)$ ，其中 $k \leqslant 30$ 。空间复杂度为 $O(S)$ 。

总结

门槛上界 $20$ 是本题的核心条件：它把高状态的复杂分支压缩成统一平移，只需显式处理很小的低状态集合。特殊机器数量很小，则允许在特殊位置做集合合并。

图示解析

这张图串起本题从状态集合到查询答案的主线：

text

1
2
3
4
5
6可达钱数集合
|- 低于 20：掩码逐个处理
`- 至少 20：统一平移
   |- 普通机器：调整偏移并切出低状态
   `- 特殊机器：三路有序归并
      `- 得到最终集合并回答查询

低状态之所以可以逐个处理，是因为门槛上界只有 20。高状态共享同一个平移量，特殊机器数量很少，因此只在特殊位置扫描并合并集合。

P17415 「IXOI R3」帮助她玩游戏

题目背景

她在阴险狡诈的黑心游戏厅玩游戏。由于你非常担心她，你决定对她进行帮助。

题目描述

她去了一个黑心游戏厅，由于你的会员身份，她初始有 $x$ 个游戏币。

游戏厅里有 $n$ 台兑换机，第 $i$ 台兑换机有如下功能：投入 $a_i$ 个游戏币，它会弹出 $b_i$ 个游戏币。其中 $k$ 个兑换机有特殊功能（剩余 $n-k$ 个功能如上），对于具有特殊功能的兑换机，投入 $a_i$ 个游戏币后，既有概率弹出 $b_i$ 个游戏币又有概率弹出 $c_i$ 个游戏币。

下文把有特殊功能的兑换机称为“特殊兑换机”，其他的兑换机称为“普通兑换机”。

她依次走过第 $1\sim n$ 台兑换机，她决定使用每个兑换机不超过 $1$ 次。如果当前这一台是普通兑换机且她的游戏币有至少 $a_i$ 个，那么她一定会使用这个兑换机；如果这台是一个特殊兑换机且她的游戏币至少有 $a_i$ 个，那么她谨慎选择是否使用；对于其他情况，她一定不会使用。

你非常关心她，你对她进行了 $q$ 次询问：对于所有选择方案，是否存在一种方案使得她有概率在最后获得恰好 $y_i$ 个游戏币。

输入格式

第一行，输入三个正整数 $n,x,q$ ，表示兑换机数、初始的游戏币数和询问数。由于 $k$ 可以由下面信息得到，这里不再输入。

接下来 $n$ 行，依次输入每台兑换机的信息。对于每个兑换机：先输入 $o_i$ 表示该兑换机的类型（ $0$ 表示普通兑换机， $1$ 表示特殊兑换机）。对于普通兑换机，接下来输入 $a_i,b_i$ ；对于特殊兑换机，输入 $a_i,b_i,c_i$ （其含义见题目描述）。

接下来 $q$ 行，每行一个正整数 $y_i$ ，表示询问参数。

输出格式

输出 $q$ 行，按顺序每行回答一个询问。如果存在方案输出 $1$ ，否则输出 $0$ 。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

样例解释

对于该样例 $k=2$ 。

初始时，她有 $5$ 个游戏币。

经过第一个兑换机时，她有 $5$ 个游戏币。由于是普通兑换机且 $5>2$ ，所以她一定会使用，此时她有 $5-2+1=4$ 个游戏币。

经过第二、三个兑换机时，由于她只有 $4$ 个游戏币，她一定不会使用。

经过第四个兑换机时，她有 $4$ 个游戏币。由于该兑换机是特殊兑换机她可以选择是否使用。如果不使用，将维持 $4$ 个游戏币；如果使用，有可能变为 $4-1+2=5,4-1+3=6$ 个游戏币。

因此最后她有可能获得 $4,5,6$ 个游戏币，所以 $2,3,4$ 询问的答案是 $1$ ，其他询问答案答案是 $0$ 。

数据范围

本题采用捆绑测试。

子任务 $0$ （ $5$ 分）： $n\le 10$ ；
子任务 $1$ （ $1$ 分）： $k=0$ ；
子任务 $2$ （ $15$ 分）： $k\le 4$ ；
子任务 $3$ （ $20$ 分）： $n\le 100$ ；
子任务 $4$ （ $10$ 分）： $a_i=b_i$ ；
子任务 $5$ （ $4$ 分）： $n\le 2\times 10^4$ ；
子任务 $6$ （ $5$ 分）： $a_i=1$ ；
子任务 $7$ （ $40$ 分）：无特殊限制；

对于 $100\%$ 的数据， $1\le n,q\le 2.5\times 10^5$ ， $0\le k\le \min(n,30)$ ， $0\le o_i\le 1$ ， $1 \le a_i\le 20$ ， $1\le x,b_i,c_i,\sum\limits_{i=1}^{n} b_i,\sum\limits_{i=1}^{n} c_i\le 2.5\times 10^5$ ， $1\le y_i\le 10^{18}$ （上述 $c_i,\sum\limits_{i=1}^{n} c_i$ 可以理解为忽略 $o_i=0$ 的 $i$ 后的结果）。

「IXOI R3」帮助她玩游戏

目录

形式化题目

解法路线

暴力解法

思路

代码

复杂度与瓶颈

子任务解法：n⩽10n \leqslant 10n⩽10 或 k⩽4k \leqslant 4k⩽4

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察

思路

代码

复杂度

总结

图示解析

子任务解法： $n \leqslant 10$ 或 $k \leqslant 4$