CF464E The Classic Problem
Codeforces Luogu 分析 显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。 因为边权全部是 $2$ 的幂，...
M_sea 发布的文章
- 首页
- M_sea
洛谷4119 [Ynoi2018]未来日记
Luogu 分析 先考虑没有修改怎么用分块做。 一个想法是将序列分块，然后维护 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量，然而这样子查询是 $\mathcal{O}(n)$ 的。 因此我们再对值域分块，并再维护 $s'_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块中的数的数量，询问时先把所求在值域的哪一块中求出来，再在这一块中求，复杂度 $\mathcal{O}(\s...
CF932F Escape Through Leaf
Codeforces Luogu 分析 容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。...
CF757G Can Bash Save the Day?
Codeforces Luogu 分析 考虑把每个询问拆成 $\sum_{i=1}^r\operatorname{dis}(p_i,u)-\sum_{i=1}^{l-1}\operatorname{dis}(p_i,u)$。 我们考虑怎么求 $\sum_{i=1}^t\operatorname{dis}(p_i,u)$，这个东西可以拆成 $t\times dep_u+\sum_{i=1}^t...
ARC103F Distance Sums
AtCoder Luogu 分析 不难发现 $d_i$ 最大的节点一定是叶子节点，$d_i$ 最小的节点一定是重心。 考虑某个叶子节点 $u$ 的父节点 $f$ 应该满足什么。显然有 $d_v=d_f+(n-sz_u)-sz_u$ 即 $d_f=d_v+2sz_u-n$。于是我们只要随便找一个这样的 $f$ 连上去即可，如果找不到则无解。这个 $f$ 可以通过二分来找。 这样子我们就可以按照...
CF1060H Sophisticated Device
Codeforces Luogu 分析 首先确定基本的计算方式 则我们需要平方、减法、乘法（除以 $2$ 就是乘逆元）这三种运算。 既然要造计算机，那么一定要先求出一个 $0$ 来。因为 $1+1\times(p-1)\equiv 0\pmod p$，所以可以快速乘一下。 for (int i=p-1;i;>=1) { // 0 -> o[16] if (i&1...
LOJ535 「LibreOJ Round #6」花火
LOJ 分析 如果只能用操作 $1$，根据某个经典结论答案就是逆序对数。于是很容易想到 $\mathcal{O}(n^3\log n)$ 的暴力：枚举操作 $2$ 交换了哪两个位置，然后求逆序对即可。 考虑优化。因为每次只交换了两个位置，所以没有必要整个重新求一遍逆序对。假设交换了 $i$ 和 $j$，原来的逆序对数是 $A$，那么交换后的逆序对数 $A'$ 为 讨论一下：当 $p_i&l...
CF543E Listening to Music
Codeforces Luogu 分析 我们要让小于 $x$ 的数最少，即让大于等于 $x$ 的数最多。 那么我们可以对于每个大于等于 $x$ 的 $a_i$，将能覆盖到它的左端点的区间加上 $1$，这样子查询 $[l,r]$ 中的最大值就可以得到答案了。 仍然用上面的思路，但是我们考虑用分块维护这个区间加 $1$ 区间求最大值。 这个很好分块维护：对于整块，我们直接打标记即可；对于散块，我...
洛谷5471 [NOI2019]弹跳
Luogu 分析 首先容易看出一个暴力，即每个点向能到达的点连边，然后最短路即可。 然而边数是 $\mathcal{O}(n^2)$ 级别的，我们需要优化连边。由于是向矩形范围内的点连边，所以考虑 KD-Tree 优化连边。 对于城市 $u$ 向矩形连的边，我们在 KD-Tree 上遍历：如果当前节点范围包含在矩形内，则 $u$ 直接向这个节点连边；如果当前节点范围与矩形无交，则直接返回；否...
洛谷4117 [Ynoi2018]五彩斑斓的世界
Luogu 分析 考虑分块。 对于每一块，维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的，因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式 如果 $2x\geq mx$，则直接将所有 $>x$ 的数减去 $mx$。这样...