队内训练1 牛客多校第六场补题H 扫描线

题目链接link.

题意：给你一个n，给你一个d。一共有n个陷阱。一只兔子可以上下左右任意蹦跶，但是每次只能蹦跶d步。问你存不存在一个点，使得这个兔子从这里开始随意蹦跶无论怎么蹦都不会死掉。范围很大，-1e9到1e9的地

其实很容易就可以想到，这些陷阱其实都是可以平移到[0,0,d,d]的范围里的。如果超过了就%个d就好啦。最后看看[0,0,d,d]被覆盖的面积能不能达到d^2,可以达到的话就输出NO，不能达到就还得找那个空缝隙。这就不能直接抄板子了，得理解一下板子才行。

我感觉我的做法应该是比较麻烦的，最后码量也比较长。如果发现更好的做法再更新好了。下面说说我的做法。

算面积的时候，不是算∑len*（hi+1 - hi）嘛，那么当这个面积不等于零并且len<n的时候，就说明这个地方有空隙了。可以记录一个sumh。代表当前的累积到的高度，检测到这里有空隙的时候，在[sumh,sumh+1]这里一定是某个地方有空隙的。记录当前sumh为orz。代码太长了实在不知道该用啥命名了

最开始，存储覆盖的矩形的时候，可以用结构体存一下x1,x2,y1,y2。再回来遍历这些矩形，当[y1,y2]包含了之前找到的orz时，利用差分数组做一个记录，即x1++，x2–.

最后还要在计算这个差分数组的前缀和，当前缀和为0时候，就说明这个横坐标对应的是个空隙。假设这个横坐标是oxy，兔子跳不死的起点的位置就是（oxy,orz）.

比赛的时候脑子一抽想到一个傻逼的优化，结果优化假了呜呜呜没过太可惜了。我再也不瞎想了

板子是抄的洛谷的，等会儿把链接贴上，别骂我侵权啊
要赶不上ddl了.jpg

AC代码： 是时候展现一下真正的技术了，现学的.jpg

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#define lson (x << 1)
#define rson (x << 1 | 1)
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
typedef long long ll;

ll x1,y1,x2,y2;
ll n, cnt = 0;
ll X[MAXN << 1];

struct ScanLine {
	ll l, r, h;
	int mark;
//  mark用于保存权值 (1 / -1)
	bool operator < (const ScanLine &rhs) const {
		return h < rhs.h;
	}
} line[MAXN << 1];

struct SegTree {
	int l, r, sum;
	ll len;
//  sum: 被完全覆盖的次数；
//  len: 区间内被截的长度。
} tree[MAXN << 2];

void build_tree(int x, int l, int r) {
//  我觉得最不容易写错的一种建树方法
	tree[x].l = l, tree[x].r = r;
	tree[x].len = 0;
	tree[x].sum = 0;
	if(l == r)
		return;
	int mid = (l + r) >> 1;
	build_tree(lson, l, mid);
	build_tree(rson, mid + 1, r);
	return;
}

void pushup(int x) {
	int l = tree[x].l, r = tree[x].r;
	if(tree[x].sum /* 也就是说被覆盖过 */ )
		tree[x].len = X[r + 1] - X[l];
//      更新长度        
	else
		tree[x].len = tree[lson].len + tree[rson].len;
//      合并儿子信息
}

void edit_tree(int x, ll L, ll R, int c) {
	int l = tree[x].l, r = tree[x].r;
//  注意，l、r和L、R的意义完全不同
//  l、r表示这个节点管辖的下标范围
//  而L、R则表示需要修改的真实区间
	if(X[r + 1] <= L || R <= X[l])
		return;
//  这里加等号的原因：
//  假设现在考虑 [2,5], [5,8] 两条线段，要修改 [1,5] 区间的sum
//  很明显，虽然5在这个区间内，[5,8] 却并不是我们希望修改的线段
//  所以总结一下，就加上了等号
	if(L <= X[l] && X[r + 1] <= R) {
		tree[x].sum += c;
		pushup(x);
		return;
	}
	edit_tree(lson, L, R, c);
	edit_tree(rson, L, R, c);
	pushup(x);
}

ll maxx(ll oxy,ll ozl)
{
	if(oxy>ozl) return oxy;
	else return ozl;
}

ll minn(ll oxy,ll ozl)
{
	if(oxy<ozl) return oxy;
	else return ozl;
}

struct qaq
{
	ll xx1,yy1,xx2,yy2;
}oxy[MAXN];

map<ll,ll> xixi;
int nn=0;

