洛谷4492 [HAOI2018]苹果树
Luogu LOJ 分析 可以发现第 $i$ 个点有 $i$ 个位置可以插入,所以不同的树的个数为 $n!$,因此题目要求的就是所有树的答案总和。 如果只考虑一棵树,有一个经典的做法:考虑每个点父边的贡献,为两端点数之积 $sz \times (n - sz)$。 我们考虑枚举一个点 $i$ 和其子树大小 $k$,然后计算多少棵树中有这样的边。 首先,我们需要插入 $[1, i]$ 中的点,...
Luogu LOJ 分析 可以发现第 $i$ 个点有 $i$ 个位置可以插入,所以不同的树的个数为 $n!$,因此题目要求的就是所有树的答案总和。 如果只考虑一棵树,有一个经典的做法:考虑每个点父边的贡献,为两端点数之积 $sz \times (n - sz)$。 我们考虑枚举一个点 $i$ 和其子树大小 $k$,然后计算多少棵树中有这样的边。 首先,我们需要插入 $[1, i]$ 中的点,...
Luogu LOJ 分析 可以发现确保自己不死和攻击大佬是两个独立的行为。 于是我们可以先求出最多有多少天可以用来攻击大佬,只需要做一个简单的 DP 即可。设这个天数为 $t$。 考虑怼大佬的操作,我们实际上只关心能够发动它的天数以及它的伤害。于是我们可以 BFS 出所有这样的 $(d, F)$ 二元组。 接下来考虑如何能够打败一个自信值为 $c$ 的大佬。进行分类讨论: 不怼大佬,那么...
Luogu 分析 先考虑暴力怎么做。把 $[l, r]$ 中的数排序,然后维护 $lim$ 表示 $[1, lim]$ 中的数都能被表示出。假设当前加入了 $w$,那么 如果 $w > lim + 1$,则 $lim + 1$ 不能被表示出,答案即为 $lim + 1$; 否则更新 $lim$ 为 $lim + w$。 考虑优化。设上一次的 $lim$ 为 $pre$,那么只有 $...
Luogu 分析 首先题目中的集合是无序的,我们将其转为有序的来计算,只需要最后除以 $m!$ 即可。 设 $f_i$ 表示划分为 $i$ 个片段的方案数,考虑转移。 首先,如果我们已经确定了前 $i - 1$ 个片段,那么第 $i$ 个片段唯一确定,这样子的方案数为 $A_{2^n - 1}^{i - 1}$。 但是这样子会有一些不合法的情况: 第 $i$ 个片段为空:这样子去掉第 $i...
Codeforces 分析 设 $f_{i, j}$ 表示前 $i$ 个数、LIS 长度为 $j$ 时末尾元素的最小值。 考虑转移。假设当前区间为 $[l, r]$,那么 不加:$f_{i, j} \gets f_{i - 1, j}$。 对于 $f_{i - 1, j -1} < l$,有 $f_{i, j} \gets l$。 对于 $l \leq f_{i - 1, j - 1...
LOJ 分析 对于一张课桌,如果其区间被另外的课桌包含,那么它是没用的,可以去掉。那么剩下的课桌满足左右端点都递增。 对于每个班的学生,将其按身高排序,显然每两个人坐同一张课桌更优,且一定是身高小的坐 $l$ 小的桌子。 那么每对学生选择的桌子满足决策单调性,可以分治处理。在计算代价时,把所有班当前组的 $2m$ 个人拿出来按照身高排序,然后维护一个前缀和,这样子只需要二分一下就可以计算了。...
LOJ 分析 感觉和 WC2019 数树 的 $op = 1$ 基本一致,如果不会可以戳 这里。 我们还是套用 $\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义:从 $S$ 中选择一条边,再从每个连通块中选择一个点,每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。 考虑 DP。设 $f_{u, 0/1, 0/1}$ ...
HDU 分析 将问题看做平面上的游走,每步有 $a = \frac{pq}{1 - (1 - p)(1 - q)}$ 的概率移动到 $(n - 1, m - 1)$、$b = \frac{p(1 - q)}{1 - (1 - p)(1 - q)}$ 的概率移动到 $(n, m - 1)$、$c = \frac{(1 - p)q}{1 - (1 - p)(1 - q)}$ 的概率移动到 $(n...
Codeforces Luogu 分析 如果 $[l, r]$ 内不存在两个相同字符,则无解,否则答案至多为 $4$。 于是我们可以对答案进行讨论: 如果答案为 $1$,说明子串形如 $AAAA\cdots$,因此我们可以枚举 $r - l + 1$ 的约数 $d$,并判断其是否存在长度为 $d$ 的周期。 如果答案为 $2$,有三种情况:$AAB$、$ABA$、$BAA$。对于第一种和第...
Codeforces Luogu 分析 设最后得到的序列为 $\{b\}$,可以发现答案为 求出 $\prod(a_i - x)$,然后枚举其次数计算即可。时间复杂度 $\mathcal{O}(n \log^2 n)$ 甚至 $\mathcal{O}(n^2)$。 代码 // ==================================== // author: M_sea /...