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

M_sea 的博客

歩み続けて 辿り着く先へと

洛谷6920 [ICPC2016 WF]Clock Breaking

LuoguGym分析竟然一遍 A 了，写篇题解纪念一下。如果一个灯管一直都是 X 或者一直都是 .，那它就有可能恒亮或恒灭。枚举起始时间，那么如果一个不可能恒亮或恒灭的灯管没有正常发光，那么这个起始时间就不合法。如果对于某个起始时间，某个灯管都正常发光，那它就有可能是正常工作的。如果一个灯管的可能性超过 $2$ 种，那么就输出 ?，否则输出对应的东西即可。难点主要在于码，但是想清楚了也不是很...

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

    • 洛谷4747 [CERC2017]Intrinsic Interval

    LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点，那么答案就是这个析点对应的段；否则还要找到两个点所在的两棵子树，LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...

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

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

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

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

    • CSP2020 ～Lost in the Nowhere～

    本来不想更了的，但是被催更了，所以还是来更一下。

  • 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

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

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

    • 洛谷5326 [ZJOI2019]开关

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

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