冒泡ioa
冒泡ioa

[GZ/GXOI2019]与或和(单调栈)

题目链接

题解

看到这个首发平台就觉得是rainbowcat出的题,一看题面——都有Freda了,就确定是rainbowcat出的了。

这一题第一次写我写挂了orz

由于与运算和或运算在每一位上都是独立的,我们可以考虑对每一位进行计算。

我们先考虑与运算(其实两个运算是一样的)
于是就成了一个求一个矩阵中,有多少个0/1子矩阵,我们可以考虑用单调栈做。

有一个显然的结论

在一个 N\times M 的矩阵中,以(n,m)为右下角的子矩阵共有 N\times M

具体来讲,我们要求出一个s二维数组,s[i][j]表示(i,j)点上方有多少个连续的1,O(N^2)预处理

枚举每一个点,我们来计算以它为右下角的子矩阵个数,观察如下矩阵:

假设我们现在统计到(3,3),可以发现它的贡献=(3,2)处贡献+s[3][3] (与前面的组合+该列的组合)

但是,如果是这样一个矩阵:

(3,3)处的贡献=(3,2)处的贡献+s[3][3]-1 (1为非法矩阵的数目)

对于一般情况,在2处,A区域就没有意义,4处,B区域就没有意义

http://bubbleioa.top/wp-content/uploads/2019/04/andor1.png

所以我们要维护一个单调栈,栈中元素k要满足s[i][k]单调递增(栈顶s[i][k]最大)

每次有元素出栈时,说明有部分答案不能产生贡献,见代码注释

对于或运算,求所有0子矩阵,全集-0子矩阵数目即是贡献。

代码

发表评论

textsms
account_circle
email

冒泡ioa

[GZ/GXOI2019]与或和(单调栈)
题目链接 题解 看到这个首发平台就觉得是rainbowcat出的题,一看题面——都有Freda了,就确定是rainbowcat出的了。 这一题第一次写我写挂了orz 由于与运算和或运算在每一位上都是独立…
扫描二维码继续阅读
2019-04-16