专栏文章

题解：P10438 [JOISC 2024] 塔楼 (Day3)

ccwfxlh
P10438题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipqsfnm
此快照首次捕获于
2025/12/03 16:25
3 个月前
此快照最后确认于
2025/12/03 16:25
3 个月前
查看原文

P10438

现有的两篇题解都是两 log⁡\log 的，来一个一 log⁡\log 的！(其实差不了太多)

情况一

第一个情况是 D×A≥BD\times A\ge B，也就是说要尽可能少跳。
先编一个 O(V)O(V) 的 dp。令 dpidp_i 表示到达 ii 最多跳多少次，那么转移就是 dpi=min⁡(dpi−1,dpi−D+1)dp_i=\min(dp_{i-1},dp_{i-D}+1)，dp0=0dp_0=0，不能通过的位置 dpi=inf⁡dp_i=\inf。
优化以上 dp。能通过的位置是一段一段的，先猜一下 dp 值长什么样子。
对于每一段，肯定有一段前缀的 dp 值是 inf⁡\inf。这是显然的。
继续猜，每一段不是 inf⁡\inf 的都相同，并且每一段都不小于前一段。这个结论仔细想想也是对的。
首先因为 dpidp_i 对 dpi−1dp_{i-1} 取了 min⁡\min，所以每一段肯定是不升的。递归证明。新加入一段，令这段的左端点为 ll，则 dpl=dpl−D+1dp_l=dp_{l-D}+1，第一个大于 dpldp_l 的位置为 xx，则 dpx=min⁡(dpx−1,dpx−D+1)=min⁡(dpl,dpx−D+1)<dpl=dpl−D+1dp_x=\min(dp_{x-1},dp_{x-D}+1)=\min(dp_l,dp_{x-D}+1)<dp_l=dp_{l-D}+1，推出 dpx−D<dpl−Ddp_{x-D}<dp_{l-D}，如果 x−D≥lx-D\ge l，那么肯定不成立，否则因为前面的段都满足条件，因此也不成立。
所以 dp 值的连续段有 O(n)O(n) 个，从前往后插入，然后找到第一个能转移到新段落的位置（转移的限制是距离限制状物），维护一个指针即可 O(n)O(n) 解决。

情况二

第一个情况是 D×A<BD\times A<B，也就是说要尽可能多跳。
同样的，考虑 dp，令 dpidp_i 表示到达 ii 最多跳多少次，转移是 dpi=max⁡(dpi−1,dpi−D+1)dp_i=\max(dp_{i-1},dp_{i-D}+1)，dp0=0dp_0=0，不能到达的地方 dp 值为 −inf⁡-\inf。
同样的，dp 值不为 −inf⁡-\inf 的位置是 O(n)O(n) 个段落，并且每一段不降。
显然的，现在每一段不是全相等了，因为可以对 dpi−D+1dp_{i-D}+1 取 max⁡\max，所以至少每经过 DD 个位置，dp 值会 +1。对于长度大于 DD 的段落，其形态必定如同将前 DD 个拿来一直复制，并且每往后加一段都整体将 dp 值 +1。
考虑这前 DD 个，我们猜想其涨幅不会超过 1。考虑如下更强的命题：对于任意 i,j∈[i+1,i+D],dpi≠−inf⁡,dpj≠−inf⁡i,j\in[i+1,i+D],dp_i\not=-\inf,dp_j\not=-\inf，那么都有 dpj∈[dpi,dpi+1]dp_j\in[dp_i,dp_i+1]。证明可以递归证明，在 [1,j−1][1,j-1] 都满足情况的条件下，如果 dpj=dpj−1dp_j=dp_{j-1}，那么显然满足条件，如果 dpj=dpj−D+1dp_j=dp_{j-D}+1，那么有 i∈[j−D,j−1]i\in[j-D,j-1] 也就是 i∈[(j−D),(j−D)+D−1]i\in[(j-D),(j-D)+D-1]，如果 i=j−Di=j-D，那么 dpj=dpi+1dp_j=dp_i+1，否则 dpi∈(dpj−D,dpj−D+1)dp_i\in(dp_{j-D},dp_{j-D}+1)，一样可以证明。
于是 dp 值又被刻画出来了，每一段都是不降的，且段与段之间也是不降的，每一段的 dp 值形态是长为 x≤Dx\le D 的某个值，然后每 DD 格 dp 值 +1。
维护每段端点，开头的值，开头的长度，添加一段的时候通过二分算出开头的长度，复杂度 O(nlog⁡n)O(n\log n)。
两部分结合起来算 dp，查询二分到对应的段落查询，复杂度 O(nlog⁡n+qlog⁡n)O(n\log n+q\log n)。
代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,D,A,B,lft,rgt,mid,flg;
pair<int,int>a[200003];
int k1,k2,k3,k4,k5,k6,k7,k8,k9;
struct Segmt{
	int l;
	int r;
	int stv;
	int stlen;
}P[200003];
int totP;
int getval(int num,int pos){
	if(!flg)return P[num].stv;
	if(P[num].stlen==D)return P[num].stv+((pos-P[num].l)/D);
	return P[num].stv+((pos-P[num].l+D-P[num].stlen)/D);
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>q>>D>>A>>B;
	if(A*D>B)flg=1;
	for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
	P[++totP].l=0;P[totP].r=a[1].first-1;P[totP].stv=0;P[totP].stlen=D;
	a[n+1].first=1000000000001ll;
	a[n+1].second=1000000000001ll+D-1;
	for(int i=1,j=0;i<=n;i++){
		int u=a[i].second+1,v=a[i+1].first-1;
		lft=1;rgt=totP;
		while(lft<rgt){
			mid=((lft+rgt)/2);
			if(P[mid].r+D>=u)rgt=mid;
			else lft=mid+1;
		}
		j=lft;
		if(j>totP)continue;
		if(max(P[j].l+D,u)>min(P[j].r+D,v))continue;
		P[++totP].l=max(P[j].l+D,u);P[totP].r=v;P[totP].stv=getval(j,P[totP].l-D)+1;
		if(!flg){P[totP].stlen=0;continue;}
		k1=P[totP].stv-1;
		lft=j;rgt=totP-1;
		while(lft<rgt){
			mid=((lft+rgt)/2);
			if(getval(mid,P[mid].r)>k1||getval(mid,P[mid].l)>k1)rgt=mid;
			else lft=mid+1;
		}
		if(lft>=totP||lft<j||getval(lft,P[lft].r)==k1){P[totP].stlen=D;continue;}
		int pos=0;
		if(getval(lft,P[lft].l)>k1)pos=P[lft].l;
		else pos=P[lft].l+P[lft].stlen+D*(k1-P[lft].stv);
		pos+=D;
		if(pos>=P[totP].l&&pos<=P[totP].r)P[totP].stlen=pos-P[totP].l;
		else P[totP].stlen=D;
		if(P[totP].stlen==0)P[totP].stlen=D;
	}
	while(q--){
		cin>>k1;
		lft=1;
		rgt=totP;
		while(lft<rgt){
			mid=((lft+rgt)/2)+1;
			if(P[mid].l<=k1)lft=mid;
			else rgt=mid-1;
		}
		if(P[lft].l<=k1&&P[lft].r>=k1)cout<<A*(k1-getval(lft,k1)*D)+B*getval(lft,k1)<<'\n';
		else cout<<-1<<'\n';
	}
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...