[USACO23DEC] Target Practice S

寒鸽儿 · 2023-12-25 22:31:45 · 题解

提供一种比较好写的思路：

基本思想是枚举每个位置，当前的字母枚举变成了什么字母。

对于同一种变化，那么某个位置变化后，其后面的攻击 F 发生时所在的位置的变化量是确定的。

预处理出不发生变化时每次操作操作前所处的位置。

对每种变化分别枚举所有位置。从后往前枚举，当前枚举的点之后的点都是变化后的位置。如果这个字母符合变化，则将当前的答案更新全局最优解。然后修改当前操作的位置（维护下面的枚举）：统计全局每个 target 第一个被击中的 F 发生的下标，在移动到某个位置的时候，如果原有位置是 F ，那么需要判断是不是 left，如果是，用后面的最近的相同位置的 F（如果存在）更新 target，不存在则 left 置为 0 。同时更新变到的位置的 left（如果可以）。使用一个变量全局地记录 left 中非 0 的 target 点的个数，即为当前枚举的答案。（也可以写成 cnt 数组，更好写一点）。

复杂度 \mathcal{O}(n) 。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

const int N = 1e5 + 10, DELTA = 1e5 + 1;
int pls[N], mp[N << 1], lft[N << 1], second[N << 1], LEFT[N << 1], nTar, nOp, curAns, ans;
char op[N];

void work(int delta, char from, char to) {
    memset(second, 0, sizeof(second));
    memcpy(lft, LEFT, sizeof(lft));
    per(i,nOp,1) {
        if(op[i] == from) {
            if(from == 'F' && mp[pls[i] + DELTA] && lft[pls[i] + DELTA] == i && second[pls[i] + DELTA] == 0) ans = max(ans, curAns - 1);
            else if(to == 'F' && mp[pls[i] + DELTA] && lft[pls[i] + DELTA] == 0) ans = max(ans, curAns + 1);
            else ans = max(ans, curAns);
        }
        if(op[i] == 'F') {
            if(mp[pls[i] + DELTA] && lft[pls[i] + DELTA] == i) {
                lft[pls[i] + DELTA] = second[pls[i] + DELTA];
                if(lft[pls[i] + DELTA] == 0) -- curAns;
            }
            pls[i] += delta;
            if(mp[pls[i] + DELTA]) {
                if(lft[pls[i] + DELTA] == 0) ++ curAns, lft[pls[i] + DELTA] = i;
                second[pls[i] + DELTA] = i;
                lft[pls[i] + DELTA] = min(lft[pls[i] + DELTA], i);
            }
            pls[i] -= delta;
        }

    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> nTar >> nOp;
    int tar;
    rep(i,1,nTar) {
        cin >> tar;
        mp[tar + DELTA] = 1;
    }
    cin >> (op + 1);
    int x = 0;
    rep(i,1,nOp) {
        pls[i] = x;
        if(op[i] == 'L') -- x;
        else if(op[i] == 'R') ++ x;
        else if(mp[x + DELTA] && !lft[x + DELTA]) {
            ++ ans;
            lft[x + DELTA] = i;
        }
    }
    int tmp = ans;
    memcpy(LEFT, lft, sizeof(lft));
    curAns = tmp; work(2, 'L', 'R');
    curAns = tmp; work(-2, 'R', 'L');
    curAns = tmp; work(1, 'L', 'F');
    curAns = tmp; work(-1, 'R', 'F');
    curAns = tmp; work(-1, 'F', 'L');
    curAns = tmp; work(1, 'F', 'R');
    cout << ans << endl;
    return 0;
}