n维偏序方法记录

乎语百科 2022-10-08 21:30:17 339 0

题解

首先我们要对一个地点能否到达建立认知：一个地点能到达不仅仅是能从它的上一个点或上上个点跳到，而是能从第一个点开始跳一路跳到。就好比说，咱吃了6个包子吃饱了，但咱不能只付第6个包子的钱。

方法一：并查集

遍历整个序列，若一个点能由上一个点或上上个点跳到，则把出发点和目标点丢入同一个并查集。最后检查第一个点和最后一个点是否在同一个集合里。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int t;
int fa[N];
int h[N];
template <typename T>inline void re(T &x) {
	x=0;
	int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-f;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	x*=f;
	return;
}
template <typename T>void wr(T x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) wr(x/10);
	putchar(x%10^'0');
	return;
}
int my_abs(int a,int b)
{
	if(a>=b) return a-b;
	else return b-a;
}
int get(int x)
{
	if(fa[x]!=x) fa[x]=get(fa[x]);
	return fa[x];
}
void merge(int r1,int r2)
{
	fa[r2]=r1;
}
int main()
{
	freopen("n.in","r",stdin);
	freopen("n.out","w",stdout);
	re(t);
	while(t--)
	{
		int n,d1,d2;
		memset(h,0,sizeof(h));
		re(n);re(d1);re(d2);
		for(int i=1;i<=n;i++)
		{
			re(h[i]);
			fa[i]=i;
		}
		for(int i=1;i<=n;i++)
		{
			if(i>=2&&my_abs(h[i],h[i-1])<=d1)
			{
				int r1=get(i);
				int r2=get(i-1);
				if(r1!=r2) merge(r1,r2);
			}
			if(i>=3&&h[i-2]>h[i-1]&&h[i-1]<h[i]&&my_abs(h[i],h[i-2])<=d2)
			{
				int r1=get(i);
				int r2=get(i-2);
				if(r1!=r2) merge(r1,r2);
			}
		}
		if(get(1)==get(n)) puts("Yes");
		else puts("No");
	}
	return 0;
}

方法二：标记法

给每个能被跳到的点打上标记，而每一个能被跳到的点不仅要满足存在上个点或上上个点能跳到这个点，还要满足起跳点也能被跳到。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100001];
bool pd[100001];
template <typename T>inline void re(T &x) {
	x=0;
	int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-f;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	x*=f;
	return;
}
int main()
{
	freopen("n.in","r",stdin);
	freopen("n.out","w",stdout);
	int t,n,d1,d2;
	re(t);
	for(int x=1;x<=t;x++)
	{
		n=0,d1=0,d2=0;
		re(n);
		re(d1);
		re(d2);
		memset(pd,0,sizeof(pd));
		pd[1]=1;
		re(a[1]);
		for(int i=2;i<=n;i++)
		{
			re(a[i]);
			if(abs(a[i]-a[i-1])<=d1&&pd[i-1])
			{
				pd[i]=1;
				continue;
			}
			if(abs(a[i]-a[i-2])<=d2&&pd[i-2]&&a[i]>a[i-1]&&a[i-1]<a[i-2])
			{
				pd[i]=1;
				continue;
			}
		}
		if(pd[n]) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

标签：

n维偏序 方法记录

题解

方法一：并查集

方法二：标记法

n维偏序方法记录