#C241128A. 再种花

标签（Label）

单调栈
思维

网址（Website）

题目详情 - 再种花 - Super

题解 - 再种花 - Super

题目（Problem）

输入数据 1

输出数据 1

样例 2

见选手目录下的 $plant/plant2.in$ 与 $plant/plant2.ans$。

该样例数据满足测试点 $3$ 的性质。

样例 3

见选手目录下的 $plant/plant3.in$ 与 $plant/plant3.ans$。

该样例数据满足测试点 $6$ 的性质。

样例 4

见选手目录下的 $plant/plant4.in$ 与 $plant/plant4.ans$。

该样例数据满足测试点 $8, 9$ 的性质。

样例 5

见选手目录下的 $plant/plant5.in$ 与 $plant/plant5.ans$。

该样例数据满足测试点 $12, 13, 14$ 的性质。

样例 6

见选手目录下的 $plant/plant6.in$ 与 $plant/plant6.ans$。

该样例数据满足测试点 $17, 18$ 的性质。

样例 7

见选手目录下的 $plant/plant7.in$ 与 $plant/plant7.ans$。

该样例数据满足测试点 $21, 22, 23$ 的性质。

样例 8

见选手目录下的 $plant/plant8.in$ 与 $plant/plant8.ans$。

该样例数据满足测试点 $25$ 的性质。

题解（Solution）

矩阵有几种处理方法，一个是枚举左上角，一个是枚举矩阵的上下边界，还有就是无视矩阵的限制，直接将整个矩阵二分。

枚举上下边界很明显应该用双指针优化复杂度，这道题使用双指针还是 $O(n^3)$ 的，并不能优化，探索了半天发现这种方法不行。无奈只能想回枚举左端点。

矩阵有一个明显的预处理就是先计算出每个点 $(x,y)$ 向某个方向能延伸到最多哪个地方，这个是能在 $O(nm)$ 的时间内处理的。那么我们令 $f_{i,j}$ 表示 $(i,j)$ 这个点向右最多有多少个零。

固定了左上角后，画出所有可能的矩形所有可能的矩形，发现当前点的答案就是一个阶梯状的图形，大致长这样：

后面的直接使用单调栈优化，并且维护矩形面积就好了。

时间复杂度：$O(Tnm)$ 。

出题者题解

代码（Code）

100分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,n) {For(o,1,n) cerr<<a[o]<<' ';cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10), putchar('0'+x%10);
}constexpr int inf = 0x3f3f3f3f3f3f3f3fll;
constexpr int mod = 998244353ll;
constexpr int N = 2005;
bool ST;int Tt,tid;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void sub(int &x,int y){if((x-=y)<0)x+=mod;}

int a[N][N];
int n,m,ans;

int f[N][N],g[N][N];
int st[N],tp;

void Solve(){
	n=rd(),m=rd(),ans=0;For(i,1,n){
		char s[N];scanf("%s",s+1);
		For(j,1,m) a[i][j] = s[j]=='1';
	}
	For(i,1,n){
		int r = m;
		Rof(j,m,1){
			if(a[i][j]) r=j-1;
			f[i][j] = r;
		}
	}
	For(j,1,m){
		int s = 0; st[tp=0]=n+1;
		Rof(i,n,1){
			while(tp && f[i][j] <= f[st[tp]][j]) sub(s, g[st[tp]][j]), tp--;
			g[i][j] = (st[tp]-i)*(f[i][j]-j+1)%mod;
			add(s, g[i][j]), st[++tp] = i;
			
			add(ans, s);
		} 
	}write((ans%mod+mod)%mod), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("plant.in","r",stdin);
	freopen("plant.out","w",stdout);
	Tt=rd(),tid=rd();double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}