LOJ3192 「ROI 2019 Day2」课桌
LOJ 分析 对于一张课桌，如果其区间被另外的课桌包含，那么它是没用的，可以去掉。那么剩下的课桌满足左右端点都递增。 对于每个班的学生，将其按身高排序，显然每两个人坐同一张课桌更优，且一定是身高小的坐 $l$ 小的桌子。 那么每对学生选择的桌子满足决策单调性，可以分治处理。在计算代价时，把所有班当前组的 $2m$ 个人拿出来按照身高排序，然后维护一个前缀和，这样子只需要二分一下就可以计算了。...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
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 /...
Luogu 分析 考虑拆掉绝对值。对于一个数 $i$，如果它左右两边都比它小则其贡献为 $-2i$，如果一边比它小一边比它大则其贡献为 $0$，如果两边都比它大则其贡献为 $2i$。 考虑从小到大插入所有数。设 $f_{i, j, k, l}$ 表示插入了 $1 \sim i$，形成了 $j$ 个连续段，$1 \sim n$ 的贡献之和为 $k$，有 $l$ 个边界已经放了数的方案数。 这里...
Luogu 分析 如果我们在相邻的两个相同字符间连一条边，可以发现得到的图为平面图。 对于平面图，我们有欧拉公式 其中 $F$ 为区域数（无界域也算一个区域）、$V$ 为点数、$E$ 为边数、$C$ 为连通块数。 于是我们可以想办法求出 $F, V, E$。 $V$ 是好求的，即为 $(x_2 - x_1 + 1)(y_2 - y_1 + 1)$；$E$ 也是好求的，只需要维护二维前缀和即...
牛客 分析 设 $X$ 为小 C 的排名，$Y$ 为题目条件。 那么 随便用什么方法算自然数幂和即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #inc...
Luogu LOJ orz laofu！!1 分析 $op = 0$ 只需要统计两棵树有多少条重边即可。假设有 $c$ 条，答案即为 $y^{n - c}$。 $op = 1$ 先特判掉 $y = 1$ 的情况，答案为 $n^{n - 2}$。 我们要求的是 考察每个连通分量。一个大小为 $a$ 的连通分量会产生 $\frac{n^2 y}{1 - y} a^2$ 的乘积贡献，而 $a$...
Codeforces Luogu 分析 考虑对于每一件 T-shirt 计算其贡献。下面设当前考虑的 T-shirt 为 $k$。 设 $f_{i, j}$ 表示前 $i$ 个人，有 $j$ 人适合大小为 $k$ 的 T-shirt 的概率，转移为 是单减的。 因此我们可以每次贪心地找一个 $\Delta g$ 最大的 T-shirt 大小出来。 实现时，我们先求出对每个 T-shirt ...