17.[USACO10FEB]Covering the Corral G

作者：H_D_NULL

---

不是我说，还是外国的题出得简单一些

---

首先分析题面，第一眼觉得是一个贪心。然后仔细看了一下，居然是一个环！太不好贪心了。还有段与段之间还有包含关系，不能支持简单的贪心。最后总体分析了一下，得出本题最大的难点：那是什么鬼图啊？！

经过以上分析，我们不难得出本题的做法：贪心。

---

大体贪心策略： 管他是不是环，对于当前已选的，只要找到一类围栏，使其起始端点在已选围栏的包含范围之内（或刚好能接上），然后在这些围栏里，找延伸得最远的（及右端点的值越大的）。正确性不难证明，只是复杂度暂时有些问题。枚举要选的第一个围栏，然后如上述策略贪心地加围栏，直到形成一个环。

进一步优化： 策略是没得优化了，关键就看能不能用更少的时间。大多数的人的做法（特指某篇题解）是只预处理对于选了某一条边的情况，下一次贪心选的边，这样做完全没有问题，但是没有逼格 。而有些人（特指另一篇）给我们提供了更优的思路——倍增 。用类似找LCA的方法，可以快速找到从一段围栏出发，到结束所用的最少围栏数。P.S. 似乎加了倍增优化和暴力跳边实际的时间差距不大？

Talk is cheap, show me the code.

#include<bits/stdc++.h>
#define re register
#define Maxm 100005
using namespace std;

int C,M,Ans=Maxm,tot;

inline int read(){
	re int ret=0;
	re char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ret;
}

struct dr{
	int L,R;
	int Nxt[20];
} t1[Maxm],t[Maxm<<1];

inline bool cmp(dr x,dr y){
	return x.L<y.L;
}

int main(){
	C=read();
	M=read();
	for(re int i=1;i<=M;i++){
		t1[i].L=read();
		t1[i].R=t1[i].L+read();
	}
	sort(t1+1,t1+1+M,cmp);
	for(re int i=1;i<=M;i++){ //去重（目测有大用）
		if(t1[i].R>t[tot].R){
			t[++tot]=t1[i];
		}
	}
	M=tot;
	for(re int i=1;i<=M;i++){
		t[i+M].L=t[i].L+C;
		t[i+M].R=t[i].R+C;
	}
	re int tmp=1;
	for(re int i=1;i<=M<<1;i++){
		t[i].Nxt[0]=t[i-1].Nxt[0];
		for(;tmp<=M<<1&&t[tmp].L<=t[i].R;tmp++){ //贪心：找直接接在自己后面的那条围栏
			if(t[tmp].R>t[t[i].Nxt[0]].R) t[i].Nxt[0]=tmp;
		}
	}
	for(re int i=M<<1;i;i--){ //预处理倍增数组
		for(re int j=1;j<=18&&t[t[i].Nxt[j-1]].Nxt[j-1];j++){
			t[i].Nxt[j]=t[t[i].Nxt[j-1]].Nxt[j-1];
		}
	}
	for(re int i=1,sum,now;i<=M;i++){
		sum=1; now=i;
		for(re int j=18;j>=0;j--){ //倍增从大往小找
			if(t[now].Nxt[j]&&t[t[now].Nxt[j]].R-t[i].L<C){
				now=t[now].Nxt[j];
				sum+=1<<j;
			}
		}
		if(t[now].Nxt[0]&&t[now].R-t[i].L<C){
			sum++; now=t[now].Nxt[0];
		}
		if(t[now].R-t[i].L>=C) Ans=min(Ans,sum);
	}
	printf("%d",Ans);
	return 0;
}

本文作者： 益题 Yitee
发布时间： 2020-12-13
最后更新： 2021-08-19
本文标题： 17.[USACO10FEB]Covering the Corral G
本文链接： https://yitee.top/posts/20756.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

微信