【题解】P10132 [USACO24JAN] Cannonball B

· · 题解

题意简述

Bessie 已经精通了变成炮弹并沿着长度为 N 的数轴弹跳的艺术，数轴上的位置从左到右编号为 1,2,⋯,N。她从某个整数位置 S 开始，以 1 的初始能量向右弹跳。如果 Bessie 的能量为 k，则她将弹跳至距当前位置向前距离 k 处进行下一次弹跳。

数轴上从 1 到 N 的整数位置均有炮击目标或跳板。如果 Bessie 弹跳无限长的时间或直到她离开数轴，她会击破几个炮击目标？

解题思路

看懂题意后，很容易便能想到这是一道模拟题。于是便有了思路，我们可以直接模拟 Bessie 的弹跳过程。

跳的过程中，我们需要判断她是否越界，若越界了，就要退出循环。

注意还有重要的一点：需要判断她是否在数轴上无限跳跃。若她数轴上无限弹跳，则需要立即停止循环，否则程序将进入死循环，你将可能会有五个测试点运行超时。那么如何判断她是否在数轴上无限弹跳呢？其实很简单，我们可以每次到达一个未来过的炮击目标上时，记录当前的运动方向和能量。当到达一个来过的炮击目标时，则检查当前的运动方向和能量是否与记录的一致，若一致，则他在数轴上无限弹跳，需要立即退出循环。

代码展示

#include<bits/stdc++.h>
using namespace std;
inline int read(){//当然，数据范围这么小，也没必要使用快读
    int k=0;
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))k=k*10+(c^'0'),c=getchar();
    return k;
}const int N=1e5+2;
int n=read(),pos=read(),val=1,v[N],va[N],cnt;//N,当前坐标，当前能量，记录的能量，击破的目标数
bool jp[N],mp[N],di,d[N];//方向:F为right,T为left,判断此处是否来过，当前方向，记录的方向
int main(){
    for(int i=1;i<=n;i++)jp[i]=getchar()^'0',v[i]=read();//此处getchar()^'0'等同于getchar()-'0'
    while(pos>0&&pos<=n){//判断她是否越界 
        if(jp[pos]){//当此处有炮击目标时
            if(!mp[pos]&&val>=v[pos])mp[pos]=true,va[pos]=val,d[pos]=di,cnt++;
            else if(va[pos]==val&&d[pos]==di)break;//判断她是否在无限弹跳
        }else di=!di,val+=v[pos];//当此处有跳板时
        di?pos-=val:pos+=val;//处理此时的位置
    }printf("%d",cnt);//完美地输出答案
return 0;
}