Target Practice

· · 题解

题意：数轴上有 t 个目标（位置两两不同），你现在在 0 处。给定长度为 c 的命令串（包含 L，R，F 三种字母），你需要按照命令串依次执行命令：L 表示向左走一步，R 表示向右走一步，F 表示在当前位置开火，如果该位置有未被击中过的目标则其被击中。你有一次修改的机会（可以不用），使命令串的一个字符改变。问最多能击中多少个目标。

注意到一次修改之后，操作位置后面的整个串的行为发生的位置都会偏移相同的长度。（比如：RRLFFRF 将 L 改成 R 后，后面的每一次操作发生的位置都会 +2。）那么我们可以先预处理出没有修改时的每个动作的位置在哪里。对于每个位置，记录它被打了多少次，以及记录初始时的答案。

然后我们可以枚举偏移的长度（-1，1，-2，2 四种），然后在命令串中从右往左进行扫描线。涉及的操作有：撤销一次开火、进行一次开火，询问当前有多少个目标被击中。直接维护即可。具体的细节可以看代码。

时间复杂度 \mathcal{O}(c)。

#include <bits/stdc++.h>
using namespace std;
int max(int x, int y) { return (x > y ? x : y); }

int T, c, buc[200015], cnt, pos[100015];
bool vis[200015];
char s[100015];

void init() {
    memset(buc, 0, sizeof buc);
    int now = c + 10; cnt = 0;
    for (int i = 1; i <= c; i++) {
        if (s[i] == 'L') now--;
        if (s[i] == 'R') now++;
        if (s[i] == 'F') {
            if (vis[now]) {
                if (!buc[now]) cnt++;
                buc[now]++;
            }
        }
        pos[i] = now;
    }
}

int work1() { // 0
    init(); return cnt;
}

int work2() { // 2
    init(); int ans = 0;
    for (int i = c; i; i--) {
        if (s[i] == 'F') {
            buc[pos[i]]--;
            if (!buc[pos[i]]) cnt--;
            if (vis[pos[i] + 2]) {
                if (!buc[pos[i] + 2]) cnt++;
                buc[pos[i] + 2]++;
            }
        }
        if (s[i] == 'L') ans = max(ans, cnt);
    }
    return ans;
}

int work3() { // -2
    init(); int ans = 0;
    for (int i = c; i; i--) {
        if (s[i] == 'F') {
            buc[pos[i]]--;
            if (!buc[pos[i]]) cnt--;
            if (vis[pos[i] - 2]) {
                if (!buc[pos[i] - 2]) cnt++;
                buc[pos[i] - 2]++;
            }
        }
        if (s[i] == 'R') ans = max(ans, cnt);
    }
    return ans;
}

int work4() { // 1
    init(); int ans = 0;
    for (int i = c; i; i--) {
        if (s[i] == 'L') {
            if (vis[pos[i] + 1]) {
                if (!buc[pos[i] + 1]) cnt++;
                buc[pos[i] + 1]++;
            }
            ans = max(ans, cnt);
            if (vis[pos[i] + 1]) {
                buc[pos[i] + 1]--;
                if (!buc[pos[i] + 1]) cnt--;
            }
        }
        if (s[i] == 'F') {
            buc[pos[i]]--;
            if (!buc[pos[i]]) cnt--;
            ans = max(ans, cnt);
            if (vis[pos[i] + 1]) {
                if (!buc[pos[i] + 1]) cnt++;
                buc[pos[i] + 1]++;
            }
        }
    }
    return ans;
}

int work5() { // -1
    init(); int ans = 0;
    for (int i = c; i; i--) {
        if (s[i] == 'R') {
            if (vis[pos[i] - 1]) {
                if (!buc[pos[i] - 1]) cnt++;
                buc[pos[i] - 1]++;
            }
            ans = max(ans, cnt);
            if (vis[pos[i] - 1]) {
                buc[pos[i] - 1]--;
                if (!buc[pos[i] - 1]) cnt--;
            }
        }
        if (s[i] == 'F') {
            buc[pos[i]]--;
            if (!buc[pos[i]]) cnt--;
            ans = max(ans, cnt);
            if (vis[pos[i] - 1]) {
                if (!buc[pos[i] - 1]) cnt++;
                buc[pos[i] - 1]++;
            }
        }
    }
    return ans;
}

int main() {
    scanf("%d %d", &T, &c);
    for (int i = 1, x; i <= T; i++) {
        scanf("%d", &x); vis[x + c + 10] = 1;
    }
    scanf("%s", s + 1);
//  printf("%d %d %d %d %d\n", work1(), work2(), work3(), work4(), work5());
    printf("%d\n", max({work1(), work2(), work3(), work4(), work5()}));
}