Target Practice (USACO Silver 2024 January)
总体是一个有点思考难度的模拟题。
因为最多只修改一个动作，所以从这个动作看出去，前面部分结果不变，当前动作可能改结果，而后面所有动作的结果可能改变。
主要就是要快速计算后面的动作的改变，每个的变化可能是五种之一，就是左移2、左移1、不变、右移1或右移2。
具体地，我们使用如下数据结构来记录所有的状态：
set<int> left: 已经被击中的目标位置map<int,int> right[5]: 在上述5种情况下，未来所有会被击中的目标以及分别被击中的次数，我们定义right中不包含已经在left中的目标。
left开始时是空，right的初始状态需要做预先计算，按时间顺序模拟一遍就可以预计算出来（见程序）。
然后我们再次按时间顺序进行模拟，这时我们每击中一个目标，就加入到left中，同时right中的目标被击中次数会随着时间进展逐渐减少。然后考虑每一次动作可能都是被修改的动作，我们观察，修改后的结果应该是：
left.size() + right[shift_index].size()
每个时间步骤，根据动作是L,R还是F进行分类讨论，看shift_index能取哪些值，就可以计算出修改后的结果。这样对所有时间和所有shift_index下的结果取最大值，就是最终答案。程序中newhit是跟踪如果当前动作如果从L或R改成F，是否正好击中一个尚未被击中过的目标，如果newhit为1，而且这个目标未来也不会被击中，那么在对应的情况下要加到总的分值中。
剩下的问题，就是模拟过程中怎样维护left和right：每次射击的时候，判断是否击中的新的目标，是就加入left，同时从right中将这个目标删除。
📙 Target Practice讲解幻灯片 (Target Practice slides)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, c;
char s[100005];
set<int> targets;
set<int> left; // target positions already hit
map<int,int> right[5]; // number of future hits for each target position
// 0: offset left 2, 1: left 1, 2: no change, 3: right 1, 4: right 2
int ans;
int main() {
scanf("%d %d", &t, &c);
for (int i = 0; i < t; i++) {
int p;
scanf("%d", &p);
targets.insert(p);
}
scanf("%s", s);
int p = 0; // Bessie's position
// prepare all right lists
for (int i = 0; i < c; i++) {
if (s[i] == 'L') p--;
if (s[i] == 'R') p++;
if (s[i] == 'F') {
if (targets.count(p-2)) right[0][p-2] ++;
if (targets.count(p-1)) right[1][p-1] ++;
if (targets.count(p)) right[2][p] ++;
if (targets.count(p+1)) right[3][p+1] ++;
if (targets.count(p+2)) right[4][p+2] ++;
}
}
// simulate from left to right, and calculate result if we change this move
p = 0;
ans = right[2].size(); // no change
for (int i = 0; i < c; i++) {
int res = left.size();
int newhit = left.count(p) ? 0 : targets.count(p); // new hit if this is a F
if (s[i] == 'L') {
ans = max(ans, res + (int)right[3].size() // change to F, rest move right
+ (right[3].count(p) ? 0 : newhit)); // additional hit at target p
ans = max(ans, res + (int)right[4].size()); // change to R, rest move right 2 steps
p--;
} else if (s[i] == 'R') {
ans = max(ans, res + (int)right[1].size() // change to F, rest move left
+ (right[1].count(p) ? 0 : newhit)); // additional hit at target p
ans = max(ans, res + (int)right[0].size()); // change to L, rest move left 2 steps
p++;
} else { // F
for (int j = 0; j < 5; j++) { // count down all right lists
if (right[j][p+j-2]) right[j][p+j-2]--;
if (right[j][p+j-2] == 0) right[j].erase(p+j-2);
}
ans = max(ans, res + (int)right[1].size()); // change to L, move left 1
ans = max(ans, res + (int)right[3].size()); // change to R, move right 1
if (targets.count(p) && left.count(p) == 0) { // add hit to left list and remove from right lists
left.insert(p);
for (int j = 0; j < 5; j++) right[j].erase(p);
}
}
}
printf("%d\n", ans);
return 0;
}