自动搬运

查看原文

来自洛谷，原作者为

	wandereman 历史是沉默的，却见证了岁月如歌，生命如梦

搬运于2025-08-24 22:28:39，当前版本为作者最后更新于2025-01-21 15:46:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

我们想要知道怎么成功，不如知道怎么失败，那么我们就把失败的情况列出来：

• 一条行或列有堵塞的记录，而另一条行或列没有，如下情况：

if(l[i] != r[i] && (l[i] == -1 || r[i] == -1)){
	cout<<"NE"<<endl;
	return 0;
}
if(u[i] != d[i] && (u[i] == -1 || d[i] == -1)){
	cout<<"NE"<<endl;
	return 0;
}

• 一边是空的，却把另一边堵塞的覆盖了，如下情况：

if(l[i] + r[i] >= n){
	cout<<"NE"<<endl;
	return 0;
}
if(u[i] + d[i] >= n){
	cout<<"NE"<<endl;
	return 0;
}

• 某一行的堵塞把另一行的堵塞覆盖了，如下情况：

if(u[l[i] + 1] > i && d[l[i] + 1] > (n - i + 1){
	cout<<"NE"<<endl;
	return 0;
}

最后如果这些情况都不满足，就直接输出 DA。

AC code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+15;
ll n;
ll l[N],r[N],u[N],d[N];
int main() {
	for(i = 1;i <= n;i++){
		cin>>l[i];
	}
	for(i = 1;i <= n;i++){
		cin>>r[i];
	}
	for(i = 1;i <= n;i++){
		cin>>u[i];
	}
	for(i = 1;i <= n;i++){
		cin>>d[i];
	}
	for(i = 1;i <= n;i++){
		if(l[i] + r[i] >= n){
			cout<<"NE"<<endl;
			return 0;
		}
		if(u[i] + d[i] >= n){
			cout<<"NE"<<endl;
			return 0;
		}
		if(l[i] != r[i] && (l[i] == -1 || r[i] == -1)){
			cout<<"NE"<<endl;
			return 0;
		}
		if(u[i] != d[i] && (u[i] == -1 || d[i] == -1)){
			cout<<"NE"<<endl;
			return 0;
		}
		
		if(u[l[i] + 1] > i && d[l[i] + 1] > (n - i + 1)){
			cout<<"NE"<<endl;
			return 0;
		}
	}
	cout<<"DA"<<endl;
	return 0;
}