博主已经退役，评论可能会审核很久才能通过。

M_sea 的博客

“Poet Nai Dist, Phier”

洛谷5419 [CTSC2016]单调上升路径

Luogu 分析 根据题目里提供的证明，不难得到答案的下界是 $n-1$。下面我们来考虑如何构造出这个下界。 考虑拿出 $n-1$ 组匹配，满足两两无交，这样子每组匹配中的边只会有一条被经过，组内直接赋连续权值即可。 这 $n-1$ 组匹配可以把下面这个图旋转 $n-1$ 次得到 代码 // ==================================== // author:...

  • M_sea
  • 2020 年 11 月 10 日
  • 1 条评论

    • CSP2020 ～Lost～

    最后的倒计时。

  • M_sea
  • 2020 年 11 月 08 日
  • 3 条评论

    • 洛谷5607 [Ynoi2013]无力回天NOI2017

    Luogu 分析 没想到差分 /ll 根据要求的东西，不难想到线性基。现在既然有一个区间询问，而且线性基还很好合并，那么可以想到在外面套一层线段树。 问题是区间修改时一个线性基如何整体异或一个值。考虑差分，变成单点修改，直接把叶节点线性基清空然后 pushup 上去即可。 可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相...

  • M_sea
  • 2020 年 11 月 03 日
  • 2 条评论

    • NOIP2020 前的做题记录 III

    我做题速度什么时候能有卡老师一半快啊

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

    • IOI2021 集训队作业乱做

    咕了

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

    • 洛谷5296 [北京省选集训2019]生成树计数

    Luogu 分析 根据二项式定理有 所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。 因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ===...

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

    • CF1172E Nauuo and ODT

    Codeforces Luogu 分析 考虑计算每种颜色的贡献，即计算每种颜色包含在多少条路径中。 这个东西似乎还是不好算，可以考虑计算每种颜色不包含在多少条路径中。 我们把这种颜色染成白色，其它颜色染成黑色，那么只有黑色连通块内部的点对才满足条件。 于是我们需要支持修改颜色、求黑色连通块大小平方和，使用 QTREE6 一题的方法把颜色放到父边上，LCT 维护子树信息即可。具体细节可以看一看...

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

    • 洛谷5326 [ZJOI2019]开关

    Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...

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

    • 洛谷4705 玩游戏

    Luogu 分析 答案显然是 直接分治把所有 $1-a_ix$ 卷起来，然后多项式 $\ln$ + 多项式求导即可求出 $G(x)$，再推回 $A(x)$ 后卷积即可。 代码 不想写 vector，于是从鱼那里蒯了一个分治 /kel // ==================================== // author: M_sea // website: https:...

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

    • AGC038E Gachapon

    AtCoder Luogu 分析 我不喜欢容斥，我不喜欢组合意义，我不喜欢生成函数，我也没有精神 首先 Min-Max 容斥一手 转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去，转移要乘上一个 $-1$。 算答案就把上面这个东西代回去就好了。 代码 // ==================================== // author: M_sea //...

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