P9979 [USACO23DEC] Target Practice S 题解

· · 题解

题目大意

Bessie 在一个数轴上，这个数轴上有些点上有靶子，Bessie 需要按照指定命令行动，你可以修改一条命令，求出最多可以命中多少靶子。

题目分析

思路

首先我们发现一共只能修改一条命令，我们观察对于修改后的命令哪些点会开火。

不难发现，对于修改前的命令，因为没有变，我们可以直接知道哪些点开火。对于修改后的命令，所有开火点的相对位置不会变，只会左右偏移 1\sim2 个单位长度。

于是我们可以考虑枚举修改点，然后计算其答案（也可以看成枚举修改后的命令，因为总共只有 C \times 3 + 1 种可能）。

思路有了，开始实现。

实现及细节

我们先来想对于修改点前的点，我们只需要边枚举修改点，边存就行了，在这里我开了个 set。

然后考虑修改点后的点，我们可以预处理出偏移量为 1\sim2 的开火点的集合，这里也可以开个 set。

然后问题就变成了如何计算两者之间重复的部分，我们发现我们可以将其都归在修改前算，即我们之前打过的点就不再打了，于是我们可以把打过的点在后面的 set 里删掉。

所以时间复杂度是 \mathcal O(C \log C) 的。

然后算法就口糊出来了，开始实现。

第一个细节是维护后面的 set 时不仅要把之前打过的删掉，还要把“过期”的，也就是修改点之前的部分删掉。这个也很好实现，之前怎么加进来的就怎么删。

对于这个部分，由于 set 只有有和没有的区别，不好判断出了当前点，后面还有没有开火在这个位置，比较难处理，我在这里开了个筒子记个数，判断后面还有没有。

纯开 5 个 set 然后删的话，你就会获得 70 \sim 76 pts 的好成绩（也可能是我太菜了，第一遍好多细节都没注意到）。

第二个细节，对于将 L 或 R 改成 F，当前这个点需要计入答案，这个点能被计入有两个判断条件：

  1. 当前位置有靶子。
  2. 当前位置既没有在前面算过，后面也不会打到。

然后基本上代码就完善了。

最后还有一个小细节，就是可以不对命令进行修改，这种情况记得考虑到。

code

#include <iostream>
#include <cstdio>
#include <set>
#include <map>

using namespace std;

int T, c, x, ans;
string s;
map <int, bool> mp;
map <int, int> st[7];
set <int> se[7];

int main()
{
    scanf("%d %d", &T, &c);
    for(int i = 1;i <= T;i++)
    {
        scanf("%d", &x);
        mp[x] = true;
    }
    cin >> s;
    s = "#" + s;
    int now = 0;
    for(int i = 1;i <= c;i++)
    {
        if(s[i] == 'L')
        {
            now--;
        }
        else if(s[i] == 'R')
        {
            now++;
        }
        else
        {
            if(mp[now - 2]) st[1][now - 2]++, se[1].insert(now - 2);
            if(mp[now - 1]) st[2][now - 1]++, se[2].insert(now - 1);
            if(mp[now]) st[3][now]++, se[3].insert(now);
            if(mp[now + 1]) st[4][now + 1]++, se[4].insert(now + 1);
            if(mp[now + 2]) st[5][now + 2]++, se[5].insert(now + 2);
        }
    }
    ans = max(ans, (int)(se[3].size()));
    st[3].clear(), se[3].clear();
    now = 0;
//    printf("%d\n", ans);
    for(int i = 1;i <= c;i++)
    {
        if(s[i] == 'L')
        {
            ans = max(ans, (int)(se[3].size() + max(se[4].size() + (mp[now] && se[3].count(now) == 0 && se[4].count(now) == 0), se[5].size())));
            now--;
        }
        else if(s[i] == 'R')
        {
            ans = max(ans, (int)(se[3].size() + max(se[1].size(), se[2].size() + (mp[now] && se[3].count(now) == 0 && se[2].count(now) == 0))));
            now++;
        }
        else
        {
            se[1].erase(now);
            se[2].erase(now);
            se[4].erase(now);
            se[5].erase(now);
            if(--st[1][now-2] <= 0) se[1].erase(now-2);
            if(--st[2][now-1] <= 0) se[2].erase(now-1);
            if(--st[4][now+1] <= 0) se[4].erase(now+1);
            if(--st[5][now+2] <= 0) se[5].erase(now+2);
            ans = max(ans, (int)(se[3].size() + max(se[2].size(), se[4].size())));
            if(mp[now]) st[3][now]++, se[3].insert(now);
        }
//        printf("%d\n", ans);
    }
    printf("%d", ans);
    return 0;
}

附

附带一个小小小 hack：

in:

1 1
0
F

ans:

1

再附带一个大样例

写在后面

2024-1-17：感谢 @whx1118 的hack，已更正。