CF888G Xor-MST
Codeforces 分析 这种奇奇怪怪的生成树题考虑 Boruvka 算法。其核心思想是对每个连通块找到最近的连通块，然后合并。 对于这道题，我们考虑把所有数插入到一棵 Trie 中，那么对于每个节点，其左子树和右子树中必定只由一条边相连。这是因为在执行 Boruvka 算法的过程中，必定是左右子树先分别连通，然后再通过一条边合并在一起。 那么我们只需要知道两个数组间两两异或的最小值，将一...
M_sea 发布的文章
- 首页
- M_sea
CF1007E Mini Metro
Codeforces 分析 orz yhx 为了方便我们在最后加一个 $a_i = N, b_i = N, c_i = +\infty$ 的站台，其中 $N$ 是一个很大的数。这样子我们可以保证每辆火车恰好送走 $k$ 个人。 设 $f_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ 时刻最少需要放多少辆火车，$g_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ ...
洛谷5617 [MtOI2019]不可视境界线
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$ 个圆...
洛谷5292 [HNOI2019]校园旅行
Luogu LOJ 分析 orz myy 可以发现，一条回文路径左右扩展一个相同字符仍然是一条回文路径。 设 $f_{u, v}$ 表示 $(u, v)$ 间是否存在一条回文路径，转移枚举出边即可。这样子是 $\mathcal{O}(m^2)$ 的。 因为我们可以在一条边上反复横跳，所以直觉上这个东西只会和奇偶性有关。 对于连接同色点的边，我们对每个连通块单独考虑：如果构成二分图，则可以只保...
洛谷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$ 个人拿出来按照身高排序，然后维护一个前缀和，这样子只需要二分一下就可以计算了。...