[IOI2016]shortcut 题解

洛谷地址//UOJ地址

题意描述

在一个 \(n\) 个点的链上,每个点下面挂了一条长度为 \(d_i\) 的边
现在可以添加一条边连接两个链上的点,这条边长度为 \(c\),现在要使直径最小

题解

\(IOI\) 题目被 \(wc\) 老师五分钟带过……
首先求出每个点到第一个点的距离,设其为 \(L\),那么每两点间的最短路就是 \(L_j-L_i+d_i+d_j\)
若在 \(a,b\) 两点间添加一条边,那么 \(i,j\) 间的距离就变成 \(|L_i-L_a|+|L_j-L_b|+d_i+d_j\)
那么这个时候我们想找到 \(min(式1,式2)\) 的最大值
这个时候想到了二分一个 \(M\),然后去验证这个 \(M\)是否可行
对于加边前,两点距离就已经小于等于 \(M\) 的,我们就没必要管他,重点是 \(L_j-L_i+d_i+d_j>M\) 的
然后我们看一下式二,既然式一不能满足限制,那么式二肯定要满足限制,也就是 \(|L_i-L_a|+|L_j-L_b|+d_i+d_j \leq M\)
然后就考虑爆拆绝对值,分别求最小值再求交
然后老师就默认大家都会,没有讲了[IOI2016]shortcut 题解
其实呢,老师的意思是,把绝对值爆拆之后,把含 \(a,b\) 的项移到右边去,构成约束,找到最紧的约束,这样就可以判
于是我们来拆开这个式子看一下(分类中的小于等于和大于等于就省略掉等于了)

  • \(L_j>L_b\)且\(L_i>L_a\)

\[L_i-L_a+L_j-L_b+d_i+d_j \leq M \]

\[L_i+L_j+d_i+d_j-M \leq L_a+L_b \]

  • \(L_j>L_b\)且\(L_i<L_a\)

\[L_a-L_i+L_j-L_b+d_i+d_j \leq M \]

\[L_j-L_i+d_i+d_j-M \leq L_b-L_a \]

\[L_i-L_j-d_i-d_j+M \geq L_a-L_b \]

  • \(L_j<L_b且L_i>L_a\)

\[L_i-L_a+L_b-L_j+d_i+d_j \leq M \]

\[L_i-L_j+d_i+d_j-M \leq L_a-L_b \]

  • \(L_j<L_b且L_i<L_a\)

\[L_a-L_i+L_b-L_j+d_i+d_j \leq M \]

\[-L_i-L_j+d_i+d_j-M \leq -L_a-L_b \]

\[L_i+L_j-d_i-d_j+M \geq L_a+L_b \]


啊,\(mk\) 排版有待提升
然后我们得到了一系列约束,这个时候我们发现很多符号不太统一,所以我们给第二、四种情况两边取负,这样的话 \(L_a\) 就一直会是正的(然后我们会从求最大值变成求最小值)
我们对于四种情况,把左式求出,考虑枚举一个 \(j\),我们可以想到用一个线段树来找到 \(L_i+d_i\) 或 \(L_i-d_i\) ,似乎需要两棵树(没试过)
这样的话时间就是 \(O(nlog_nlog_n)\),还是过不去,我们还需要更好的
原课件是证明了一个单调性之后使用双指针,但是我并没有看懂,于是在网上找到了一位大佬的代码做参考,使用单调队列
然后由于我比较菜,一眼看过去并不怀疑其正确性,所以没有研究为什么单调队列就可以了
然后我们说一下怎么判断有没有解
我们的 \(L\) 数组肯定是单调不降的,这没问题,但是细心的小伙伴可能发现,有没有可能,第一种情况下,约束是最紧的,但是我们在该约束条件下找到的\(a,b\)并不满足该约束的前提(也就是 \(L_j>L_b\)且\(L_i>L_a\) )
这是不可能的,因为如果不符合前提,那么爆拆绝对值之后的值就是负数,不是最优的
最后,枚举一个 \(a\),用两组 \(l,r\) 分别代表两组约束,然后如果 \(r1>=l1且r1>=l2\),\(r2\)同理,成立,那么就是有解了
具体细节可以看代码(这次没有放毒瘤码风了)

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll inf=((1ll<<62)-1);
ll n,m,s[10100101],d[1010001],L,R,ans,mid;

bool check(ll sam){
	ll mx1=-inf,mx2=-inf,mn1=inf,mn2=inf,Mx=-inf,mx=d[1]-s[1];
	ll qq[1001001],l1=n+1,r1=n,l2=1,r2=0,l=1,r=1;
	qq[1]=1;
	for(ll i=2;i<=n;++i){
		if(mx+s[i]+d[i]>sam){
			mn1=min(mn1,sam-d[i]+s[i]-mx-m);
			mn2=min(mn2,sam-d[i]-s[i]-mx-m);
			while(l<=r&&d[qq[l]]-s[qq[l]]+d[i]+s[i]>sam){
				Mx=max(Mx,d[qq[l]]+s[qq[l]]);
				++l;
			}
			mx1=max(mx1,-sam+d[i]+s[i]+Mx+m);
			mx2=max(mx2,-sam+d[i]-s[i]+Mx+m);
		}
		mx=max(mx,d[i]-s[i]);
		while(r>=l&&d[i]-s[i]-d[qq[r]]+s[qq[r]]>=0)--r;
		qq[++r]=i;
	}
	if(mx1>mn1||mx2>mn2)return 0;
	for(ll i=1;i<=n;++i){//寻找 a b 
		while(l1>1&&s[l1-1]+s[i]>=mx1)--l1;
		while(r1>=l1&&s[r1]+s[i]>mn1)--r1;
		while(r2<n&&s[r2+1]-s[i]<=-mx2)++r2;
		while(l2<=r2&&s[l2]-s[i]<-mn2)++l2;
		if(l1>r1||l2>r2)continue;
		if(!(l2>r1||l1>r2))return 1;
	}
	return 0;
}

int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=2;i<=n;++i)scanf("%lld",&s[i]);
	for(ll i=1;i<=n;++i)s[i]+=s[i-1];
	for(ll i=1;i<=n;++i)scanf("%lld",&d[i]);
	L=0,R=(n+1)*(1e9);
	while(L<=R){
		mid=(L+R)>>1;
		if(check(mid))ans=mid,R=mid-1;
		else L=mid+1;
	}
	cout<<ans;
}
上一篇:Ubuntu set up 8 - shortcut for enable/disable touchpad


下一篇:Qunar直击探索WWDC2018(上)