首页 > 其他分享 >【题解】CF364E Empty Rectangles

【题解】CF364E Empty Rectangles

时间:2023-02-13 16:23:07浏览次数:49  
标签:yl xl int 题解 CF364E xr dw yr Rectangles

题目分析:

如果题目放在序列上,也就是询问一个长度为 \(n\) 的序列有多少个子段满足其和为 \(k\),那么考虑应该怎么做。
显然就是使用分治,即左边的答案+右边的答案+跨过中间的答案。
跨过中点的答案就可以使用一个类似卷积的方式去求,因为只需要求 \(k\) 这一项所以就可以做到 \(O(k)\) 了。

放在二维上显然也可以使用类似的思路去思考,也就是用 K-D Tree 建树式的方法,每次按横坐标或纵坐标划分。
因为我们要求的是一个矩阵所以我们可以考虑枚举一下矩阵的左右端点,然后其实发现如果是去预处理矩阵和等于 \(k\) 的子矩阵是很难办的,所以就差分一下,求一下矩阵和小于 \(k\) 的子矩阵,就可以设 \(up_i\) 表示矩阵和小于 \(i\) 的子矩阵的最上(左)面对应的坐标,\(dw_i\) 就是最下(右)面对应的坐标,因为随着 \(r\) 的递增 \(up\) 和 \(dw\) 是满足单调性的,所以就可以直接扫一遍求出来。

那么最后的统计答案显然就是 \(\sum_{i=0}^k (up_i - up_{i+1}) \times (dw_{k - i + 1} - dw_{k - i})\)

代码:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3+5;
int sum[N][N],up[N],dw[N],res,n,m,k;
char s[N];
int get(int xl,int xr,int yl,int yr){
	return sum[xr][yr] - sum[xl][yr] - sum[xr][yl] + sum[xl][yl];
}
void solve(int xl,int xr,int yl,int yr,int opt){
	if(xl == xr || yl == yr)	return;
	if(xr == xl+1 && yr == yl + 1){
		res += (get(xl,xr,yl,yr) == k);
		return;
	}
	if(opt == 0){
		int mid = (yl + yr)>>1;
		for(int l=xl; l<=xr; l++){
			up[0] = dw[0] = mid;
			for(int i=1; i<=k+1; i++)	up[i] = yl,dw[i] = yr;
			for(int r = l + 1; r <= xr; r++){
				for(int i=1; i<=k+1; i++){
					while(get(l,r,up[i],mid) >= i)	up[i]++;
					while(get(l,r,mid,dw[i]) >= i)	dw[i]--;
				}
				for(int i=0; i<=k; i++)	res += (up[i] - up[i+1]) * (dw[k-i+1] - dw[k-i]);
			}
		}
		solve(xl,xr,yl,mid,1);solve(xl,xr,mid,yr,1);
	}
	else{
		int mid = (xl + xr)>>1;
		for(int l=yl; l<=yr; l++){
			up[0] = dw[0] = mid;
			for(int i=1; i<=k+1; i++)	up[i] = xl,dw[i] = xr;
			for(int r = l + 1; r <= yr; r++){
				for(int i=1; i<=k+1; i++){
					while(get(up[i],mid,l,r) >= i)	up[i]++;
					while(get(mid,dw[i],l,r) >= i)	dw[i]--;
				}
				for(int i=0; i<=k; i++)	res += (up[i] - up[i+1]) * (dw[k-i+1] - dw[k-i]);
			}
		}
		solve(xl,mid,yl,yr,0);solve(mid,xr,yl,yr,0);
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		for(int j=1; j<=m; j++){
			sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + (s[j] == '1');
		}
	}
	solve(0,n,0,m,1);
	printf("%lld\n",res);
	return 0;
}

标签:yl,xl,int,题解,CF364E,xr,dw,yr,Rectangles
From: https://www.cnblogs.com/linyihdfj/p/17116732.html

相关文章

  • 【题解】CF150E Freezing with Style
    题目分析:看到中位数最大显然可以想到直接二分这个中位数,然后将大于等于的边设为\(1\)小于的设为\(-1\),那么一条路径权值和大于等于\(0\)就意味着中位数大于等于二分......
  • org.apache.ibatis.binding.BindingException: Parameter ‘XXXX‘ not found.的问题
    文章目录​​问题分析​​​​[1]两个普通参数​​​​[2]既有参数又有对象​​问题分析是当Dao层的方法有多个参数的时候,我们需要加入@Param注解我下面都是用注解开发的,不......
  • JAVA - - - HashMap常见问题解答
    HashMap与ConcurrentHashMap的异同都是key-value形式的存储数据;HashMap是线程不安全的,ConcurrentHashMap是JUC下的线程安全的;HashMap底层数据结构是数组+......
  • 联想笔记本充电周期达到300问题解决。
       1.发现联想笔记本电源低于45W就会损耗电池周期;高于45W时电池则直接用充电器电,右下角的叹号也会消失。2.笔记本默认电源就只有45W。如果用了type-c扩展坞,走PD......
  • L5-NOIP模拟11 测试题解
    经典老题排名-L5-NOIP模拟11-码创未来A.[CQOI2009]中位数洛谷P1627|码创未来题意给出\(1,2,\dots,n\)的一个排列,统计该排列有多少个长度为奇数的连续子串......
  • 期末复习 | CUMT数据结构实验期末——精简版题解
    前言该博客保存了博主本人的刷题记录,博客中题源来自学长博客和CUMTOJ,但是由于本人记性不好,忘记了CUMTOJ的密码TT,如有错误敬请指正!该博客的解题代码很大程度上参照了Acwi......
  • 第十一届蓝桥杯题解
    第十一届蓝桥杯题解A,门牌制作签到题,利用int转换到String就可以检验每一个字符是不是2packagetrain;publicclasstest_12{publicstaticvoidmain(String[]a......
  • 【题解】P3711 仓鼠的数学题
    poly令人晕眩,令人晕眩的poly.思路伯努利数。首先意识到有一个拉插题也是求自然数幂和,所以答案是关于\(n\)的\(k\)次多项式。考虑设出\(S_{n,k}=\sum\limits_......
  • [WC2019] 数树 题解
    关于https://codeforces.com/blog/entry/112709,我的评价是:你说得对,但是原神,后边忘了算了。[WC2019]数树神题。看到题后我的第一反应是:白云哭了。所以我也哭......
  • P5221 Product 题解
    求:\[\prod_{i=1}^n\prod_{j=1}^n\frac{lcm(i,j)}{gcd(i,j)}\(\bmod\104857601)\\1\leqn\leq1000000\]而且这个题的时限卡在200ms,空间卡在7.81MB。先推式子。\[......