Target Practice

题意

Bessie 在数轴上从 0 开始执行一串指令：

L：向左走一格；
R：向右走一格；
F：向当前位置开火，如果这里有未被打掉的目标，就打掉它。

现在允许把至多一条指令改成另外一种指令，求最多能打掉多少个不同目标。

思路

先看暴力：枚举每个位置改成另外两种指令，然后完整模拟一遍。

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

int target_count, command_count;
set<int> targets;
string cmd;

int simulate(string s) {
    int pos = 0;
    set<int> hit;

    for (int i = 0; i < command_count; i++) {
        if (s[i] == 'L') {
            pos--;
        } else if (s[i] == 'R') {
            pos++;
        } else {
            if (targets.count(pos)) {
                hit.insert(pos);
            }
        }
    }

    return (int)hit.size();
}

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

    cin >> target_count >> command_count;
    for (int i = 1; i <= target_count; i++) {
        int x;
        cin >> x;
        targets.insert(x);
    }
    cin >> cmd;

    int ans = simulate(cmd);
    char choices[3] = {'L', 'F', 'R'};

    for (int i = 0; i < command_count; i++) {
        char old = cmd[i];
        for (int j = 0; j < 3; j++) {
            if (choices[j] == old) continue;
            cmd[i] = choices[j];
            ans = max(ans, simulate(cmd));
        }
        cmd[i] = old;
    }

    cout << ans << '\n';

    return 0;
}

暴力的瓶颈是每次修改都要重新模拟，最坏是 $O(C^2)$ 。

只修改一条指令时，有一个很重要的性质：修改点之前完全不变，修改点之后的所有位置只会整体平移。

各种修改对后缀位移的影响如下：

原指令	新指令	后缀位移
`L`	`F`	`+1`
`L`	`R`	`+2`
`R`	`F`	`-1`
`R`	`L`	`-2`
`F`	`L`	`-1`
`F`	`R`	`+1`

所以后缀只需要维护五种整体位移：-2,-1,0,1,2。

从右往左枚举修改位置。当前枚举到 i 时：

prefix_hits 表示原始指令中，i 左边已经打中的目标数；
right_side[d] 表示 i 右边后缀整体位移 d 后能打中的目标集合；
pending_add[d] 暂存“后缀能打中，但当前已经被前缀打中，所以暂时不能计数”的目标。

为什么需要 pending_add？

如果一个目标已经在前缀中被打中过，后缀即使也能打中它，也不能重复计数。随着反向扫描继续向左，这个目标的首次命中会从前缀中移出去。此时它才可以加入对应位移的后缀集合。

枚举每个修改位置时，根据上表选择对应的后缀位移。如果把 $L/R$ 改成 F，还要额外判断当前位置这一枪是否能新打中一个目标。

原始不修改的答案先模拟一次得到，用它初始化最大值。

代码

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

const int MAXC = 100005;
const int MAXP = 200015;

int target_count, command_count;
int offset_pos;
string cmd;

bool is_target[MAXP];
bool hit_in_prefix[MAXP];  // 当前分割点左侧，原始指令已经打中的目标。
bool right_side[5][MAXP];  // 位移 -2..2 下，右侧后缀能打中的目标。
bool pending_add[5][MAXP]; // 被右侧后缀打中，但暂时还在左侧前缀中。
int right_count[5];
int first_hit_time[MAXC];

int move_delta(char ch) {
    if (ch == 'L') return -1;
    if (ch == 'R') return 1;
    return 0;
}

void add_right_target(int idx, int pos) {
    if (pending_add[idx][pos]) {
        pending_add[idx][pos] = false;
    }
    if (!right_side[idx][pos]) {
        right_side[idx][pos] = true;
        right_count[idx]++;
    }
}

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

    cin >> target_count >> command_count;
    offset_pos = command_count;

    for (int i = 1; i <= target_count; i++) {
        int x;
        cin >> x;
        is_target[x + offset_pos] = true;
    }
    cin >> cmd;

    for (int i = 0; i < command_count; i++) {
        first_hit_time[i] = -1;
    }

    int cur_pos = offset_pos;
    int original_hits = 0;

    // 先模拟原始指令，记录每个目标第一次被打中的时刻。
    for (int i = 0; i < command_count; i++) {
        if (cmd[i] == 'F') {
            if (is_target[cur_pos] && !hit_in_prefix[cur_pos]) {
                hit_in_prefix[cur_pos] = true;
                first_hit_time[i] = cur_pos;
                original_hits++;
            }
        }
        cur_pos += move_delta(cmd[i]);
    }

    int ans = original_hits;
    int prefix_hits = original_hits;

    // 从右往左移动修改位置。cur_pos 表示执行完 i 号指令后的原始位置。
    for (int i = command_count - 1; i >= 0; i--) {
        if (first_hit_time[i] != -1) {
            int pos = first_hit_time[i];
            hit_in_prefix[pos] = false;
            prefix_hits--;

            for (int idx = 0; idx < 5; idx++) {
                if (pending_add[idx][pos]) {
                    add_right_target(idx, pos);
                }
            }
        }

        // 回到执行 i 号指令之前的位置。
        cur_pos -= move_delta(cmd[i]);

        if (cmd[i] == 'L') {
            // L -> F：当前位置开火，后缀整体相对原来右移 1。
            int add_now = 0;
            if (is_target[cur_pos] && !hit_in_prefix[cur_pos] && !right_side[3][cur_pos]) {
                add_now = 1;
            }
            ans = max(ans, prefix_hits + add_now + right_count[3]);

            // L -> R：后缀整体相对原来右移 2。
            ans = max(ans, prefix_hits + right_count[4]);
        } else if (cmd[i] == 'R') {
            // R -> F：当前位置开火，后缀整体相对原来左移 1。
            int add_now = 0;
            if (is_target[cur_pos] && !hit_in_prefix[cur_pos] && !right_side[1][cur_pos]) {
                add_now = 1;
            }
            ans = max(ans, prefix_hits + add_now + right_count[1]);

            // R -> L：后缀整体相对原来左移 2。
            ans = max(ans, prefix_hits + right_count[0]);
        } else {
            // F -> L / F -> R：当前不再开火，只改变后缀位移。
            ans = max(ans, prefix_hits + right_count[1]);
            ans = max(ans, prefix_hits + right_count[3]);
        }

        // 原始 i 号指令加入右侧后缀，供更靠左的修改位置使用。
        if (cmd[i] == 'F') {
            for (int pos = cur_pos - 2; pos <= cur_pos + 2; pos++) {
                if (pos < 0 || pos >= MAXP) continue;
                if (!is_target[pos]) continue;

                int idx = pos - cur_pos + 2;
                if (hit_in_prefix[pos]) {
                    if (!right_side[idx][pos]) {
                        pending_add[idx][pos] = true;
                    }
                } else {
                    add_right_target(idx, pos);
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

每个指令在反向扫描中只处理常数次，后缀位移只有 5 种。

时间复杂度为 $O(T+C)$ 。

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

总结

这题的核心是抓住“修改一条指令只会让后缀整体平移”。

前缀命中和后缀命中不能重复计数，所以需要在反向扫描时维护 pending_add：目标还在前缀时先暂存，等它离开前缀后再加入后缀集合。

目录

题意

思路

代码

复杂度

总结