原题链接
https://ac.nowcoder.com/acm/contest/11259/F
题目大意
有一个
n
×
m
(
1
≤
n
,
m
≤
500
)
n\times m(1\le n,m\le 500)
n×m(1≤n,m≤500)大小的网格，左上角是
(
1
,
1
)
(1,1)
(1,1)，右下角是
(
n
,
m
)
(n,m)
(n,m)，其中有一些无法通过的格子。
有以下三种机器人：
1.只能向下移动的机器人，即只能从
(
x
,
y
)
(x,y)
(x,y)移动到
(
x
+
1
,
y
)
(x+1,y)
(x+1,y)；
2.只能向右移动的机器人，即只能从
(
x
,
y
)
(x,y)
(x,y)移动到
(
x
,
y
+
1
)
(x,y+1)
(x,y+1)；
3.既可以向下也可以向右移动的机器人；
有
q
(
1
≤
q
≤
5
×
1
0
5
)
q(1\le q\le 5\times 10^5)
q(1≤q≤5×105)次询问
t
t
t型机器人需要从起点
(
x
1
,
y
1
)
(x1,y1)
(x1,y1)前往终点
(
x
2
,
y
2
)
(x2,y2)
(x2,y2)，判断是否可行。
题解
1和2这两种机器人可以直接通过前缀和来得知中间是否存在障碍物，是非常简单的。
然后就是第三种机器人的情况。
我们假设
d
p
x
1
,
y
1
,
x
2
,
y
2
dp_{x_1,y_1,x_2,y_2}
dpx1?,y1?,x2?,y2??记录能否从
(
x
1
,
y
1
)
(x_1,y_1)
(x1?,y1?)到
(
x
2
,
y
2
)
(x_2,y_2)
(x2?,y2?)，但是直接枚举的复杂度过高，达到了
O
(
q
×
n
4
)
O(q\times n^4)
O(q×n4)，所以我们通过采取
b
i
t
s
e
t
bitset
bitset的算法来进行优化，并进行离线操作，算出同一起点（或终点）的情况，将复杂度将至
O
(
n
4
64
)
O(\frac{n^4}{64})
O(64n4?)。
并得到以下转移式：
d
p
x
1
,
y
1
=
d
p
x
1
+
1
,
y
1
∣
d
p
x
1
,
y
1
+
1
∣
(
x
1
,
y
1
)
dp_{x_1,y_1}=dp_{x_1+1,y_1}|dp_{x_1,y_1+1}|(x_1,y_1)
dpx1?,y1??=dpx1?+1,y1??∣dpx1?,y1?+1?∣(x1?,y1?)
当然了，我们还可以进行进一步优化，将第一维度压缩掉，时间复杂度进一步降低。
参考代码
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
const int N=5e3+5;
int n,m,q,X[N][N],Y[N][N],op,lx,ly,rx,ry;
bitset<N>vis[N];
char c[N][N];
bool ans[500005];
struct P{int rx,ly,ry,id;};
vector<P>p[N],t[N];
int main(){
scanf("%d%d",&n,&m);
FOR(i,1,n){scanf("%s",c[i]+1);FOR(j,1,m)X[i][j]=X[i][j-1]+(c[i][j]=='1'),Y[i][j]=Y[i-1][j]+(c[i][j]=='1');}
scanf("%d",&q);
FOR(i,1,q){
scanf("%d%d%d%d%d",&op,&lx,&ly,&rx,&ry);
if(op==1){if(ly==ry&&rx>=lx&&Y[rx][ly]-Y[lx-1][ly]==0)ans[i]=1;}
else if(op==2){if(lx==rx&&ry>=ly&&X[lx][ry]-X[lx][ly-1]==0)ans[i]=1;}
else if(lx<=rx&&ly<=ry)p[lx].pb({rx,ly,ry,i});
}
FOR(l,1,n){
for(auto o:p[l])t[o.rx].pb(o);FOR(i,1,m)vis[i].reset();
FOR(i,1,m)if(c[l][i]=='1')vis[i].reset();else vis[i][i]=1,vis[i]|=vis[i-1];
FOR(r,l,n){
FOR(i,1,m){vis[i]|=vis[i-1];if(c[r][i]=='1')vis[i].reset();}
for(auto o:t[r])ans[o.id]=vis[o.ry][o.ly];
t[r].clear();
}
}
FOR(i,1,q)puts(ans[i]?"yes":"no");
}
|