专栏文章

题解：P4858 [PA 2013] Karty

sstrapplE
P4858题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipcacpo
此快照首次捕获于
2025/12/03 09:39
3 个月前
此快照最后确认于
2025/12/03 09:39
3 个月前
查看原文
很神秘的一个题啊。感觉真可以上位紫或者黑了。
下面我们称 X 为非障碍点，_ 为障碍点。首先做一些 trivial 的转化：多加矩形一定不会变劣，因此我们要求，所有非障碍点，都要有一个 r×cr\times c 的无障碍矩形包含它。因此 (r,c)(r,c) 合法当且仅当每个非障碍点都对 r×cr\times c 合法。
接下来还能观察到，显而易见的是，设 mxcrmxc_r 为最大的 cc 使得 (r,c)(r,c) 合法，不存在则为 00。那么因为 (r,c)(r,c) 合法可以直接得到 (r−1,c)(r-1,c) 和 (r,c−1)(r,c-1) 合法，因此 mxcrmxc_r 单调不增。因此直接暴力，你可以双指针去做，我们就可以 O(n3)O(n^3) 了。
但是你发现刚才的想法不太容易扩展。这只能说明我们有的性质还不太够，因此在下面，你要观察到一个最重要，也最神经的结论：
对一个固定的 (r,c)(r,c)，如果一个点的"包围圈"都合法，它自然就合法了。
刚才是自然语言或者说是感性理解，接下来我们严谨地刻画一下：对一个非障碍点 (x,y)(x,y)，找到包含它的极大的无障碍四连通块。如果靠在四连通块边上的点（这种点需要满足，和一个障碍点或界外相邻）都合法，则 (x,y)(x,y) 合法。其实这个结论比刚才说的包围圈弱一些，不过至少我会证，而且下面说的做法也只依赖于这个性质。
这个怎么理解呢？
首先你可以手摸一下，发现 (x,y)(x,y) 四周如果都是合法非障碍，则 (x,y)(x,y) 也合法。还可以做一些加强：如果三边都合法，则 (x,y)(x,y) 也合法（这个证明并不困难，就不说了）。我们可以在这个感觉的基础上加以证明：
现在所有边上的点都已经合法了，要证明中间的也要合法。从上往下归纳。设目前考虑到的为 (x,y)(x,y)。
第一点：很容易发现，如果 (x,y−k)(x,y-k)（其中 1<k≤c1<k\leq c）为障碍点，则取 kk 最小的一个，那么因为 (x,y−k+1)(x,y-k+1) 合法，它的矩形一定包含 (x,y)(x,y)，所以 (x,y)(x,y) 合法。同理 (x,y+k)(x,y+k) 和 (x−k,y)(x-k,y) 也是。下面，我们只需要证明，蓝色部分都非障碍的基础上，(x,y)(x,y) 合法即可。
接下来，第二点：如果 (x−1,y−k)(x-1,y-k) 为障碍点，取 kk 最小的一个，那么 (x−1,y−k+1)(x-1,y-k+1) 合法，它的矩形如果包含 (x,y)(x,y) 就结束了，否则下边界为 (x−1)(x-1)，而且此时 xx 这一行都非障碍，导出 (x,y)(x,y) 也合法，因此只需考虑 (x−1,y−k)(x-1,y-k) 非障碍的情况即可。
以此类推，蓝色会越来越多：
最后整个 (r+1)×(2c+1)(r+1)\times (2c+1) 的部分都蓝了，那么 (x,y)(x,y) 显然合法了。
好了，话说这么多，就是为了证明一个结论：对于每个 (r,c)(r,c)，只考虑边上的点的合法性和考虑所有的合法性是等价的。
那么怎么完全解决这个题呢？其实就容易多了。
对每个边上的点，我们把障碍转到它下面（对不同的障碍，共四种不同角度的转法，都要试一次），则它的矩形只能往上左右扩展。枚举它的行 ii，设 hjh_j 表示 (i,j)(i,j) 往上能走多远。则对一个下面是障碍的非障碍位置，可以形成若干个极大矩形，都取个 min⁡\min 就行了。
然而这样复杂度还是三方。你会发现，很多区间是没啥用的，只需要关注"极长"的段即可。这部分我的解决方法是建小根笛卡尔树，只需要考虑它的所有子树。不过可能有更容易的做法，但是 anyway，时间复杂度是 O(nm)O(nm)，空间可以做到除读入外 O(n+m)O(n+m)。下面给了一种实现：
CPP
#include<bits/stdc++.h>
using namespace std;
char ss[2505][2505];
int a[2505][2505],b[2505][2505];
int h[2505],d[2505],s[2505],ans[2505];
void get(int rr,int cc){
	ans[rr+1]=min(ans[rr+1],cc);
}
int ls[2505],rs[2505],st[2505],L[2505],R[2505];
void dfs(int x){
	if(ls[x]){
		dfs(ls[x]);L[x]=L[ls[x]];
		if(s[R[ls[x]]]>s[L[ls[x]]-1])get(d[x],R[ls[x]]-L[ls[x]]+1);
	}
	if(rs[x]){
		dfs(rs[x]);R[x]=R[rs[x]];
		if(s[R[rs[x]]]>s[L[rs[x]]-1])get(d[x],R[rs[x]]-L[rs[x]]+1);
	}
}
void sfd(int x){
	if(ls[x]){
		sfd(ls[x]);L[x]=L[ls[x]];
		if(s[R[ls[x]]]>s[L[ls[x]]-1])get(R[ls[x]]-L[ls[x]]+1,d[x]);
	}
	if(rs[x]){
		sfd(rs[x]);R[x]=R[rs[x]];
		if(s[R[rs[x]]]>s[L[rs[x]]-1])get(R[rs[x]]-L[rs[x]]+1,d[x]);
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%s",ss[i]+1);
	for(int i=0;i<=n;++i)ans[i]=m;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
		a[i][j]=b[j][i]=(ss[i][j]=='X');
	}
	for(int i=1;i<=m;++i)h[i]=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			h[j]=a[i][j]*(h[j]+1),s[j]=s[j-1]+(a[i][j]&&!a[i+1][j]);
			d[j]=(a[i][j]?h[j]:n+1);if(s[j]>s[j-1])get(h[j],0);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=m;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		dfs(st[1]);
	}
	for(int i=1;i<=m;++i)h[i]=0;
	for(int i=n;i>=1;--i){
		for(int j=1;j<=m;++j){
			h[j]=a[i][j]*(h[j]+1),s[j]=s[j-1]+(a[i][j]&&!a[i-1][j]);
			d[j]=(a[i][j]?h[j]:n+1);if(s[j]>s[j-1])get(h[j],0);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=m;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		dfs(st[1]);
	}
	for(int i=1;i<=n;++i)h[i]=0;
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			h[j]=a[j][i]*(h[j]+1),s[j]=s[j-1]+(a[j][i]&&!a[j][i+1]);
			d[j]=(a[j][i]?h[j]:m+1);if(s[j]>s[j-1])get(0,h[j]);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=n;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		sfd(st[1]);
	}
	for(int i=1;i<=n;++i)h[i]=0;
	for(int i=m;i>=1;--i){
		for(int j=1;j<=n;++j){
			h[j]=a[j][i]*(h[j]+1),s[j]=s[j-1]+(a[j][i]&&!a[j][i-1]);
			d[j]=(a[j][i]?h[j]:m+1);if(s[j]>s[j-1])get(0,h[j]);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=n;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		sfd(st[1]);
	}
	int mn=-1,r=0,c=0;
	for(int i=1;i<=n;++i){
		ans[i]=min(ans[i-1],ans[i]);
		if(mn<i*ans[i])mn=i*ans[i],r=i,c=ans[i];
	}
	printf("%d %d\n",r,c);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...