signed main() 
{
	int d;
	scanf("%lli %lli", &n,&d);
	
	
	for(int i = 1; i <= n; i++) 
	{
		scanf("%lli %lli %lli %lli", &x1, &y1, &x2, &y2);
		int haha1=x2-x1;
		int haha2=y2-y1;
		
		x1=(x1%d+d)%d;
		y1=(y1%d+d)%d;
		x2=x1+haha1;
		y2=y1+haha2;
		
		if(x2<=d&&y2<=d)
		{
			oxy[++nn].xx1=x1;
			oxy[nn].yy1=y1;
			oxy[nn].xx2= minn(d,x2);
			oxy[nn].yy2= minn(d,y2);
		}
		else if(x2<=d&&y2>d)
		{
			oxy[++nn].xx1=x1;
			oxy[nn].xx2=x2;
			oxy[nn].yy1=y1;
			oxy[nn].yy2=d;
			
			oxy[++nn].xx1=x1;
			oxy[nn].xx2=x2;
			oxy[nn].yy1=0;
			oxy[nn].yy2=minn(d,y2-d);
		}
		else if(x2>d&&y2<=d)
		{
			oxy[++nn].xx1=x1;
			oxy[nn].xx2=d;
			oxy[nn].yy1=y1;
			oxy[nn].yy2=y2;
			
			oxy[++nn].xx1=0;
			oxy[nn].xx2=minn(d,x2-d);
			oxy[nn].yy1=y1;
			oxy[nn].yy2=y2;
		}
		else
		{
			oxy[++nn].xx1=x1;
			oxy[nn].xx2=d;
			oxy[nn].yy1=y1;
			oxy[nn].yy2=d;
			
			oxy[++nn].xx1=0;
			oxy[nn].xx2=minn(d,x2-d);
			oxy[nn].yy1=y1;
			oxy[nn].yy2=d;
			
			oxy[++nn].xx1=x1;
			oxy[nn].xx2=d;
			oxy[nn].yy1=0;
			oxy[nn].yy2=minn(d,y2-d);
			
			oxy[++nn].xx1=0;
			oxy[nn].xx2=minn(d,x2-d);
			oxy[nn].yy1=0;
			oxy[nn].yy2=minn(d,y2-d);
		}
		
	}
	n=nn;
	for(int i=1;i<=n;i++)
	{
		x1=oxy[i].xx1;
		y1=oxy[i].yy1;
		x2=oxy[i].xx2;
		y2=oxy[i].yy2;
		
		X[2 * i - 1] = x1, X[2 * i] = x2;
		line[2 * i - 1] = (ScanLine) {x1, x2, y1, 1};
		line[2 * i] = (ScanLine) {x1, x2, y2, -1};
	}
	n <<= 1;
//  直接把 n <<= 1 方便操作
	sort(line + 1, line + n + 1);
	sort(X + 1, X + n + 1);
	int tot = unique(X + 1, X + n + 1) - X - 1;
//  去重最简单的方法：使用unique！（在<algorithm>库中）
	build_tree(1, 1, tot - 1);
//  为什么是 tot - 1 ：
//  因为右端点的对应关系已经被篡改了嘛…
//  [1, tot - 1]描述的就是[X[1], X[tot]]
	ll ans = 0;
	//cout<<"n="<<n<<endl;
	ll sumh=0;
	int okk=1;
	int orz=0;
	for(int i = 1; i < n /* 最后一条边是不用管的 */ ; i++) 
	{
		edit_tree(1, line[i].l, line[i].r, line[i].mark);
//      先把扫描线信息导入线段树
		ans += tree[1].len * (line[i + 1].h - line[i].h);
//      然后统计面积 
		
		if(tree[1].len>0&&tree[1].len<d&&
		line[i+1].h-line[i].h!=0&&okk==1)
		{
			orz=sumh;
			okk=0;
		}
		
		sumh=sumh+(line[i+1].h-line[i].h);
	}
	
	//cout<<"ans="<<ans<<endl;
	
	if(ans>= d*d) 
	{
		printf("NOn");
		return 0;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(oxy[i].yy1<=orz&&oxy[i].yy2-1>=orz)
		//实际上是在区间[xx1,xx2-1]加1 
		{
			xixi[oxy[i].xx1]++;
			xixi[oxy[i].xx2]--; 
		}	
	}
	ll pre=0;
	ll orzz=0;
	for(auto i:xixi)
	{
		pre=pre+i.second;
		//cout<<i.first<<" "<<pre<<endl;
		if(pre==0)
		{
			orzz=i.first;
			break;
		}
	}
	
	printf("YESn");
	printf("%lli %llin",orzz,orz);
	return 0;
}

最后

以上就是高大舞蹈为你收集整理的队内训练1 牛客多校第六场补题H 扫描线队内训练1 牛客多校第六场补题H 扫描线的全部内容，希望文章能够帮你解决队内训练1 牛客多校第六场补题H 扫描线队内训练1 牛客多校第六场补题H 扫描线所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。