P10132 题解

Crazyouth · 2024-02-07 19:05:49 · 题解

分析

如果某些蹦床弹力系数为 0，那么就会出现反复横跳的情况，开 map 记录一个三维状态 i,j,0/1，表示是否曾以 j 的弹力系数，朝某个方向（0 表示向左，1 表示向右）经过 i，如果有就输出答案。否则每个蹦床不会经过很多次，总共只会经过 O(n) 次，所以可以暴力。

AC Code

#include <bits/stdc++.h>
using namespace std;
map<pair<pair<int,int>,int>,int> mp;
struct loc
{
    int q,v,br;
}a[100010];
int main()
{
    int n,s,p=1,pos=1;
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].q>>a[i].v;
        a[i].br=0;
    }
    int ans=0;
    mp.clear();
    while(1<=s&&s<=n)
    {
        if(mp[{{s,p},pos}])
        {
            cout<<ans;
            return 0;
        }
        mp[{{s,p},pos}]=1;
        if(a[s].q)
        {
            if(p>=a[s].v&&!a[s].br)
            {
                a[s].br=1;
                ans++;
            }
        }
        else p+=a[s].v,pos^=1;
        s+=(pos?p:-p);
    }
    cout<<ans;
    return 0;
}