P10132 [USACO24JAN] Cannonball B

Genius_Star · 2024-02-05 11:25:55 · 题解

思路：

考虑暴力模拟，判环的话就是记 S_i 为第 i 个位置下一步跳到的位置的集合，如果下一步要跳到的位置为 x，若 x \in S_i，则之前进行过这样的操作，就重复了，退出即可。

时间复杂度为 O(N \log N)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=100100;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
ll n,s,p=1,t=1,ans;
struct Node{
    ll op;
    ll x,f;
}a[N];
set<ll> S[N];
int main(){
    n=read(),s=read();
    for(int i=1;i<=n;i++)
      a[i]={read(),read(),0};
    while(s>=1&&s<=n){
//      cout<<a[s].f<<'\n';
        if(!a[s].op){
            t*=(-1);
            p+=a[s].x;
        }
        else{
            if(p>=a[s].x&&!a[s].f){
//              cout<<s<<'\n';
                ans++;
                a[s].f=1;
            }
        }
        if(S[s].count(s+p*t))
          break;
        S[s].insert(s+p*t);
        s+=p*t;
    }
    write(ans);
    return 0;
}