E. Vus the Cossack and a Field (求一有规律矩形区域值) (有一结论待证)
2024-09-03 06:16:17
E. Vus the Cossack and a Field (求一有规律矩形区域值)
题意：给出一个原01矩阵，它按照以下规则拓展：向右和下拓展一个相同大小的 0 1 分别和原矩阵对应位置相反的矩阵，向右下拓展一个和原矩阵相同的矩阵，可以无限拓展，现给出Q个查询 问以 x1,y1,x2,y2为矩阵左上角和右下角的矩形中共有多少个一
reference :
https://blog.csdn.net/code92007/article/details/94149487
https://orzsiyuan.com/archives/Codeforces-1186E-Vus-the-Cossack-and-a-Field/
思路：要查找一个矩阵的值，可以用二维前缀和思想转化为求(1,1)到(x,y)中1的数量然后用二维前缀和得出答案。
设原矩阵为A 则逆矩阵为B A+B=nm 两个矩阵叠加起来刚好可以填满整个nm矩阵的1。所以我们考虑(1,1)到(x,y)有多少个完整的nm矩阵，先把nm矩阵的值求出来 这里要考虑nm有奇数个和偶数个也就是，(x,y)属于第几块nm矩阵，要进行分类讨论
| 1 | 1 | 2 |
|---|---|---|
| 1 | 1 | 2 |
| 4 | 4 | 3 |
这里可以看为 1 代表为完整的n*m矩形 22 ,44为不完整的这里要对1,2,4的所属块数进行分类讨论，方法相同。而3则是存在奇数的情况,需要判断其正反性，可以用前面预处理的前缀和得出
如何判断正反性
可以证明 当(bitcnt(a)+bitcnt(b))为奇数的时候是反的否则是正的，这里a,b代表所属块坐标（从0开始）（不知道怎么证）
优化解法
可以把n*m矩阵拓展成(2n)(2m)矩阵，这样就可以保证1 2,4都是偶数的快，所以1的个数为面积除以2,所以只用考虑3即可。
最新文章
- svn: 期望文件系统格式在“1”到“4”之间；发现格式“6”
- JS判断输入是否为整数的正则表达式
- Inno Setup 下载安装
- viewport ---移动端详解
- Yii源码阅读笔记（二十三）
- 初学JDBC，最简单示例
- Service知识点总结
- sql 月初和月末
- Spring - BeanPostProcessor接口（后处理器）讲解
- 图像处理------颜色梯度变化 (Color Gradient)
- 【算法】深度优先 马走日 Hamilton routes
- 【XSY3126】异或II 数学
- js获取url参数（通用方法）
- 【转】TCP和SOCKET关系
- （32）forms组件（数据校验）
- Ajax+json+jquery实现无限瀑布流布局
- VMWare Station 问题汇总
- 《机器学习实战》Logistic回归
- 深入了解oracle存储过程的优缺点
- iPhone iPad 各种控件默认高度