[USACO23DEC] Target Practice S 题解

AisDaeun 34 2024-02-04

[USACO23DEC] Target Practice S 题解

洛谷链接

注意到修改任意位的操作之后,对当前位之前的得分无影响,对当前位之后的操作的影响是整体左移或右移。我们用一个桶来保存当前坐标是否有气球,方便计算偏移量。

首先从前往后预处理出到每一位的得分和坐标(即从坐标零点开始的偏移量)。之后从后往前枚举,枚举过程中维护当前位往后偏移(-2/-1/+1/+2)的得分,当前坐标之前的得分和当前坐标之后的得分以及当前坐标的得分合并之后就是一种可能的答案。枚举所有答案之后求最大值即可。

如果你不理解怎么维护当前位往后偏移得分的:对于每一位,只有当前位是“发射”才可能得分。我们已经预处理出到每一位的坐标,如果当前坐标偏移后的坐标没有被打过就加一分。维护四种偏移的得分即可。

这就涉及到本题的一个难点:判重。很多题解中使用了set/map等容器,可能会简单一些。我使用的是桶标记当前坐标状态。

考虑维护五个桶:一个是从前往后枚举的桶,记录从前往后有哪些坐标被射击过;四个偏移量的桶,记录从后往前有哪些坐标被打过。

下面开始分类讨论将当前位更改之后的答案情况。

  1. 如果当前位是"L",更改到"R":之后所有位向右偏移两个单位,当前位无得分,答案即为当前位之前的得分+当前位之后向右偏移两个单位的得分。
  2. 如果当前位是"L",更改到"F":之后所有位向右偏移一个单位,当前位如果有得分,当且仅当当前位之后该坐标没被射击过,且当前位之后该坐标没被射击过。答案即为当前位之前的得分+当前位可能的得分+当前位之后向右偏移一个单位的得分。
  3. 如果当前位是"R",更改到"L":之后所有位向左偏移两个单位,当前位无得分,答案即为当前位之前的得分+当前位之后向左偏移两个单位的得分。
  4. 如果当前位是"R",更改到"F":之后所有位向左偏移一个单位,当前位如果有得分,当且仅当当前位之后该坐标没被射击过,且当前位之后该坐标没被射击过。答案即为当前位之前的得分+当前位可能的得分+当前位之后向左偏移一个单位的得分。
  5. 如果当前位是"F",更改到"L":之后所有位向左偏移一个单位,当前位无得分,答案即为当前位之前的得分+当前位之后向左偏移一个单位的得分。
  6. 如果当前位是"F",更改到"R":之后所有位向右偏移一个单位,当前位无得分,答案即为当前位之前的得分+当前位之后向右偏移一个单位的得分。

下面考虑如何维护重复情况:我们需要记录一个坐标第一次被打的回合,如果当前位被打了,

下面再来考虑如何维护当前位之后的得分。如果当前位是“发射”,并且当前位发射的坐标是第一个被击中,而且当前位之后打过这个坐标,那么之后偏移量的得分可以加一。

代码如下:

#include <cstdio>
char opt[100010];
int shift[5], get[100010], pos[100010], k, n;
int exist[5][200010], first[200010], ans;
void update(int x) {
  if (x <= ans) return;
  ans = x;
}
int main() {
  freopen("balloon.in", "r", stdin);
  freopen("balloon.out", "w", stdout);
  scanf("%d%d", &k, &n);
  for (int i = 1, x; i <= k; i++) {
    scanf("%d", &x);
    for (int j = 0; j < 5; j++) exist[j][x + 100000] = 1;
  }
  scanf("%s", opt + 1);
  for (int i = 1, j = 100000; i <= n + 1; i++) {
    get[i] = get[i - 1], pos[i] = j;
    if (opt[i] == 'L')
      j--;
    else if (opt[i] == 'R')
      j++;
    else if (opt[i] == 'F' && exist[0][j] == 1)
      get[i]++, exist[0][j] = -1, first[j] = i;
  }
  ans = get[n];
  for (int i = n; i >= 1; i--) {
    int now = pos[i + 1];
    if (opt[i] == 'F') {
      if (exist[0][now] == -1 && first[now] == i) {
        exist[0][now] = 1;
        for (int j = 1; j < 5; j++)
          if (exist[j][now] == -1) shift[j]++;
      }
    }
    if (opt[i] == 'L') {
      update(get[i - 1] + shift[4]);
      update(get[i - 1] + (exist[3][pos[i]] == 1 && exist[0][pos[i]] == 1) +
             shift[3]);
    } else if (opt[i] == 'R') {
      update(get[i - 1] + shift[1]);
      update(get[i - 1] + (exist[2][pos[i]] == 1 && exist[0][pos[i]] == 1) +
             shift[2]);
    } else if (opt[i] == 'F') {
      update(get[i - 1] + shift[2]);
      update(get[i - 1] + shift[3]);
    }
    if (opt[i] == 'F') {
      if (exist[1][now - 2] == 1) {
        exist[1][now - 2] = -1;
        if (exist[0][now - 2] == 1) shift[1]++;
      }
      if (exist[2][now - 1] == 1) {
        exist[2][now - 1] = -1;
        if (exist[0][now - 1] == 1) shift[2]++;
      }
      if (exist[3][now + 1] == 1) {
        exist[3][now + 1] = -1;
        if (exist[0][now + 1] == 1) shift[3]++;
      }
      if (exist[4][now + 2] == 1) {
        exist[4][now + 2] = -1;
        if (exist[0][now + 2] == 1) shift[4]++;
      }
    }
  }
  printf("%d\n", ans);
}