自动搬运

查看原文

来自洛谷，原作者为

	Genius_Star 跟你爆了

搬运于2025-08-24 22:55:00，当前版本为作者最后更新于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;
}