HNOI2015 题解

Day1

亚瑟王 arthur

神奇的概率DP
由期望可加,所以所求期望可以转化为一张牌的出现概率。
表示处理到第i张卡片目前剩余机会为j的概率。转移方程如下:

接水果 fruit

画个图就能分析出本题实质是询问包含一个点的第K小矩阵,这个可以差分+树状数组套权值线段树解决。
注意加点时,使得区间范围相对较小的一维放在前面

菜肴制作 dishes

反图最大拓扑序。有点类似NOI2010的那道拓扑序。
要标号小的尽可能出现在前面可以转化成标号大的尽可能晚的出现在后面。所以可以用逆拓扑序贪心。

Day2

落忆枫音 maple

可以脑补出DAG树形图个数为根节点外各节点入度乘积。
这题我们考虑算不合法的个数。不合法则必定带环,而环一定是从新加的那条边产生,所以转化为存在一条T->S的路径。而我们发现环的存在并不会影响不在环上的点构成的生成树的数量,所以这个环的贡献就是所有非环节点入度乘积,由于模是质数,我们就可以计算环上所有点入度积的逆元。那如何快速计算所有环的贡献呢?按照拓扑序DP,表示处理到第i个节点的所有路径乘积逆元和,按DAG转移即可。注意我们当且仅当时赋初值。时间复杂度

幻想乡开店 shop

点分治貌似可做?
递归建立点分治树,记录下所有子孙的年龄与距离,排序后将距离求前缀和。每次询问的时候,一个节点往分治树上跳,同时二分查询满足条件距离和计入贡献。
时间复杂度
坑点: 构建分治树时遍历子树的边表是以root开始,而不是x开始。

实验比较 pairwise

题目有几个比较重要的条件:
1) 每个点只有一条出边
2) 等级相同无序
条件(1)告诉我们这是一棵森林,条件(2)告诉我们可以只需要考虑被'<'分成的段数。有DP状态表示i节点的子树被'<'分成j段的方案数。

不同子树相互之间是没有影响的,所以考虑合并大小为的两棵子树,假设分别分成了段,那么合并后假设分为段,且每块至少有之前子树的一段,且相同子树的任意两段都不能在相同段中。这个的方案数为

所以状态转移方程如下: