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

M_sea的博客

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

洛谷5503 [JSOI2016]灯塔

LuoguLOJBZOJ分析这题是 POI2011 的原题，原题做法戳这里。这里讲一下别的做法。首先移一下项得到显然 $\left\lceil\sqrt{|i-j|}\right\rceil$ 仅有至多 $\sqrt{n}$ 种取值，因此枚举它的取值，得到对应的 $j$ 的范围，用 ST 表查询最大值即可。时间复杂度 $\mathcal{O}(n\sqrt{n})$。代码// =======...

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

    • 洛谷6084 [JSOI2015]isomorphism

    LuoguBZOJ分析一道做法显然的题目，然而调了我好久 QAQ先考虑原树同构怎么做。因为是无根树，所以求出重心转为有根树，然后树哈希即可。这样子我们只需要比较重心的哈希值即可判断原树是否同构。需要注意的是无根树可能有两个重心，需要都记下来。把上面的做法扩展到简化树同构，只需要在求树的重心时把度数为 $2$ 的点不算入 $sz$ 中，然后用一些特殊的树哈希方式使得只有一个儿子时哈希值和儿子相...

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

    • 洛谷6096 [JSOI2015]地铁线路

    LuoguBZOJ分析首先输入的是字符串很不好，用 std::map 转成数。第一问很简单。对于每条线路新建一个点，线路上的车站向这个点连边权为 $1$ 的边，这个点向线路上的车站连边权为 $0$ 的边。求出 $s$ 到 $t$ 的最短路即为答案。第二问比较毒瘤。设 $mx_i$ 表示到达 $i$ 车站花费最少的最多乘坐时间。显然这个东西应该放在最短路图上去转移。我们把所有线路按 $dis$...

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

    • 洛谷6095 [JSOI2015]串分割

    LuoguBZOJ分析首先倍长字符串并跑一遍后缀排序，求出 $sa_i$ 和 $rnk_i$。先考虑一个弱化版：$k|n$ 时的情况。枚举第一个串的起始位置 $i\in[1,n/k]$，于是我们可以得到剩下所有串的起始位置 $i+n/k,i+2n/k,\cdots$。我们现在要求出该方案下最大的串，直接求出最大的 $rnk$ 即可。然后最后答案就是所有方案取个 $\min$。现在考虑一般情况...

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

    • 洛谷6087 [JSOI2015]送礼物

    LuoguBZOJ分析首先求一遍区间长度为 $L$ 时的最大值，枚举左端点并用 ST 表求极值即可。然后求区间长度在 $[L+1,R]$ 内时的最大值。显然最大值和最小值一定会在区间的左右端点处。注意到要最大化的式子是一个分数，根据分数规划那一套，考虑二分答案，则令 $w_i=a_i+mid\times i$，不难使用单调队列求出。代码// ========================...

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

    • 洛谷6076 [JSOI2015]染色问题

    LuoguBZOJ分析考虑容斥。设 $f(i,j,k)$ 为至少 $i$ 行、$j$ 列不涂色且至少有 $k$ 种颜色没有使用的方案数，根据组合意义可以得到直接 $\mathcal{O}(n^3)$ 计算即可。代码// =================================== // author: M_sea // website: http://m-sea-blog...

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

    • 洛谷5502 [JSOI2015]最大公约数

    LuoguBZOJ分析有一个结论：对于每个 $r$，不同的 $\gcd(a_l,a_{l+1},\cdots,a_r)$ 的数量是 $\log$ 级别的。证明：每次 $\gcd$ 发生变化时至少除以 $2$。于是我们枚举右端点，并开一个 vector 维护一下所有 $\gcd$ 发生变化的位置，更新答案就直接枚举 vector 内的每个元素即可。代码// =================...

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

    • BZOJ4484 [Jsoi2015]最小表示

    BZOJ分析如果删去 $(u,v)$ 后仍存在从 $u$ 到 $v$ 的一条路径，则 $(u,v)$ 可以删去。扩展一下：如果存在一个点 $x$ 满足 $x\neq u,x\neq v$，且原图上存在从 $u$ 到 $x$ 的一条路径和从 $x$ 到 $v$ 的一条路径，则 $(u,v)$ 可以删去。于是我们对于每个点，求出它能到达的点和能到达它的点并存到 bitset 里，然后判断每条边能...

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

    • 洛谷6093 [JSOI2015]套娃

    LuoguBZOJ分析禁 止 套 娃当所有套娃都不套套娃时，答案为 $\sum in_i\times b_i$。而把 $i$ 套进 $j$ 里面，答案会减少 $out_i\times b_j$。对于每个套娃，我们一定会选能选的 $out_i$ 最大的套在它里面。我们把所有套娃按 $b_i$ 从大到小排序，然后依次选择能选的 $out_j$ 最大的套娃套在它里面，这样子就能得到最优解。证明：假...

  • M_sea
  • 2020 年 02 月 04 日
  • 2 条评论

    • 洛谷6082 [JSOI2015]salesman

    LuoguBZOJ分析首先，一个点能停留 $s$ 次，等价于可以进入它的 $s-1$ 棵子树。先考虑第一问。 $dp_{i}$ 表示以 $i$ 为根的子树的最大收益，转移时在所有 $dp$ 值非负的子树选最大的那些进入即可。再考虑第二问。设 $f_i$ 表示以 $i$ 为根的子树中最大收益是否唯一。如果当前子树最大收益不唯一，那么有以下可能：一棵子树最大收益不唯一。选了一棵最大收益为 $0$...

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