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

M_sea的博客

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

洛谷1861 星之器

Luogu分析手玩一下可以发现，无论怎么移动，最后得到的总魔力值总是相同的。然后就不会了。看题解后想到，对于某颗在 $(x,y)$ 位置的星，定义它的势能为 $\frac{x^2+y^2}{2}$。可以发现，当你驱动了 $(x,y_1)$ 和 $(x,y_2)$ 后，原来两者的势能之和为 $\frac{x^2+y_1^2+x^2+y_2^2}{2}$，驱动后两者的势能之和为 $\frac{x...

  • M_sea
  • 2020 年 02 月 26 日
  • 暂无评论

    • 洛谷4631 [APIO2018] Circle selection 选圆圈

    LuoguLOJ分析暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。考虑用 KD-Tree 优化模拟过程。我们把每个圆看作它的外接矩形，然后对于当前删去的圆在 KD-Tree 上递归，如果圆与矩形没有交则不会更新，可以直接返回。然后建树时按方差选维度就可以过了。代码// =================================== // author: ...

  • M_sea
  • 2020 年 02 月 21 日
  • 暂无评论

    • 洛谷4357 [CQOI2016]K远点对

    LuoguLOJ分析暴力就是维护一个大小为 $k$ 的小根堆，然后 $\mathcal{O}(n^2)$ 枚举。考虑用 KD-Tree 优化。对于每个点在 KD-Tree 上递归，如果当当前矩形的最大距离比堆顶小则不可能更新答案，可以直接返回。因为是每对点算了两遍所以堆的大小应为 $2k$，为了方便可以先插 $2k$ 个 $0$ 进去。代码// =======================...

  • M_sea
  • 2020 年 02 月 21 日
  • 暂无评论

    • 洛谷4148 简单题

    Luogu分析还是 KD-Tree 板子。插入时利用替罪羊树重构那一套保证平衡。查询时判断查询矩形和当前矩形是否有交，如果完全包含直接返回当前矩形和，部分包含就递归下去，否则返回 $0$。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ===...

  • M_sea
  • 2020 年 02 月 20 日
  • 暂无评论

    • 洛谷4169 [Violet]天使玩偶/SJY摆棋子

    Luogu分析KD-Tree 板子。插入时可能会让 KDT 不平衡，用类似于替罪羊树的方式定期重构即可。查询时利用到矩形的最短距离剪枝。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =============================...

  • M_sea
  • 2020 年 02 月 19 日
  • 暂无评论

    • LOJ6053 简单的函数

    LOJ分析注意到不妨假装 $f(2)=1$，于是就可以 Min_25 筛了。考虑到在 Min_25 筛的第二步即求 $S(n,j)$ 时，如果 $j=1$ 则质数部分算了 $2$ 的贡献，直接加上 $2$ 即可。代码// =================================== // author: M_sea // website: http://m-sea-blog...

  • M_sea
  • 2020 年 02 月 13 日
  • 暂无评论

    • Min_25 筛学习笔记

    设 $f$ 为积性函数，且其在质数处的取值 $f(p)$ 是关于 $p$ 的多项式，且其在质数的幂的取值 $f(p^c)$ 能快速计算，则 Min_25 筛可以在 $\mathcal{O}(\frac{n^{\frac{3}{4}}}{\log n})$ 的时间复杂度内算出 $\sum_{i=1}^nf(i)$。思路为了方便，设 $\mathrm{P}$ 为质数集，$p_i$ 为第 $i$ ...

  • M_sea
  • 2020 年 02 月 13 日
  • 暂无评论

    • 洛谷6083 [JSOI2015]symmetry

    Luogu分析在原方阵的基础上构造出 $6$ 个方阵，分别为原方阵沿 $4$ 条轴对称之后的方阵、旋转 $90^\circ$ 后的方阵、旋转 $180^\circ$ 后的方阵。然后对这 $7$ 个方阵做一遍哈希。现在一个暴力做法是，枚举边长和左上角的坐标，然后利用哈希判断它是否满足某些条件。这样子是 $\mathcal{O}(n^3)$ 的，并跑不过。考虑到如果存在一个边长为 $k$ 的方阵...

  • M_sea
  • 2020 年 02 月 10 日
  • 暂无评论

    • 洛谷4044 [AHOI2014/JSOI2014]保龄球

    Luogu分析太神了...看了好久才看懂...先考虑一些性质：如果上一轮是全中，那么一定放第一轮最小的补中（可以让第一轮最大的补中放在其它补中后），或者总分最大的失误。如果上一轮是补中，那么一定放第一轮最大的。可以发，我们要么取第一轮最小的补中，要么取第一轮最大的补中。考虑最优解大概是什么样子，可以发现是全中补中交替放，最后再放失误，而第一个失误要么是第一轮最大的，要么是总分最大的。但是由于...

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

    • 洛谷6084 [JSOI2015]isomorphism

    Luogu分析判无根树重构时，先以重心为根转为有根树，再做树哈希。这道题稍微改一下，求重心时忽略假节点，然后设计一种假节点的哈希值等于它的儿子的哈希值的树哈希方式就好了。需要注意的是无根树可能有两个重心。代码// =================================== // author: M_sea // website: http://m-sea-blog.com...

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