P10132 Cannonball B 题解

T_TLucas_Yin · 2024-02-05 14:56:00 · 题解

让 Bessie 停下来有以下几种方式：

• 她跳出了数轴范围。出去就别回来了。
• 她击碎了所有的目标，再跳也肯定无法击碎更多目标了。
• 她以同样的方向和能量第二次来到了一个位置，那么接下来的路就和第一次一样了，不会击碎其他目标了。

Bessie 停下来时击碎的目标数就是答案。我们记录一下目标格的数量，然后依题意模拟 Bessie 的跳跃即可。每一次跳跃都要记录状态（位置，方向和能量）。注意把打过的目标标记一下，否则下次以足够的能量跳到这里时还会判定为再打一下。

#include<bits/stdc++.h>
using namespace std;
int n,m,s,a[1000005],x[1000005],f[1000005];
map<pair<int,pair<int,int> >,bool> flag;
int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>x[i];
        if(a[i]==1) m++;
    }
    int p=1,v=1,i=s,sum=0;
    while(1){
        if(sum==m) break;
        if(flag.count({i,{p,v}})) break;
        if(i<1||i>n) break;//终止条件
        flag[{i,{p,v}}]=1;
        if(a[i]==0) p^=1,v+=x[i];
        if(a[i]==1) if(v>=x[i]&&!f[i]) sum++,f[i]=1;//互动判定
        if(p==1) i+=v;
        else i-=v;//移动
    }
    cout<<sum;
    return 0;
}