2016-2017 ACM-ICPC, Central Europe Regional Contest (CERC 16) H - Hangar Hurdles

2016-2017 ACM-ICPC, Central Europe Regional Contest (CERC 16) H - Hangar Hurdles

八月 06, 2021

题目概述

给一个由.和#组成的地图。现在要回答若干询问,从$(x_1,y_1)$​到$(x_2,y_2)$能够滑动的最大正方形的边长为多少。所谓能滑动就是路经的各个方格所能扩展的不碰到#的最大正方形。

分析与解

先说说考场上那种看起来很多，但种种原因不能通过的解法。

首先我们可以预处理出每个点能够允许的最大正方形。这里先说一下还是应该枚举半边长以保证正方形边长是奇数。然后我们把所有的节点从大到小依次加入到图中，用并查集来维护联通关系。把所有的询问离线，然后取询问的两个点的对应最大正方形边长的较小值来排序，从大到小回答询问。然后从大到小遍历边长，处理询问。如果某个询问不能在它对应的较小值时被处理，就把它放到一个队列里。这个队列也不断地取队首尝试回答询问。最后再按照原顺序输出即可。

这个解法的RE原因只不过是局部变量没赋初值，但WA之后就很难调了。理论上分析它的漏洞在于可能一些询问会反反复复出入队列，造成时间的问题。

下面来说正解。

其实基本要点已经体现了。就是我们要控制节点之间的连通性，是从大到小的添加边。而这正是我们用Kruskal做一棵最大生成树的流程。所以我们把每个点向四周能连边的连边，边的权值就是两个点最大正方形边长的最小值，然后跑一下Kruskal得到生成树。那么处理询问，就是看这个重构树上对应路径的最小边权值。求这个东西就很经典，相当于边倍增找LCA，边更新答案。

由于可能有许多的树（森林），所以树链剖分+LCA就不适用了，还是得用倍增。

具体细节见代码。

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) (a) < (b) ? (a) : (b)
#define max(a,b) (a) > (b) ? (a) : (b)
#define MAXN 2010
#define fir first
#define sec second
typedef long long LL;
typedef pair<int,int> pii;
int n,q;
char s[MAXN][MAXN];
int sum[MAXN][MAXN],mmax[MAXN][MAXN];
bool check2(int x,int y) {
	if(x<1 || x>n || y<1 || y>n || s[x][y]=='#')return false;
	return true;
}
bool check(int x,int y,int t) {
	int x1,y1,x2,y2;
	x2=x+t-1,y2=y+t-1;
	x1=x-t+1,y1=y-t+1;
	if(!check2(x1,y1) || !check2(x2,y2))return false;
	return (sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]==0);
}
#define MAXN2 1001000
namespace Tree {
	struct node {
		int v,len;
		node *nnext;
	} pool[MAXN2<<2],*h[MAXN2<<2];
	int cnt=-1;
	void addedge(int u,int v,int len) {
		node *p=&pool[++cnt];
		p->v=v,p->len=len,p->nnext=h[u],h[u]=p;
		node *q=&pool[++cnt];
		q->v=u,q->len=len,q->nnext=h[v],h[v]=q;
	}
	int f[MAXN2][21],anc[MAXN2][21];
	int dep[MAXN2];
	void dfs(int u,int fa) {
		int v,mid;
		for(int i=1; i<=20; i++) {
			mid=anc[u][i-1];
			anc[u][i]=anc[mid][i-1];
			f[u][i]=min(f[u][i-1],f[mid][i-1]);
		}
		for(node *p=h[u]; p; p=p->nnext) {
			v=p->v;
			if(v!=fa) {
				dep[v]=dep[u]+1;
				f[v][0]=p->len;
				anc[v][0]=u;
				dfs(v,u);
			}
		}
	}
	int get_ans(int x,int y) {
		int ans=0x3f3f3f3f;
		if(dep[x] < dep[y])swap(x,y);
		for(int i=20; i>=0; i--) //跳到同一起点
			if(dep[anc[x][i]] >= dep[y]) {  //!等号
				ans=min(ans,f[x][i]);
				x=anc[x][i];
			}
		if(x==y) return ans;
		for(int i=20; i>=0; i--)
			if(anc[x][i]!=anc[y][i]) {
				ans=min(ans,f[x][i]);
				ans=min(ans,f[y][i]);
				x=anc[x][i];
				y=anc[y][i];
			}
		ans=min(ans,f[x][0]);
		ans=min(ans,f[y][0]);
		return ans;
	}
}
namespace Kru {
	struct edge {
		int u,v,len;
	} e[MAXN2<<2];
	int ecnt;
	bool cmp(edge a,edge b) {
		return a.len > b.len;
	}
	int p[MAXN2];
	int ffind(int x) {
		if(p[x]==x)return x;
		return p[x]=ffind(p[x]);
	}
	void kruskal() {
		int fx,fy;
		sort(e+1,e+ecnt+1,cmp);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				p[(i-1)*n+j]=(i-1)*n+j;
		for(int i=1; i<=ecnt; i++) {
			fx=ffind(e[i].u),fy=ffind(e[i].v);
			if(fx!=fy) {
				p[fy]=fx;
				Tree::addedge(e[i].u,e[i].v,e[i].len);  //并不能用并查集的标号来
			}
		}
	}
}
int main() {
	int lef,rig,mid;  //局部变量的初始化？
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%s",s[i]+1);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			sum[i][j]=sum[i][j-1]+((s[i][j]=='#') ? 1 : 0);
	for(int j=1; j<=n; j++)
		for(int i=1; i<=n; i++)
			sum[i][j]+=sum[i-1][j];
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(s[i][j]=='#')continue;
			lef=1,rig=n;
			while(lef<=rig) {
				mid=(lef+rig)>>1;
				if(check(i,j,mid)) {
					mmax[i][j]=max(mmax[i][j],2*(mid-1)+1);
					lef=mid+1;
				} else rig=mid-1;
			}
		}
	}
	int dx[2]= {1,0},dy[2]= {0,1};
	int nx,ny;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			if(s[i][j]=='#')continue;
			for(int l=0; l<2; l++) {
				nx=i+dx[l],ny=j+dy[l];
				if(check2(nx,ny))
					Kru::e[++Kru::ecnt]= {(i-1)*n+j,(nx-1)*n+ny,min(mmax[i][j],mmax[nx][ny])};

			}
		}
	Kru::kruskal();
	memset(Tree::f[0],63,sizeof(Tree::f[0]));//!
	for(int i=1;i<=n;i++) //仍应该考虑森林情况 
		for(int j=1;j<=n;j++)
		{
			if(s[i][j]=='#')continue;
			if(!Tree::dep[(i-1)*n+j])
			{
				Tree::dep[(i-1)*n+j]=1;
				Tree::dfs((i-1)*n+j,0);
			}
		}
	int q,x1,y1,x2,y2;
	scanf("%d",&q);
	for(int i=1; i<=q; i++) {
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(Kru::ffind((x1-1)*n+y1)!=Kru::ffind((x2-1)*n+y2))printf("0\n");
		else printf("%d\n",Tree::get_ans((x1-1)*n+y1,(x2-1)*n+y2));
	}
	return 0;
}