文档章节

AGC041F Histogram Rooks

o
 osc_ho8dcqsx
发布于 07/01 14:49
字数 1413
阅读 29
收藏 0

精选30+云产品,助力企业轻松上云!>>>

有生之年自己做出了一个 AGC F 还踩了标算,但是好像在我之前已经有人踩过标算了,再鞭尸一波也无可厚非 hhh


看到“全部被覆盖” 条件感觉不好做,考虑容斥,即选择若干个位置强制它们不被覆盖,那么会有位置不能放车,而其余的位置可以选择放或者不放,方案数可以计算。但暴力枚举不优秀。在后文中为了描述方便定义行连续段表示的是某一行中不包含被删掉的格子的极长格子段,列连续段同理。

注意到这个网格的行并不连续(即对于某个确定的行,其行连续段可能有多个),但列是连续的(即第 \(i\) 列只有 \(1 \sim h_i\) 这一个列连续段)。那么如果确定了某些列上存在格子没有覆盖,那么这些列上的所有格子一定不能放车。

考虑枚举存在位置没有覆盖的列的集合 \(S\),那么这些列的所有格子就默认全部不能放车。此时对于每个行连续段,假设它的段长为 \(len\)、有 \(p\) 个位置所在的列是存在位置没有覆盖的列,考虑两种情况:

  • 在这个行上没有选择任何位置不覆盖,此时剩余的 \(len-p\) 个位置都可以选择放车或者不放车,故贡献为 \(2^{len-p}\)
  • 在这个行上存在位置选择不覆盖,此时这一个行的放车方案数为 \(1\),因为没有位置能够放车。枚举有多少个位置放了车,乘上容斥系数贡献是 \(\sum\limits_{j=1}^p (-1)^j \binom{p}{j}\)

那么这一个行连续段对答案的贡献就是 \(2^{len-p} + \sum\limits_{j=1}^p (-1)^j \binom{p}{j}\)。注意到 \(\sum\limits_{j=1}^p (-1)^j \binom{p}{j} = -[p \neq 0]\),可以改写贡献为 \(2^{len-p} - [p \neq 0]\)。最后将所有贡献的答案乘起来。


然而上面的做法在正确性上存在问题,因为无法确定强制选择了位置没有覆盖的列在方案中是否选择了格子不覆盖,如果存在某一个存在格子没有覆盖的列没有格子选择不覆盖,那么这个方案的贡献不应该算入。

继续考虑容斥,在枚举集合 \(S\) 的基础上枚举强制在最后的选择方案中不存在格子选择不覆盖的列的子集 \(T\) ,容斥系数是 \((-1)^{|T|}\)

这样某个行连续段中如果存在 \(p\) 个位置所在的列在集合 \(S\) 中,有 \(q\) 个位置所在的列在集合 \(T\) 中,方案数将变为 \(2^{len-p} - [p \neq q]\)。值得注意的是虽然集合 \(T\) 对应的列集合不存在任何格子选择不覆盖,但是仍然需要认为这些列的所有格子无法放置,否则无法达到容斥效果。

这样就可以正确地算出答案了。


这玩意显然太慢。为了优化可以注意到以下若干性质:

  • 计算某个行连续段的贡献只关心两个量:\(p\)\([p \neq q]\)
  • \(p \geq q\),所以 \([p \neq q] = [p - q > 0]\)
  • 对于左端点所在列相同、右端点所在列相同的两个行连续段,它们的贡献一定相同。把所有这样的行连续段看成一个集合,那么这样的集合最多只有 \(N\) 个,而且一个集合内所有行连续段的所在行一定是连续的若干行。

简单来说看一张图就好,下面这个图里相同颜色的所有行连续段的贡献显然是相同的,可以一起计算,且可以简单证明这样的颜色数量至多为 \(N\)

2020-04-01 12-08-24屏幕截图.png

找这样的矩形只需要在初始图中找到 \(h\) 最小的若干列,再通过这些列将原图划分为若干个子部分,每个部分递归处理。

而且还可以发现一个事情:

上图中对于红色的行,其覆盖的所有列中在集合 \(S\) 中的列的数量 = 浅绿色覆盖的所有列中在集合 \(S\) 中的列的数量 + 蓝色覆盖的所有列中在集合 \(S\) 中的列的数量 + 第 4 列是否在集合 \(S\) 中。

这是一个类似于子问题的结构,也就是说某种颜色覆盖的列的数量等于其正上方所有其他颜色矩形覆盖的列的数量加上其独有的数量。

(注:这里的正上方指的是在上方而且存在重合的边界)


给每一个矩形一个标号,并认为如果矩形 \(A\) 在矩形 \(B\) 的正上方则 \(A\)\(B\) 的儿子。

设计一个 DP:\(f_{i,j,0/1}\) 表示在 \(i\) 号矩形中,其覆盖的列有 \(j\) 列在集合 \(S\) 中,且是否存在某一列在集合 \(S\) 却不在集合 \(T\) 中,在这样的情况下所有方案中这个矩形和在它上方的所有矩形的方案数的总和。转移先从儿子处将该数组合并,再考虑其独有的若干列的选择,最后乘上每行如何放车的系数。因为每行的方案一致所以复杂度可以做到 \(O(N^2 \log N)\),而所有可能的转移系数只有 \(O(N)\) 种,通过预处理可以将复杂度优化为 \(O(N^2)\)

o
粉丝 0
博文 35
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

DateTime2与SQL Server中的DateTime - DateTime2 vs DateTime in SQL Server

问题: Which one: 哪一个: datetime datetime2 is the recommended way to store date and time in SQL Server 2008+? 是在SQL Server 2008+中存储日期和时间的推荐方法吗? I'm aware of......

富含淀粉
今天
13
0
Linux 文件打开过多 (Too many open files)

如图是程序运行了一段时间后抛出来的一个bug, 刚开始看这个bug的时候各种网上找答案, 无外乎教你怎么改ulimit(就是linux最大打开文件数), 当然不是说改这个没有用, 作为程序开发者来说, 如果...

onedotdot
今天
25
0
ZStack实践汇|ZStack与行云管家对接实践ZStack与行云管家对接实践

一、ZStack与行云管家概述 大道至简·极速部署,ZStack致力于产品化私有云和混合云。 ZStack是一家坚持自主创新、专注产品化的云计算公司,以“降低企业上云门槛、让每一家企业都拥有自己的云...

ZStack社区版
今天
7
0
switch linux mint 20 apt repository to tsinghua' mirrors

edit file /etc/apt/sources.list.d/cat official-package-repositories.list lwk@qwfys:/etc/apt/sources.list.d$ lltotal 12drwxr-xr-x 2 root root 4096 Jul 5 20:01 ./drwxr-xr-x 7 ......

qwfys
今天
12
0
面试系列之C++的对象布局【建议收藏】

我们都知道C++多态是通过虚函数表来实现的,那具体是什么样的大家清楚吗?开篇依旧提出来几个问题: 普通类对象是什么布局? 带虚函数的类对象是什么布局? 单继承下不含有覆盖函数的类对象是...

伊牙牙嘿哈哈
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部