洛谷5768 [CQOI2016]路由表
Luogu LOJ 分析 因为 IP 地址可以看做长度为 $32$ 的二进制串，所以可以考虑用 Trie 树维护。 考虑查询。可以发现一个 IP 地址的匹配最大明确度是单增的，因此求出链上修改时间的单调栈即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-b...
分类 题解 下的文章
- 首页
- 题解
洛谷4565 [CTSC2018]暴力写挂
Luogu LOJ 分析 题目中的式子等价于 我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。 虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。 代码 // =======================...
洛谷5047 [Ynoi2019模拟赛]Yuno loves sqrt technology II
Luogu 分析 考虑莫队，在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\sqrt{n}\log n)$ 的，由于这是 Ynoi 所以过不了。 由于转移是 $\mathcal{O}(\log n)$ 的，而逆序对数又是个可减的东西，所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的，一个是区间中比 $x$ 小的数的...
CF464E The Classic Problem
Codeforces Luogu 分析 显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。 因为边权全部是 $2$ 的幂，...
洛谷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...