如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。

M_sea的博客

——どうか悔いることなく 明日へ続く道 歩いて——

洛谷4565 [CTSC2018]暴力写挂

LuoguLOJ分析题目中的式子等价于我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。代码// ===============================...

  • M_sea
  • 2020 年 08 月 01 日
  • 暂无评论

    • 洛谷5047 [Ynoi2019模拟赛]Yuno loves sqrt technology II

    Luogu分析考虑莫队，在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\log n)$ 的，由于这是 Ynoi 所以过不了。由于转移是 $\mathcal{O}(\log n)$ 的，而逆序对数又是个可减的东西，所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的，一个是区间中比 $x$ 小的数的个数，另一个是区间中比...

  • M_sea
  • 2020 年 07 月 31 日
  • 暂无评论

    • CF464E The Classic Problem

    CodeforcesLuogu分析显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。因为边权全部是 $2$ 的幂，因此考虑...

  • M_sea
  • 2020 年 07 月 31 日
  • 暂无评论

    • 洛谷4119 [Ynoi2018]未来日记

    Luogu分析先考虑没有修改怎么用分块做。一个想法是将序列分块，然后维护 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量，然而这样子查询是 $\mathcal{O}(n)$ 的。因此我们再对值域分块，并再维护 $s'_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块中的数的数量，询问时先把所求在值域的哪一块中求出来，再在这一块中求，复杂度 $\mathcal{O}(\sqrt{...

  • M_sea
  • 2020 年 07 月 31 日
  • 暂无评论

    • CF932F Escape Through Leaf

    CodeforcesLuogu分析容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑...

  • M_sea
  • 2020 年 07 月 30 日
  • 暂无评论

    • CF757G Can Bash Save the Day?

    CodeforcesLuogu分析考虑把每个询问拆成 $\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 dep...

  • M_sea
  • 2020 年 07 月 30 日
  • 暂无评论

    • ARC103F Distance Sums

    AtCoderLuogu分析不难发现 $d_i$ 最大的节点一定是叶子节点，$d_i$ 最小的节点一定是重心。考虑某个叶子节点 $u$ 的父节点 $f$ 应该满足什么。显然有 $d_v=d_f+(n-sz_u)-sz_u$ 即 $d_f=d_v+2sz_u-n$。于是我们只要随便找一个这样的 $f$ 连上去即可，如果找不到则无解。这个 $f$ 可以通过二分来找。这样子我们就可以按照 $d$ ...

  • M_sea
  • 2020 年 07 月 30 日
  • 暂无评论

    • CF1060H Sophisticated Device

    CodeforcesLuogu分析首先确定基本的计算方式则我们需要平方、减法、乘法（除以 $2$ 就是乘逆元）这三种运算。既然要造计算机，那么一定要先求出一个 $0$ 来。因为 $1+1\times(p-1)\equiv 0\pmod p$，所以可以快速乘一下。for (int i=p-1;i;>=1) { // 0 -> o[16] if (i&1) puts(...

  • M_sea
  • 2020 年 07 月 30 日
  • 暂无评论

    • LOJ535 「LibreOJ Round #6」花火

    LOJ分析如果只能用操作 $1$，根据某个经典结论答案就是逆序对数。于是很容易想到 $\mathcal{O}(n^3\log n)$ 的暴力：枚举操作 $2$ 交换了哪两个位置，然后求逆序对即可。考虑优化。因为每次只交换了两个位置，所以没有必要整个重新求一遍逆序对。假设交换了 $i$ 和 $j$，原来的逆序对数是 $A$，那么交换后的逆序对数 $A'$ 为讨论一下：当 $p_i<p_j...

  • M_sea
  • 2020 年 07 月 29 日
  • 暂无评论

    • CF543E Listening to Music

    CodeforcesLuogu分析我们要让小于 $x$ 的数最少，即让大于等于 $x$ 的数最多。那么我们可以对于每个大于等于 $x$ 的 $a_i$，将能覆盖到它的左端点的区间加上 $1$，这样子查询 $[l,r]$ 中的最大值就可以得到答案了。仍然用上面的思路，但是我们考虑用分块维护这个区间加 $1$ 区间求最大值。这个很好分块维护：对于整块，我们直接打标记即可；对于散块，我们暴力加并更...

  • M_sea
  • 2020 年 07 月 28 日
  • 暂无评论