1月6日 Educational DP Contest 题目链接:https://atcoder.jp/contests/dp
大部分水题就不讲了,记录几道有趣的题目。
J - Sushi
思路: 期望要倒着推!!!
设 $f_{i,j,k}$ 为有 $i$ 个 $3$ 个的寿司碟子,有 $j$ 个 $2$ 个的寿司碟子,有 $k$ 个 $1$ 个的寿司碟子的期望,那么就有 $n-i-j-k$ 个空着的碟子。然后倒着推期望!!!!
这样我们就得到了递推的关系。因为转移的顺序问题,我们不能简单地按照 $i, j, k$ 的顺序 DP。但发现转移是从寿司总数少的状态到寿司总数多到状态,因此我们要按照寿司的总数进行 DP。总时间复杂度 $O(n^3)$。
代码:
1 |
|
O - Matching
思路: 一个简单的容斥计数,感觉和 DP 关系不大。
枚举女生集合 $S$,计算所有男生和集合中女生配对的方案数,记为 $f[S]$。既然题目要求一一配对的方案,那么如果 $n-|S|$ 为奇数,那么答案就应该减去 $f[S]$,否则就加上 $f[S]$。
代码:
1 |
|
U - Grouping
思路: 一个简单的子集 DP。
枚举所有集合 $S$,记 $f[S]$ 为选取 $S$ 集合的最大答案。先算出把 $S$ 集合作为一整组的分数作为 $f[S]$ 的初值,然后枚举 $S$ 的子集 $T$,得到转移方程 $f[S]=max(f[S], f[T]+f[S xor T])$,直接转移就行。总复杂度 $O(3^nn^2)$ 代码:
1 |
|
V - Subtree
思路: 一个简单的树形 DP 加换根操作,但是有一个很有趣的细节。
设 $f_i$ 为以 $i$ 为根的子树的方案数,那么就有 DP 方程:$f_i=\prod (f_{to}+1)$。考虑换根操作,设 $val_i$ 为节点 $i$ 的父亲所在子树的贡献,那么节点 $i$ 的答案就是 $(val_i+1)*f[i]$。$val$ 的求法一般有两种,第一种是通过式子:$val_{to}=(val_x+1)*f_x/f_{to}$ 得到。这种方法看似很简单,但是其中有除法,对于模意义下的除法表面上看可以用扩展欧几里得求逆元实现。但是,有一些数是没有逆元的,也就是说对于任意除数的除法我们不能够简单地实现。
这时候我们就要考虑第二种求 $val$ 的方法,那就是给子树一个固定的顺序,然后求出子树的前缀和后缀贡献,从而推出 $val_{to}$,虽然这种方法更为复杂,但可以很好地避免除法。
代码:
1 |
|
W - Intervals
思路:
代码:
1 |
|