HNOI2015解题报告
Author: Pengyihao
Day1 T1 亚瑟王
思路
用 \(f[i][j]\) 表示 \(i\) 一共获得了 \(j\) 次“机会”的概率。
注意这里的“机会”，是指有多少轮中，它前面的所有卡牌，要么在之前的轮中发动过，要么在这一轮中因为运气没有发动。
这里的“机会”不与自己有没有发动相关。所以就算在之前某轮中发动过，这一轮轮到它的时候贡献依然要增加。
于是有 \(f[i][j] = f[i-1][j+1]\cdot (1-(1-p[i-1])^j) + f[i-1][j]\cdot (1-p[i-1])^j\)
\(ans = \sum_{i=1}^n\sum_{j=1}^rf[i][j]\cdot d[i]\cdot (1-(1-p[i])^j)\)
代码
|
|
Day1 T2 接水果
思路
首先，我们求出每个点的dfs序。
然后对于一条x<–>y的路径，如果有路径包含它，那么有
如果 \(lca(x,y)=x or y\)，那么只需要这条路径的一个端点在深度大的点的子树中，另一个端点不在“深度小的点往深度大的点的方向上的第一个点”的子树中即可。
否则，那么只需要这条路径的两个端点分别在 \(x\) 和 \(y\) 的子树中即可。
我们令这条包含x<–>y的路径的两个端点中dfs序小的点为 \(a\)，dfs序大的点为 \(b\)。
对于上面两种情况中的任意一种情况，这种情况中 \(a\) 和 \(b\) 所在的子树互不相交，为两个不相交的dfs序区间（不在子树中的情况我们可以转化为在它的补集的区间的情况）。
于是我们就把问题转化为了，每个盘子对应一对（或两对，因为有“不在子树”）区间，然后对于每个水果的两个点，两个区间分别包含其两个点的盘子中，权值第 \(k\) 小的。
我们可以把一维转化成 \(x\) 坐标，另一维转化成 \(y\) 坐标，于是问题就转化为了包含一个点的矩形中第 \(k\) 小的。
于是可以用扫描线+树状数组套主席树解决。
代码
|
|
Day1 T3 菜肴制作
思路
按照逆序拓扑排序，然后构造字典序最大的解。
代码
|
|
Day2 T1 落忆枫音
思路
考虑没有环的情况。
每个点（除了 \(1\) 号点）任选一条入边，则构成一棵脉络树。
所有方案数为 \(\prod_{i=2}^ndegree[i]\)
但是有环，所以答案要减去它。
设 \(S\) 为 \(y\) 到 \(x\) 的路径。
\(remove=\sum_{S}\prod_{i=2}^n[i\notin S]degree[i]\)
这个可以dp……
令 \(f[i]\) 为 \(i\) 到 \(x\) 的路径求出的remove。
则 \(f[i] = \sum_{j->i}f[j]/degree[i]\)
代码
|
|
Day2 T2
这是一道动态点分治的题目。但因为我还没有搞这个专题所以暂且跳过。
Day2 T3
思路
这个题目还是很容易的。
因为所有的 \(x\) 互不相同， 所以可以把大小关系看作是图论中的边。
那么构成的就是一座森林（把相等的点用并差集缩起来）。
然后就可以树形dp辣！
因为有等于，所以我们不知道每棵子树中有多少“块”元素。
我们把相等的元素看成一块，那么一棵子树就是若干个块的大小关系。
我们设第 \(i\) 个点的子树中有 \(j\) 个块的方案数为 \(f[i][j]\)。
则两棵子树合并的结果 \(g[i]\) 为
\[g[i]=\sum_{j=1}^n\sum_{k=1}^n[max(j, k)\leq i\leq j+k]f[son1][j]\cdot f[son2][j]\cdot \binom{i}{j}\binom{j}{j+k-i}\]
代码
|
|