洛谷4587 [FJOI2016]神秘数
Luogu 分析 先考虑暴力怎么做。把 $[l, r]$ 中的数排序，然后维护 $lim$ 表示 $[1, lim]$ 中的数都能被表示出。假设当前加入了 $w$，那么 如果 $w > lim + 1$，则 $lim + 1$ 不能被表示出，答案即为 $lim + 1$； 否则更新 $lim$ 为 $lim + w$。 考虑优化。设上一次的 $lim$ 为 $pre$，那么只有 $...
如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
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 /...
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$ 也是好求的，只需要维护二维前缀和即...