BZOJ3162:独钓寒江雪 – 题解

主要思路

刚看这题我人都是懵的…仔细看了看能大概想到,定一个根然后做 DP 得到方案,然后对于相同形态的子树进行方案分配即可。(但是不会写)

具体而言,转换成有根树的方法就是用重心来做根(如果有两个重心的话,就加一个虚根),并且每次 DFS 完之后用 Hash 值排序,然后进行分组转移。

转移的时候,可以给每一种情况进行标号,然后用前缀的组合意义来做转移即可。具体:\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。

如果加了虚点,那就判一下就好了。

继续阅读BZOJ3162:独钓寒江雪 – 题解

AtCoder Regular Contest 099:E~F – 题解

E – Independence

这道题直接去想性质不好想,因为贪心的话、找到两个大小相近的团没什么性质。我们可以考虑建一张反图。如果这是个二分图,那么左右部恰好可以作为题中的两个 state。然而,意识到并不保证是一张连通的二分图,所以我们可以用一些连通块来拼成两个 state。那么,我们可以用个背包搞搞,再最后算算答案即可。(就不需要贪心的构造两个大小相近的团了,全部都算一遍即可)。

继续阅读AtCoder Regular Contest 099:E~F – 题解

「国家集训队 2011 扬天」解题报告

A – 等差子序列

因为是个排列,读入时我们可以把已有的数值放在数轴上,发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组,维护串和反串的哈希然后判断即可。

继续阅读「国家集训队 2011 扬天」解题报告