Strange Dino Game 题解

· · 题解

首先可以二分答案，这样就只要判定能否避开所有障碍。

dino 每次跳跃一定至少跨过一个仙人掌，否则可以不跳。仙人掌把整个数轴分成若干段，考虑从右往左 dp，dp[i] 表示若 dino 从第 i 段左端点出发，能使 dino 避开后面所有障碍的最靠右的起跳点。

考虑如何转移。所有障碍都对 dino 的起跳点作出了限制，即对于每个障碍，dino 不能在某一个或两个闭区间内起跳。取这些区间并集的补集就得到 dino 可以起跳的区间集合。从右往左枚举每一个可起跳的开区间 (l,r)，(l,r) 和 (l+2d,r+2d) 分别属于同一个被仙人掌划分成的段内，设这两段编号分别为 i,j (i<j)。若 j 是最后一段（即后面没有仙人掌），则 dp[i] \gets \max(dp[i],r)；否则若 l+2d < dp[j]，则 dp[i] \gets \max(dp[i],\min(r,dp[j]-2d))。最后看 dp[1] 是否 > 0 即可（注意由于可起跳的区间是开区间，这里的 dp 值均不能取到，因此必须 >0 才合法，同理前面 l+2d 必须小于 dp[j]）。

实现上为了避免浮点数的精度问题，可以把所有障碍物的横坐标和跳跃参数 d 乘上 h，这样限制区间和可起跳区间的端点均为整数。

设 n=b+c，根据具体实现，总时间复杂度为 O(Tn\log^2n) 或 O(Tn\log n)。

以下代码时间复杂度为 O(Tn\log^2n)。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=2e4+5;
struct B{
    ll x,l,r;
}bs[maxn];
struct C{
    ll x,h;
}tc[maxn],cs[maxn];
struct L{
    ll l,r;
}li[maxn*4],la[maxn*4];
int rc,pc,cl,ca;
ll f,h,b,c,mr[maxn];
bool cmpc(C x,C y){return x.x<y.x;}
bool cmpl(L x,L y){return x.l<y.l;}
void init(){
    rc=0;
}
void initc(ll x){
    cl=pc=ca=0;
    while(pc<rc&&cs[pc+1].x<x) pc++;
}
void qd(ll x,ll l,ll r)
{
    if(l>h) return;
    ll dr=x-l*f,dl=x+l*f-f*h*2,ur=x-r*f,ul=x+r*f-f*h*2;
    if(h<=r) li[++cl]=(L){dl,dr};
    else li[++cl]=(L){dl,ul},li[++cl]=(L){ur,dr};
}
int fd(ll x){
    int l=1,r=rc,re=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(cs[mid].x<=x) re=mid,l=mid+1;
        else r=mid-1;
    }
    return re+1;
}
bool ck(ll x)
{
    initc(x);
    for (int i=1;i<=pc;i++) qd(cs[i].x,0,cs[i].h),mr[i]=-1;
    for (int i=1;i<=b;i++) if(bs[i].x<x) qd(bs[i].x,bs[i].l,bs[i].r);
    sort(li+1,li+cl+1,cmpl);
    ll pr=0;
    for (int i=1;i<=cl;i++)
    {
        if(li[i].l>pr) la[++ca]=(L){pr,li[i].l};
        pr=max(pr,li[i].r);
    }
    mr[pc+1]=3e18;
    for (int i=ca;i;i--)
    {
        ll px=fd(la[i].l),nx=min(pc+1,fd(la[i].l+f*h*2));
        if(px==nx) continue;
        if(nx==pc+1) mr[px]=max(mr[px],la[i].r);
        else if(la[i].l+f*h*2<mr[nx]) mr[px]=max(mr[px],min(la[i].r,mr[nx]-f*h*2));
    }
    return mr[1]>0;
}
void solve()
{
    cin>>f>>h>>b>>c;init();
    for (int i=1;i<=b;i++) cin>>bs[i].x>>bs[i].r>>bs[i].l,bs[i].x*=h;
    for (int i=1;i<=c;i++) cin>>tc[i].x>>tc[i].h,tc[i].x*=h;
    sort(tc+1,tc+c+1,cmpc);
    for (int i=1;i<=c;i++)
        if(tc[i].x!=tc[i-1].x) cs[++rc]=(C){tc[i].x,tc[i].h};
        else cs[rc].h=max(cs[rc].h,tc[i].h);
    ll l=2,r=1e9+1,re=1;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(ck(mid*h)) re=mid,l=mid+1;
        else r=mid-1;
    }
    if(re==1e9+1) cout<<"Dino!"<<endl;
    else cout<<re<<endl;
}
int main()
{
    int t;cin>>t;
    while(t--) solve();
    return 0;
}