Target Practice (USACO Silver 2024 January)
总体是一个有点思考难度的模拟题。
因为最多只修改一个动作，所以从这个动作看出去，前面部分结果不变，当前动作可能改结果，而后面所有动作的结果可能改变。
主要就是要快速计算后面的动作的改变，每个的变化可能是五种之一，就是左移2，左移不变，右移1和右移2。
具体实现上，需要一个“离线计算”的思想，就是要把从后往前5种情况下，所有目标位置击中次数记录下来，然后倒着模拟（逐步减少击中次数），这样当击中次数从1减至0的时候，总的分值就减少1，这样就可以把后面的部分的5种情况下的分值模拟出来。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, c;
char s[100005];
set<int> targets;
map<int,int> left;
map<int,int> right[5]; // position -> # of hits, 0: 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;
// 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] += targets.count(p-2);
if (targets.count(p-1)) right[1][p-1] += targets.count(p-1);
if (targets.count(p)) right[2][p] += targets.count(p);
if (targets.count(p+1)) right[3][p+1] += targets.count(p+1);
if (targets.count(p+2)) right[4][p+2] += targets.count(p+2);
}
}
// simulate all moves
p = 0;
for (int i = 0; i < c; i++) {
int res = left.size();
int newhit = left.count(p) ? 0 : targets.count(p); // if this is a F, does it count?
if (s[i] == 'L') {
if (right[3].count(p)) // change to F, rest move right
ans = max(ans, res + (int)right[3].size());
else
ans = max(ans, res + newhit + (int)right[3].size());
ans = max(ans, res + (int)right[4].size()); // change to R, rest move right 2 steps
p--;
} else if (s[i] == 'R') {
if (right[1].count(p)) // change to F, rest move left
ans = max(ans, res + (int)right[1].size());
else
ans = max(ans, res + newhit + (int)right[1].size());
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].count(p+j-2) && --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[p] == 0) { // add hit to left list and remove from rest lists
left[p]++;
for (int j = 0; j < 5; j++) right[j].erase(p);
}
}
}
ans = max(ans, (int)left.size()); // no change
printf("%d\n", ans);
return 0;
}