【DP bitset优化】2021牛客暑期多校训练营8 F Robots
2021-09-11 16:04:00 # ACM

题链

题目解析

有三种机器人：
  $1.$ 只能往右走；
  $2.$ 只能往下走；
  $3.$ 既能往右也能往下走；
给定 $n \times m$ 的 $01$ 矩阵，以及 $q$ 个机器人的种类，起点和终点，求每个机器人是否可达；
机器人只能走 $0$，不能走 $1$；

设 $dp[i][j]$ 表示从 $(i,j)$ 点能到达的点，可以用 $lowbit$ 优化空间，并设 $dp[i][j][x*m+y] = 1$ 表示从 $(i,j)$ 点可达 $(x,y)$ 点；

那么可以写下转移公式：

$$
dp[i][j] =
\begin {cases}
0, & \text {mp[i][j]=1} \
dp[i+1][j] \mid dp[i][j+1], & \text {mp[i][j]=0}
\end {cases}
$$

发现 $dp$ 中 $i$ 只由 $i+1$ 而来，所以优化一下空间：

$$
dp[j] =
\begin {cases}
0, & \text {mp[i][j]=1} \
dp[j] \mid dp[j+1], & \text {mp[i][j]=0}
\end {cases}
$$

将询问离线，边 $dp$ 边查询询问，记录答案；

代码实现

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 2e9
	#define MS 1005

int n,m,k;
char s[MS][MS];
bitset<MS*MS > p[MS];
struct node{
	int type;
	int sx,sy;
	int ex,ey;
	int id;
};
vector<node > vc[MS][MS];
bool ac[500005];

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> s[i]+1;
	cin >> k;
	for(int i=1;i<=k;i++){
		int type,sx,sy,ex,ey;
		cin >> type >> sx >> sy >> ex >> ey;
		vc[sx][sy].push_back({type,sx,sy,ex,ey,i});
	}
	for(int i=n;i>=1;i--){
		for(int j=m;j>=1;j--){
			// ***************************** 
			if(s[i][j] == '0'){
				p[j] |= p[j+1];
				p[j][i*m+j] = 1;
			}
			else p[j].reset();
			// *****************************
			for(auto v:vc[i][j]){
				if(v.type == 1 && v.sy == v.ey && p[j][v.ex*m+v.ey]) ac[v.id] = 1;
				else if(v.type == 2 && v.sx == v.ex && p[j][v.ex*m+v.ey]) ac[v.id] = 1;
				else if(v.type == 3 && p[j][v.ex*m+v.ey]) ac[v.id] = 1;
			}
			
		}
	}
	for(int i=1;i<=k;i++){
		if(ac[i]) cout << "yes\n";
		else cout << "no\n";
	}
	
} 

int main() {
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/

Prev
2021-09-11 16:04:00 # ACM
Next