Cannonball

题意

Bessie 在长度为 $N$ 的数轴上弹跳，初始位置为 $S$ ，初始能量为 $1$ ，初始方向向右。

如果当前能量为 $k$ ，下一次会沿当前方向跳 $k$ 格。

每个位置有两类物体：

跳板 $q=0$ ：改变方向，并让能量增加 $v$ 。
目标 $q=1$ ：如果当前能量至少为 $v$ ，这个目标会被击破；同一个目标只计一次。

问 Bessie 无限弹跳直到离开数轴的过程中，最多会击破多少个目标。

思路

先看一个带状态去重的小数据模拟：

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/**
 * 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 16:07
 * update_at: 2026-07-11 16:08
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, start_pos;
int q_type[MAXN];
int value_arr[MAXN];
bool broken[MAXN];
set<tuple<long long, int, long long> > seen_state;

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

    cin >> n >> start_pos;
    for (int i = 1; i <= n; i++) {
        cin >> q_type[i] >> value_arr[i];
    }

    long long pos = start_pos;
    long long power = 1;
    int dir = 1;
    int ans = 0;

    // 小数据暴力：不断模拟，遇到完全相同的状态就说明之后会循环。
    while (1 <= pos && pos <= n) {
        tuple<long long, int, long long> state = make_tuple(pos, dir, power);
        if (seen_state.count(state)) break;
        seen_state.insert(state);

        int x = (int)pos;
        if (q_type[x] == 1) {
            if (!broken[x] && power >= value_arr[x]) {
                broken[x] = true;
                ans++;
            }
        } else {
            dir = -dir;
            power += value_arr[x];
        }

        pos += dir * power;
    }

    cout << ans << '\n';

    return 0;
}

暴力记录 (位置, 方向, 能量)。如果同一个状态再次出现，之后的运动轨迹会完全重复，而且目标是否被击破不会影响移动方式，因此可以停止。

满分做法仍然是模拟。每次落到一个位置：

如果是目标，且能量足够，并且之前没有击破过，就把答案加一。
如果是跳板，就反转方向，并增加能量。
按当前方向和能量跳到下一个位置。

问题在于：如果有值为 0 的跳板，Bessie 可能陷入循环，永远不离开数轴。

官方解析的处理方式是：模拟足够多步。原因可以这样理解：

如果跳板增加能量为正，能量会变大，跳跃距离增大，不可能在很小的区域里长期拖延。
如果陷入由 0 跳板造成的循环，运动轨迹会重复，此后不会再击破新的目标。
因此跑一个足够大的步数上限后，答案已经稳定。

代码使用官方实现中的 5000000 作为步数上限。对于 $N \leqslant 10^5$ 的数据规模，这个上限足够覆盖不会陷入循环时的有效弹跳过程。

代码

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/**
 * 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 16:07
 * update_at: 2026-07-11 16:08
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAX_STEP = 5000000;

int n, start_pos;
int q_type[MAXN];      // 0 表示跳板，1 表示炮击目标
int value_arr[MAXN];   // 跳板增加能量，目标表示击破所需能量
bool broken[MAXN];     // 目标是否已经被击破

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

    cin >> n >> start_pos;
    for (int i = 1; i <= n; i++) {
        cin >> q_type[i] >> value_arr[i];
    }

    long long pos = start_pos;
    long long power = 1;
    int dir = 1;
    int ans = 0;

    for (int step = 0; step < MAX_STEP && 1 <= pos && pos <= n; step++) {
        int x = (int)pos;

        if (q_type[x] == 1) {
            if (!broken[x] && power >= value_arr[x]) {
                broken[x] = true;
                ans++;
            }
        } else {
            dir = -dir;
            power += value_arr[x];
        }

        pos += dir * power;
    }

    cout << ans << '\n';

    return 0;
}

复杂度

设模拟步数上限为 $MAX_STEP = 5000000$ 。

时间复杂度为 $O(\text{MAX_STEP})$ ，空间复杂度为 $O(N)$ 。

总结

本题是状态模拟题，关键是把“落地后先处理当前位置，再跳到下一位置”的顺序写对。

目标被击破后仍然可以继续作为普通位置经过，所以需要 broken[] 防止重复计数，但不能改变运动规则。

目录

题意

思路

代码

复杂度

总结