[HDU5977]Garden of Eden(点分治,高维前缀和)

发布于 2018-02-22  396 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5977]Garden of Eden(点分治,高维前缀和)

Description

When God made the first man, he put him on a beautiful garden, the Garden of Eden. Here Adam lived with all animals. God gave Adam eternal life. But Adam was lonely in the garden, so God made Eve. When Adam was asleep one night, God took a rib from him and made Eve beside him. God said to them, “here in the Garden, you can do everything, but you cannot eat apples from the tree of knowledge.”
One day, Satan came to the garden. He changed into a snake and went to live in the tree of knowledge. When Eve came near the tree someday, the snake called her. He gave her an apple and persuaded her to eat it. Eve took a bite, and then she took the apple to Adam. And Adam ate it, too. Finally, they were driven out by God and began a hard journey of life.
The above is the story we are familiar with. But we imagine that Satan love knowledge more than doing bad things. In Garden of Eden, the tree of knowledge has n apples, and there are k varieties of apples on the tree. Satan wants to eat all kinds of apple to gets all kinds of knowledge.So he chooses a starting point in the tree,and starts walking along the edges of tree,and finally stops at a point in the tree(starting point and end point may be same).The same point can only be passed once.He wants to know how many different kinds of schemes he can choose to eat all kinds of apple. Two schemes are different when their starting points are different or ending points are different.

Http

HDU

Tag

点分治,高维前缀和,状态压缩

题目大意

给出一棵树,这棵树上的每一个点有一个类别,求经过每一种类别的点至少一次的路径条数。

解决思路

点分治求解。考虑到\(K\)即种类数的范围只有\(10\),所以可以对每一个点维护一个二进制状态表示它到当前点分治的根的路径上经过的点的种类集合。每一次计算出当前根的答案再减去不经过当前根的答案即可,递归求解。
这题的关键在于如何计算每一次的答案。一个点到根的路径上的点种类集合这个比较好求,直接\(bfs\)即可,关键是如何组合出经过所有类别的路径。根据题意我们可以得到一个计算公式。
记\(nowAns\)表示这一次的答案,\(nown\)表示这一次遍历的点的数量,\(Path[u]\)表示\(u\)这个点到当前根的路径上的点类型的集合,\(Cnt[S]\)表示到根的路径上点类型的集合为\(S\)的点有多少个,那么有
\[nowAns=\sum_{i=1}^{nown} \sum_{S|Path[i]==(1 < < K)-1} Cnt[S]\]
那么现在的问题就是如何统计一个集合\(S\)的超集之和。(超集,比如对于F[0101],超集之和为F[0101]+F[1101]+F[0111]+F[1111])。
这个可以用高维前缀和解决,具体来说可以这样求

正确性暂不会证。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5977]Garden of Eden(点分治,高维前缀和)


HNCJ OIer