这是本文档旧的修订版！

错题集 3

1、The Escape Plan of Groundhog

链接

题意

给定一个 $n\times m$ 的 $01$ 矩形，求满足下列条件的子矩阵数目：

该子矩形的边界上没有 $0$
该子矩形中内部(即不含边界)的 $01$ 个数差不超过 $1$
该子矩形的长宽大于 $1$

题解

考虑 $O(n^2)$ 枚举所有的矩阵上下边界，然后 $O(n)$ 扫描所有的列。

对与约束条件一，不妨依次处理上下边界均为连续 $1$ 的区间，然后只考虑在该区间中全是 $1$ 的列的贡献。

对约束条件二，不妨将 $0$ 设为 $-1$，于是约束变为子矩阵内部的数值和绝对值不超过 $1$。

考虑桶维护区间内所有合法列的内部数值和，总时间复杂度 $O(n^3)$。

查看代码

const int MAXN=505,MAXM=MAXN*MAXN;
int a[MAXN][MAXN],b[MAXN][MAXN],s[MAXN],c[MAXM<<1];
int main()
{
	int n=read_int(),m=read_int();
	LL ans=0;
	_rep(i,1,n)_rep(j,1,m){
		a[i][j]=read_int();
		if(!a[i][j])a[i][j]=-1;
		b[i][j]=b[i-1][j]+a[i][j];
	}
	_rep(i,1,n)_rep(j,i+1,n){
		int last=0;
		s[last]=MAXM;
		_rep(k,1,m){
			if(a[i][k]==-1||a[j][k]==-1){
				_rep(t,last+1,k){
					if(b[j][t]-b[i-1][t]==j-i+1)
					c[s[t]]--;
				}
				s[last=k]=MAXM;
			}
			else{
				s[k]=s[k-1]+b[j-1][k]-b[i][k];
				if(b[j][k]-b[i-1][k]==j-i+1)
				ans+=c[s[k-1]-1]+c[s[k-1]]+c[s[k-1]+1],c[s[k]]++;
			}
		}
		_rep(k,last+1,m){
			if(b[j][k]-b[i-1][k]==j-i+1)
			c[s[k]]--;
		}
	}
	enter(ans);
	return 0;
}

CVBB ACM Team

目录

错题集 3

1、The Escape Plan of Groundhog

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

错题集 3

1、The Escape Plan of Groundhog

题意

题解

页面工具