P9979 [USACO23DEC] Target Practice S 题解

· · 题解

场上做法。

考虑枚举每一个位置变成哪种指令，然后我们只需要处理每个操作前面的指令带来的射击点和后面的操作带来的射击点。

具体来说，我们将所有位置分成大小为 B 的块，然后对于每一块，用 bitset b_i 记录一下前 Bi 次指令带来的所有射击点和在第 i 次指令时牛的位置 p_i。

接下来我们从后往前枚举改变指令的位置 i。我们维护一个后继射击点集 c，然后依托 i 所在的块求出 i 的前缀射击点集 d。那么答案就是 d 或上位移 p_i+\Delta 后的 c 并上 a 之后 1 的个数，\Delta 的值视情况而定。

时间复杂度 O(\frac{n^2}{w}+nB)，空间复杂度 O(\frac{n^2}{Bw})。

按理来说其实也跑不了多久，但是 USACO 评测机太慢了，遥遥落后。于是我们以 20\% 的概率考虑某一次改变，80\% 的概率不考虑。由于是 IOI 赛制，所以多交几次就过了。

在洛谷提交的话可以将考虑一次改变的概率提升到 50\%。

#include<bits/stdc++.h>
using namespace std;
const int o=1e5+5,B=300,k=5;
int n,m,ans,p[o];
char s[o];
bitset<o*2>a,b[o/B+5],c,d,e,f;
vector<int>v;
void work(){
    int sum=0;f=a;
    for(int i=1,x=o;i<=m;i++){
        if(s[i]=='L')x--;
        if(s[i]=='R')x++;
        if(s[i]=='F'&&f[x])sum++,f[x]=0;
    }
    ans=max(ans,sum);
}
int main(){
    srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,x;i<=n;i++)cin>>x,a[o+x]=1;
    cin>>(s+1);p[0]=o;work();
    for(int i=1,x=o;i<=m;i++){
        if(s[i]=='L')x--;
        if(s[i]=='R')x++;
        if(s[i]=='F')v.push_back(x);
        p[i]=x;
        if(i%B==0){
            b[i/B]=b[i/B-1];
            for(auto j:v)b[i/B][j]=1;
            v.clear();
        }
    }
    for(int i=m,v;i;i--){
        d=b[(i-1)/B];
        for(int j=(i-1)/B*B+1;j<i;j++)
            if(s[j]=='F')d[p[j]]=1;
        if(s[i]!='L'&&(n<=1000||rand()%k==0)){
            e=c;
            if(o<=p[i-1]-1)e<<=p[i-1]-1-o,e|=d,e&=a;
            else e>>=o-p[i-1]+1,e|=d,e&=a;
            ans=max(ans,v=e.count());
        }
        if(s[i]!='R'&&(n<=1000||rand()%k==0)){
            e=c;
            if(o<=p[i-1]+1)e<<=p[i-1]+1-o,e|=d,e&=a;
            else e>>=o-p[i-1]-1,e|=d,e&=a;
            ans=max(ans,v=e.count());
        }
        if(s[i]!='F'&&(n<=1000||rand()%k==0)){
            e=c;e[o]=1;
            if(o<=p[i-1])e<<=p[i-1]-o,e|=d,e&=a;
            else e>>=o-p[i-1],e|=d,e&=a;
            ans=max(ans,v=e.count());
        }
        if(s[i]=='L')c>>=1;
        if(s[i]=='R')c<<=1;
        if(s[i]=='F')c[o]=1;
    }
    cout<<ans<<'\n';
    return 0;
}