CF2159B Rectangles 题解

打 Duel 时跳出来的 *2100 的题。
注意到

nm\le2.5\times10^5

，不妨

n\le m

（否则转置一下即可），则有

n\le\sqrt{nm}

。
我们枚举两行，尝试处理两行之间的矩形。
显然只有与选定两行交叉点均为

1

的列才是合法的列。

观察发现选定两行后，若一个矩形内部有更小的矩形，那么这个矩形没有意义。
所以我们只需要记录上一个满足条件的列，大力更新即可。
时间复杂度

O(n^2m^2)

，无法通过。
考虑优化，注意到我们固定第一行后，更新的每个矩形上边界均为该行，对每一列而言就是前缀

\min

操作，可以离线下来统一处理。

时间复杂度为

O(n^2m)

，而

n\le \sqrt{nm}

，总复杂度

O(nm\sqrt{nm})

，可以通过。

CPP

#include<bits/stdc++.h>
using namespace std;
int memory[4000005];//内存池
int *a[505];
int *ans[505];
int *b[505];//用于记录固定第一行后的答案
int *p;//内存池当前未占用的第一个位置
int n,m;
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; cin>>t; while(t--){
		p=memory;
		cin>>n>>m;
		bool flag=n>=m; if(flag) swap(n,m);
		for(int i=1;i<=n;i++){
			a[i]=p; p+=m+2;
		}
		for(int i=1;i<=n;i++){
			ans[i]=p; p+=m+2;
		}
		for(int i=1;i<=n;i++){
			b[i]=p; p+=m+2;
		}
		if(flag){//处理转置问题
			for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){
				char c; cin>>c; a[j][i]=c=='1';
			}
		}else{
			for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
				char c; cin>>c; a[i][j]=c=='1';
			}
		}
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans[i][j]=0x3f3f3f3f;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) for(int k=1;k<=m;k++) b[j][k]=0x3f3f3f3f;
			for(int j=i+1;j<=n;j++){
				int beg=m+1;
				for(int k=1;k<=m;k++){
					if(a[i][k]&&a[j][k]){
						for(int l=beg;l<=k;l++) b[j][l]=min(b[j][l],(j-i+1)*(k-beg+1));//只更新b[j][l]，离线处理
						beg=k;
					}
				}
			}
			for(int j=n;j>i;j--) for(int k=1;k<=m;k++) b[j-1][k]=min(b[j-1][k],b[j][k]);//统一进行 min 操作
			for(int j=i;j<=n;j++) for(int k=1;k<=m;k++) ans[j][k]=min(ans[j][k],b[j][k]);
		}
		if(flag){//处理转置问题
			for(int i=1;i<=m;i++){
				for(int j=1;j<=n;j++){
					if(ans[j][i]==0x3f3f3f3f) ans[j][i]=0;
					cout<<ans[j][i]<<' ';
				}
				cout<<'\n';
			}
		}else{
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++){
					if(ans[i][j]==0x3f3f3f3f) ans[i][j]=0;
					cout<<ans[i][j]<<' ';
				}
				cout<<'\n';
			}
		}
		memset(memory,0,(p-memory+20)<<2);
	}
	return 0;
}

CF2159B Rectangles 题解

文章操作

相关推荐

评论

CF2159B Rectangles 题解