题解：P5957 [POI 2017] Flappy Bird

chase_the_light · 2026-06-11 15:44:36 · 题解

非常地朴素。

首先考虑我们从上一个点跳到现在这个点需要点击的次数，记为 need，当前的位置为 (nowx,nowy)，需要跳到的位置显然应该是 (x,a + 1)，假设我们这段时间一直都不点，那么我们就会坠落到 (nowx,nowy -x + nowx)，这时我们每把一个时间点由不点击改为点击就会上升 2 格，那么所需要的时间就是 \displaystyle \frac{a + 1 - nowy + x - nowx}{2}，然后向上取整即可。

考虑记录我们前面剩下来的能用的时间为 up，如果 need > up + x - nowx，那么我们的时间不够用。如果跳完之后反而高于上界，即如果 nowy - x + nowx + need \times 2 \ge b，是不可行的。

判断完无解之后更新 up，我们要注意，有可能不是所有的剩下的时间都是能给后面用的，如果跳得太多了跳过了 b 也是不行的，因此我们应该这样更新，

up=min(t-need,up+(b-nowy-1)>>1);

接下来就很好写了。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+5;
int n,ans,X,up,nowx,nowy;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>X;
    for(int i=1,x,a,b;i<=n;i++){
        cin>>x>>a>>b;
        nowy-=(x-nowx);
        int need=(a-nowy+2)>>1,t=x-nowx+up;
        need=max(need,0);
        if(nowy+(need<<1)>=b||t<need){
            cout<<"NIE";
            return 0;
        }
        nowy+=(need<<1);
        up=min(t-need,up+(b-nowy-1)>>1);nowx=x;
        ans+=need;
    }
    cout<<ans;
    return 0;
}