P10132

Hughpig · 2024-02-05 22:10:14 · 题解

于 2024/11/29 更新：更正错误之处。

考虑暴力模拟跳的过程，用 power 表示奶牛的力量，dir 表示方向，1 为向右，-1 为向左。用 broken 数组记录跳板是否损坏。

代码：

void jump(){
    if(s<1||s>n)return;
    if(type[s]==1){
        if(v[s]<=power&&(!broken[s]))broken[s]=1,ans++;
    }
    else{
        dir=-dir,power+=v[s];
    }
    s+=power*dir;
    jump();
}

但是这样有个问题，这份代码无法处理无限跳跃的情况。

我们发现 N 最大为 10^5，如果能跳出数轴的话，奶牛第一次从头跳到尾力量为 1，要 n 步；第二次力量为 2，要 \dfrac{n}{2} 步；第 3 次要 \dfrac{n}{3} 步；第 n 次要 1 步，总步数为 \displaystyle\sum_{i=1}^{x}\lfloor\dfrac{n}{i}\rfloor\approx n\ln n。所以最大大约要跳 10^5\times\ln 10^5\approx 10^6 步。

因此只要用一个变量 cnt 记录跳的次数，如果跳跃次数大于 10^6 就判定为无限，直接输出答案即可。

代码：

#include<bits/stdc++.h>
using namespace std;

int n,s,power=1,v[100007],dir=1,ans,cnt;
bool type[100007],broken[100007];

void jump(){
    if(cnt>1000000){
        cout<<ans,exit(0);
    }
    cnt++;
    if(s<1||s>n)return;
    if(type[s]==1){
        if(v[s]<=power&&(!broken[s]))broken[s]=1,ans++;
    }
    else{
        dir=-dir,power+=v[s];
    }
    s+=power*dir;
    jump();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++)cin>>type[i]>>v[i];
    jump();
    cout<<ans;
    return 0;
}