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

M_sea的博客

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

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

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

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

    • 洛谷4557 [JSOI2018]战争

    LuoguLOJ分析设第一个部落的领地为 $A$，第二个部落的领地为 $B$。假设 $B$ 移动了 $\vec{v}$ 后 $A$ 和 $B$ 仍有交，说明存在 $a\in A,b\in B$，满足 $b+\vec{v}=a$ 即 $\vec{v}=a-b$。构造 $A$ 和 $-B$ 的闵可夫斯基和 $C$，问题变为判断 $\vec{v}$ 是否在 $C$ 内，二分出极角相邻的点再利用叉积...

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

    • 洛谷4559 [JSOI2018]列队

    LuoguLOJ分析显然，所有学生跑到指定位置后，相对位置不改变会最优。那么最终会有一部分学生向左跑，一部分学生向右跑，而且两部分一定是分开的。考虑建立一棵以位置为下标的主席树。设 $rk_i$ 表示 $i$ 是当前区间中的学生中编号第 $rk_i$ 小的。若当前递归的区间是 $[l,r]$ ，分四种情况：没有学生，直接返回 $0$ 。全部向左跑，直接返回 $\sum a_i-\sum(k+...

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

    • 洛谷4516 [JSOI2018]潜入行动

    LuoguLOJ分析设 $dp_{i,j,0/1,0/1}$ 表示以 $i$ 为根的子树，已经放了 $j$ 个监听设备，$i$ 是否放了监听设备，$i$ 是否被子树中的点监听时子树中除 $i$ 外的所有点都被监听的方案数。转移类似于树形背包，需要将各种情况讨论清楚。边界为 $dp_{i,0,0,0}=dp_{i,1,1,0}=1$。代码// =========================...

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

    • 洛谷5772 [JSOI2016]位运算

    Luogu分析先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直接枚举...

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

    • 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 日
  • 暂无评论

    • 洛谷5545 [JSOI2016]炸弹攻击2

    Luogu分析枚举发射源，然后以它为源点将敌人和激光塔极角排序然后扫一遍。对于扫到的每个激光塔，显然它会和每个极角相差 $<\pi$ 的激光塔一起贡献所夹的敌人数的答案。破环为链，然后预处理出前缀和即可 $\mathcal{O}(n)$ 计算每个发射源的贡献。总时间复杂度 $\mathcal{O}(n^2\log n)$。代码// ===========================...

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

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

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

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