[小清新] [并查集] [计数问题] P6008 [USACO20JAN] Cave Paintings P

· · 个人记录

被比赛创死后做几道小清新题目令人舒适。

最好先自己想想，看了题解就没意思了。

题目传送门

思路

显然需要从底往上计数，首先抽出每一层并对空格进行染色，接下来考虑每个块之间的联系。

初始思路：块之间的关系类似树，可以建树后处理。

假若 i 层的水不能扩散到同层的其它块，那么这无疑是个很好的思路。

但由题意，上述假设不成立，同层的块若连通则会相互影响。连通性问题，可以考虑并查集，在合并过程中计数是可行的。

连通问题解决了，但是怎么维护方案数呢？我们可以拆开两部分计数。

假设在 i 层。对于一个连通块，“不在 i 层注水” 方案数应当是 i-1 层的块的方案数相乘，因为满足乘法原理。

最后，“在 i 层注水” 方案数就是 1。

然后答案是所有连通块的方案数相乘。

提交记录