• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

题解 CF232E 【Quick Tortoise】

互联网 diligentman 6个月前 (10-30) 51次浏览

题解 –

C

F

232

E

mathrm{CF232E}

CF232E

题目意思

题目传送门

给你一张

n

×

m

ntimes m

n×m 的图。

Q

Q

Q 次询问

(

x

,

y

,

x

1

,

y

1

)

(x,y,x_1,y_1)

(x,y,x1,y1) 问你能否从

(

x

,

y

)

(

x

1

,

y

1

)

(x,y)sim(x_1,y_1)

(x,y)(x1,y1)

n

,

m

500

,

Q

6

e

5

n,mleq 500,Qleq 6e5

n,m500,Q6e5

S

o

l

mathrm{Sol}

Sol

分治 +

d

p

mathrm{dp}

dp +

b

i

t

s

e

t

mathrm{bitset}

bitset 做法

我们考虑离线做。

考虑如何判定能走到,我们对于每一行

l

l

l

f

i

,

j

,

k

f_{i,j,k}

fi,j,k 表示哪些

(

i

,

j

)

(

i

[

1

,

l

]

)

(i,j)(i∈[1,l])

(i,j)(i[1,l]) 能够走到

(

l

,

k

)

(l,k)

(l,k)

同时设

g

i

,

j

,

k

g_{i,j,k}

gi,j,k 哪些

(

i

,

j

)

(

i

[

l

,

n

]

)

(i,j)(i∈[l,n])

(i,j)(i[l,n]) 能够走到

(

l

,

k

)

(l,k)

(l,k)。转移很简单

我们考虑分治来优化这个枚举

l

l

l 的过程。我们以

x

x

x 坐标进行分治,每次分治一边做掉一对起点终点在两端的询问。对于那些全部在一段的询问继续分治即可。

以及我们可以把 dp 用

b

i

t

s

e

t

mathrm{bitset}

bitset优化,时间复杂度

O

(

log

n

×

n

m

2

w

)

O(log ntimes frac{nm^2}{w})

O(logn×wnm2)

C

o

d

e

mathrm{Code}

Code

int n,m,Q,Ans[M];
char ch[N][N];
struct Node
{
	int x,y,fx,fy,id;
};
vector<Node> que;
bitset<N> f[N][N],g[N][N];
inline void solve(int l,int r,vector<Node> v) 
{
	if(l>r) return;
	int mid=l+r>>1,sz=(int)v.size();
	if(!sz) return;
	Dow(i,mid,l) Dow(j,m,1) 
	{
		f[i][j].reset(); 
		if(ch[i][j]!='#') 
		{
			if(i==mid) f[i][j][j]=1;
			else f[i][j]|=f[i+1][j];
			if(j<m) f[i][j]|=f[i][j+1];
		}
	}
	For(i,mid,r) For(j,1,m) 
	{
		g[i][j].reset();
		if(ch[i][j]!='#') 
		{
			if(i==mid) g[i][j][j]=1;
			else g[i][j]|=g[i-1][j];
			if(j!=1) g[i][j]|=g[i][j-1];
		}
	}
	vector<Node> L,R;
	for(Node i:v) 
	{
		if(i.fx<mid) L.pb(i); 
		else if(i.x>mid) R.pb(i);
		else Ans[i.id]|=((f[i.x][i.y]&g[i.fx][i.fy]).count()>=1); 
	}
	solve(l,mid-1,L),solve(mid+1,r,R);
}
int main()
{
	io.read(n),io.read(m);
	For(i,1,n) scanf("%s",ch[i]+1); 
	io.read(Q);
	For(i,1,Q)
	{
		int x,y,fx,fy;
		io.read(x),io.read(y),io.read(fx),io.read(fy);
		que.pb((Node){x,y,fx,fy,i});
	}
	solve(1,n,que);
	For(i,1,Q) puts((Ans[i])?"Yes":"No");
	return 0;
}


程序员灯塔
转载请注明原文链接:题解 CF232E 【Quick Tortoise】
喜欢 (0)