专栏文章

B4222 [常州市赛 2023] 积木题解

ddongrunxuan
B4222题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miod7g28
此快照首次捕获于
2025/12/02 17:17
3 个月前
此快照最后确认于
2025/12/02 17:17
3 个月前
查看原文

B4222 [常州市赛 2023] 积木 题解

看到题解区均为二位前缀和的做法，这里提供二维 ST 表做法。

思路

首先肯定考虑二分。问题转化为求是否存在范围为 mid×midmid\times mid 的矩形满足矩形内每一个元素值均大于 midmid。
注意到这里是判断区间最小值是否大于定值，考虑使用二维 ST 表维护，注意不同于一维，二维的判断需四个值进行维护。
最后输出的值为取走的方块数，所以应输出 sum−ans3sum - ans^3。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e3+5;
int n,m,sum;
int lg[maxn];
int st[25][maxn][maxn];
int minm(int x,int y,int aa,int bb)
{
	int res=min(aa,bb);
	res=min(res,y);
	res=min(res,x);
	return res;
}
int calc(int x,int y,int len)
{
	int sz=lg[len];
	return minm(st[sz][x][y],st[sz][x+len-(1<<sz)][y],st[sz][x][y+len-(1<<sz)],st[sz][x+len-(1<<sz)][y+len-(1<<sz)]);
}
bool check(int x)
{
    for(int i=1;i<=n-x;i++)
    {
    	for(int j=1;j<=m-x;j++)
    	{
    		if(calc(i,j,x)>=x)
    		{
    			return 1;
			}
		}
	}
    return 0;
}
signed main()
{
	cin>>n>>m;
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>st[0][i][j];
			sum+=st[0][i][j];			
		}
	}
	int mx=lg[min(n,m)];
	for(int k=1;k<=mx;k++)
	{
		for(int i=1;i+(1<<k)-1<=n;i++)
		{
			for(int j=1;j+(1<<k)-1<=m;j++)
			{
				st[k][i][j]=minm(st[k-1][i][j],st[k-1][i+(1<<k-1)][j],st[k-1][i][j+(1<<k-1)],st[k-1][i+(1<<k-1)][j+(1<<k-1)]);
			}				
		}
	}
	int l=1,r=min(n,m);
	int ans=1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}	
    cout<<sum-ans*ans*ans;
	return 0;
}

评论

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

正在加载评论...