CF1534F2 Falling Sand (Hard Version)
个人思路:
每个点向相邻沙子连边,向本列和相邻 \(2\) 列下方第一个沙子连边。
对于一个 DAG,所有入度为 \(0\) 的点会覆盖全部点。我们缩点即可通过 F1。
但是这样做是过不了 F2 的。
我们发现一个沙子下落,其下面的所有沙子都会下落,也就是说,第 \(i\) 列从下往上第 \(a_i\) 个沙子一定会直接或间接下落。
我们维护每行取最上方的沙子,它一定能覆盖一个连续的区间。因为每行只能让相邻两列下落,不可能不连续。
那么我们只需要求出每列最高点的覆盖区间,这个问题就转化为了区间覆盖问题。
先求区间。
我们对每个点计算相邻两列不比这个点高的最高点的位置,对其建边。这可以通过从低往高枚举每一行实现。
我们从每列最高点分别向两边搜索,不断沿边走,到达一个点后不断往上走直到上方相邻的点没沙子。以左边为例,在第 \(i\) 列小于 \(a_i\) 时,停止搜索,此时区间左端点就是 \(i+1\)。
然后区间覆盖,比较简单。
我们维护下标 \(now\) 与 \(R\),表示当前覆盖了 \([1,now]\),已有线段中可以覆盖到 \(R\)。到一个节点时,用以该节点为左端点的线段更新 \(R\),如果这个点没有被覆盖,\(now \leftarrow R\),表示直接覆盖到 \(R\)。
上述算法假了,hack 如下:
6 8
#.#..##.
..####..
..#..###
..##.##.
.#.####.
####.#..
1 2 2 3 1 5 2 1
显然可以在第 \(4\) 列走回第 \(3\) 列,第 \(1\) 列即可覆盖所有。
必须 dfs。与 F1 类似,向本列和相邻 \(2\) 列下方第一个沙子连边,然后暴力沿边搜索。
最坏情况下每个点走一遍全图,直接寄。
然后就不会了。
正解:
上述算法是假的,一个点覆盖区间连续的结论是错误的,例如 test #\(5\)。
但是我们发现可以覆盖一个点的列是连续的区间,因为如果某一列最高点不能覆盖到一个点,整列的点都不能覆盖到这个点,而外面的列需要通过这一列,也覆盖不到。我们可以通过 dfs 计算每个点的区间左端点和右端点。
我们从左到右枚举每列最高的位置,从这里进行搜索,搜到的点的区间左端点为当前枚举到的列。我们不搜已经搜过的点,因为是从左往右搜,先搜到的一定比后搜到的更优。
题目转化为若干个限制条件 \([l_i,r_i]\) 表示区间内的数至少选一个。
我们贪心选点。假设我们上一个选点位置 \(pre\),这一次选点位置 \(p\) 应当满足:
- \(p\) 最右可以选到所有 \(l_i > pre\) 的限制中 \(r_i\) 的最小值,否则不满足限制。
- \(p\) 选的越靠右越好,因为剩下的限制更少,接下来选点数更少。
发现每次直接选所有 \(l_i > pre\) 的限制中 \(r_i\) 最小值,可以对每个位置预处理得到。
这道题虽然正解是建图 \(+\) 缩点 \(+\) dp \(+\) 贪心的难度为 \(3000\) 的题,却可以简单的搜索。
一定要扔进校内模拟赛。
最新文章
- Markdown 语法总结
- sacc scss less
- Nice Sequence_线段树***
- 【Machine Learning】机器学习の特征
- php获取当前时间和转换格式
- EJB--事务管理 .
- ldap
- 函数hash_get_nth_cell
- OC3_MyRect
- POJ1384完全背包问题
- hdu 2211
- JAVA基础编程50题(10-12题)具体解释
- 【Python中if __name__ == '__main__': 的解析】
- 使用PowerApps快速构建基于主题的轻业务应用 —— 入门篇
- linux下查看系统属性
- 内置函数 -- filter 和 map
- :after/:before使用技巧
- 每个 Python 程序员都要知道的日志实践
- mysql 定期删除表中无用数据
- 无法新建EXCLE