AHOI/HNOI2018 游戏（乱搞/拓扑排序）

发表于 |
字数统计: 978字 | 阅读时长 ≈ 5min

「AHOI / HNOI2018」游戏

问题描述

一次小 G 和小 H 在玩寻宝游戏，有 $n$ 个房间排成一列，编号为 $1,2,…,n$，相邻房间之间都有 $1$ 道门。其中一部分门上有锁（因此需要对应的钥匙才能开门），其余的门都能直接打开。

现在小 G 告诉了小 H 每把锁的钥匙在哪个房间里（每把锁有且只有一把钥匙），并作出 $p$ 次指示：第 $i$ 次让小 H 从第 $S_i$ 个房间出发，去第 $T_i$ 个房间寻宝。但是小 G 有时会故意在指令里放入死路，而小 H 也不想浪费多余的体力去尝试，于是想事先调查清楚每次的指令是否存在一条通路。

你是否能为小 H 作出解答呢？

输入格式

第一行三个整数$n$，$m$，$p$，代表共有 $n$ 个房间，$m$ 道门上了锁，以及 $p$ 个询问。

接下来 $m$ 行每行有两个整数$x$，$y$，代表第 $x$ 到第 $x + 1$ 个房间的门上有把锁，并且这把锁的钥匙被放在了第 $y$ 个房间里。输入保证 $x$ 不重复。

接下来 $p$ 行，其中第 $i$ 行是两个整数 $S_i$，$T_i$，代表一次询问。

输出格式

输出 $m$ 行，每行一个大写的 YES 或 NO 分别代表能或不能到达。

样例输入

5 4 5
1 3
2 2
3 1
4 4
2 5
3 5
4 5
2 1
3 1

样例输出

YES
NO
YES
YES
NO

提示

测试点编号 n m 其他特性
1 $ \le 1000 $ $ \le 1000 $ 无
2 $ \le 1000 $ $ \le 1000 $ 无
3 $ \le 10^5 $ $ \le 10^5 $ $y \le x$ 恒成立
4 $ \le 10^5 $ $ \le 10^5 $ $y \le x$ 恒成立
5 $ \le 10^5 $ $ \le 10^5 $ 无
6 $ \le 10^5 $ $ \le 10^5 $ 无
7 $ \le 10^6 $ $ \le 10^6 $ $y \le x$ 恒成立
8 $ \le 10^6 $ $ \le 10^6 $ $y \le x$ 恒成立
9 $ \le 10^6 $ $ \le 10^6 $ 无
10 $ \le 10^6 $ $ \le 10^6 $ 无

对于所有数据，保证 $1 \le n,p \le 10^6$，$0 \le m < n$，$1 \le x, y, S_i,T_i < n$，保证 $x$ 不重复。

由于本题输入文件较大，建议在程序中使用读入优化。

显然需要处理出每个点能到的区间。一个显然的优化是到达某个点后将当前区间与该点能到的区间取并。

本题数据较水，略加优化的暴力即可AC。并且跑得比正解快。

正解是考虑每一扇门，假如$i$到$i+1$的门的钥匙在$i$的那一边，那么就只能是$i$走到$i+1$，因此从$i$向$i+1$连边，然后处理出拓扑关系，按照拓扑关系来暴力往两边拓展即可保证复杂度。

暴力代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
int n,m,q,pos[N],L[N],R[N];
bool In(int p,int i){return p>=L[i]&&p<=R[i];} 
int main()
{
	int i,j,k,x,y;
	_R(n);_R(m);_R(q);
	for(i=1;i<=m;i++)_R(x),_R(y),pos[x]=y;
	for(i=1;i<=n;i++)L[i]=R[i]=i;
	for(i=n;i>=1;i--)
	{
		while(R[i]<n)
		{
			if(!pos[R[i]]||In(pos[R[i]],i))R[i]=R[R[i]+1];
			else break;
		}
	}
	for(i=1;i<=n;i++)
	{
		while(1)
		{
			bool ok=0;
			if(L[i]>1&&(!pos[L[i]-1]||In(pos[L[i]-1],i)))
			{
				L[i]=L[L[i]-1];
				ok=1;
			}
			if(R[i]<n&&(!pos[R[i]]||In(pos[R[i]],i)))
			{
				R[i]=R[R[i]+1];
				ok=1;
			}
			if(!ok)break;
		}
	}
	for(i=1;i<=q;i++)
	{
		_R(x);_R(y);
		if(In(y,x))puts("YES");
		else puts("NO");
	}
}