洛谷5292 [HNOI2019]校园旅行
Luogu LOJ 分析 orz myy 可以发现，一条回文路径左右扩展一个相同字符仍然是一条回文路径。 设 $f_{u, v}$ 表示 $(u, v)$ 间是否存在一条回文路径，转移枚举出边即可。这样子是 $\mathcal{O}(m^2)$ 的。 因为我们可以在一条边上反复横跳，所以直觉上这个东西只会和奇偶性有关。 对于连接同色点的边，我们对每个连通块单独考虑：如果构成二分图，则可以只保...
M_sea 发布的文章
- 首页
- M_sea
洛谷4492 [HAOI2018]苹果树
Luogu LOJ 分析 可以发现第 $i$ 个点有 $i$ 个位置可以插入，所以不同的树的个数为 $n!$，因此题目要求的就是所有树的答案总和。 如果只考虑一棵树，有一个经典的做法：考虑每个点父边的贡献，为两端点数之积 $sz \times (n - sz)$。 我们考虑枚举一个点 $i$ 和其子树大小 $k$，然后计算多少棵树中有这样的边。 首先，我们需要插入 $[1, i]$ 中的点，...
洛谷3724 [AHOI2017/HNOI2017]大佬
Luogu LOJ 分析 可以发现确保自己不死和攻击大佬是两个独立的行为。 于是我们可以先求出最多有多少天可以用来攻击大佬，只需要做一个简单的 DP 即可。设这个天数为 $t$。 考虑怼大佬的操作，我们实际上只关心能够发动它的天数以及它的伤害。于是我们可以 BFS 出所有这样的 $(d, F)$ 二元组。 接下来考虑如何能够打败一个自信值为 $c$ 的大佬。进行分类讨论： 不怼大佬，那么...
洛谷4587 [FJOI2016]神秘数
Luogu 分析 先考虑暴力怎么做。把 $[l, r]$ 中的数排序，然后维护 $lim$ 表示 $[1, lim]$ 中的数都能被表示出。假设当前加入了 $w$，那么 如果 $w > lim + 1$，则 $lim + 1$ 不能被表示出，答案即为 $lim + 1$； 否则更新 $lim$ 为 $lim + w$。 考虑优化。设上一次的 $lim$ 为 $pre$，那么只有 $...
洛谷3214 [HNOI2011]卡农
Luogu 分析 首先题目中的集合是无序的，我们将其转为有序的来计算，只需要最后除以 $m!$ 即可。 设 $f_i$ 表示划分为 $i$ 个片段的方案数，考虑转移。 首先，如果我们已经确定了前 $i - 1$ 个片段，那么第 $i$ 个片段唯一确定，这样子的方案数为 $A_{2^n - 1}^{i - 1}$。 但是这样子会有一些不合法的情况： 第 $i$ 个片段为空：这样子去掉第 $i...
CF809D Hitchhiking in the Baltic States
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...
LOJ3192 「ROI 2019 Day2」课桌
LOJ 分析 对于一张课桌，如果其区间被另外的课桌包含，那么它是没用的，可以去掉。那么剩下的课桌满足左右端点都递增。 对于每个班的学生，将其按身高排序，显然每两个人坐同一张课桌更优，且一定是身高小的坐 $l$ 小的桌子。 那么每对学生选择的桌子满足决策单调性，可以分治处理。在计算代价时，把所有班当前组的 $2m$ 个人拿出来按照身高排序，然后维护一个前缀和，这样子只需要二分一下就可以计算了。...
LOJ3399 「2020-2021 集训队作业」Communication Network
LOJ 分析 感觉和 WC2019 数树 的 $op = 1$ 基本一致，如果不会可以戳 这里。 我们还是套用 $\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义：从 $S$ 中选择一条边，再从每个连通块中选择一个点，每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。 考虑 DP。设 $f_{u, 0/1, 0/1}$ ...
HDU6842 Battle for Wosneth2
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...
CF1043G Speckled Band
Codeforces Luogu 分析 如果 $[l, r]$ 内不存在两个相同字符，则无解，否则答案至多为 $4$。 于是我们可以对答案进行讨论： 如果答案为 $1$，说明子串形如 $AAAA\cdots$，因此我们可以枚举 $r - l + 1$ 的约数 $d$，并判断其是否存在长度为 $d$ 的周期。 如果答案为 $2$，有三种情况：$AAB$、$ABA$、$BAA$。对于第一种和第...