自动搬运

查看原文

来自洛谷，原作者为

	Nineyx **

搬运于2025-08-24 23:04:39，当前版本为作者最后更新于2024-08-05 04:21:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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;
}