Loading...
博主已经退役,评论可能会审核很久才能通过。
Luogu 分析 首先考虑给你两个圆怎么算交的面积。 设两圆心距离为 $d$,可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$,然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$,因此交面积为 $(\theta - \sin\theta)r^2$。 考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆...
Luogu LOJ 分析 orz myy 可以发现,一条回文路径左右扩展一个相同字符仍然是一条回文路径。 设 $f_{u, v}$ 表示 $(u, v)$ 间是否存在一条回文路径,转移枚举出边即可。这样子是 $\mathcal{O}(m^2)$ 的。 因为我们可以在一条边上反复横跳,所以直觉上这个东西只会和奇偶性有关。 对于连接同色点的边,我们对每个连通块单独考虑:如果构成二分图,则可以只保...
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...