在文章《我的 OI 故事（二）：世上本没有路》发表评论：

龙猫老师，我们敬爱你口牙/xin

在文章《寒风是冬日的糖霜-WC2026青岛游记》发表评论：

我喜欢你

在讨论《提醒大家做好文章防抄袭工作。》回复：

@[mjhcsp1](luogu://user/1814180) 可以抄抄我的吗/kel

在讨论《在合理范围内随机平衡因子的替罪羊树对单次期望复杂度有保证吗》回复：

其实可以以 $\frac{1}{siz}$ 的概率重构子树

在文章《当树剖和倍增同时闪耀——O(log log n) LCA》发表评论：

实际上可以位单调栈 + ST 做到 OI 意义下较为简单的 O(n)/O(1) RMQ，自然 O(n)/O(1) LCA 也是容易的

在讨论《萌新袜子求助关于本题的线性做法（悬赏自提）》回复：

@[Acheron_RBM](luogu://user/700091) 就是将它转化到线性似乎不太容易x

在讨论《萌新袜子求助关于本题的线性做法（悬赏自提）》回复：

@[Acheron_RBM](luogu://user/700091) 感谢/bx

如题，我在做 QOJ9605（本题的线性空间版本）的时候发现了一种时空复杂度均为 $\Theta(n)$ 的做法，询问 U 群后未能得到该做法的解释。 本题同时也是 https://ac.nowcoder.com/acm/contest/23218/F。 其中 Tony 老师的做法就是本做法。 QOJ9605 的提交记…

如题，是本题最典型的二分在 fail 树的虚树边上统计的做法，调两个小时破防，随对着题解改改改几乎跟题解同构了但是在很神秘的地方 WA 掉了而且都是几百几十行的 WA，求查错（要悬赏可以自己提x） ```cpp #include #define X first #define Y second #define rep(…

在文章《「我希望这一切都只是梦」》发表评论：

我喜欢你

记录一下最近关于梦熊炼石做的题。 - CF1000F One Occurrence 维护 $\text{pre}$，查询是区间 $\min$，扫描线即可。 - P10833 [COTS 2023] 下 Niz 最值分治启发式分裂，$\Theta(n \log n)$。 找到所有 $1$ 的位置，讨论一个 $p$ 跟相邻…

在讨论《关于一篇题解的正确性问题》回复：

当然这个说明是相当平凡的

在讨论《关于一篇题解的正确性问题》回复：

所以这个做法至少正确性百分百没问题，就是证明没那么严谨，你还需要说明这种边界情况下另一个重心的情况，我后续补。

在讨论《关于一篇题解的正确性问题》回复：

哥们，这玩意是路径上一定包含了一个重心，但是重心有两个的情况下可能有一个不在里面，但是你知道了一个重心之后另一个显然是好求的，不然你猜为什么我后面代码写这么多。

感觉有点不明所以的题。 以下序列均为 1-index，假设 $k | n$，如果不是那么将序列末尾补 $0$ 即可，显然不影响复杂度。 首先 $\Theta(n)$ 的 dp 是显然的，考虑类似序列最大权独立集的转移就行。$f_i$ 为只考虑前 $i$ 个元素的得分，$f_i \gets \max(f_{i - 1},…

从这题出发，我决定用一个**比较基础的视角**来看贡献延迟计算。 --- 首先贡献是一个比较抽象的东西，你可以理解为我们把要算的东西拆成了很多个部分，每个部分之间它们的关系就是贡献。 贡献延迟计算就是考虑到，我们确定了当前位置的值，可能当下并没有影响，但是往后跟它取值相同的那些点，贡献又跟它不同了。这时候我们几乎不可能…

在文章《P5666 [CSP-S2019] 树的重心 - Solution》发表评论：

你注意到这个 d 压根没用

考虑 $s_1$ 和 $s_2$ 的 LCP 和 LCS 夹在中间的那一块。 比如考虑 $s_1 = x + y + z$ 和 $s_2 = x + y' + z$。 并且令 $t_1 = a + b + c$ 和 $t_2 = a + b' + c$。 令 $x$ 是 $a$ 的后缀，$z$ 是 $c$ 的前缀，$y…

在讨论《为什么这种是对的》回复：

kruskal，被 $m$ 条边就毙掉的边，加边后肯定还没办法排在原来毙掉它的边的之前，那它还是要被毙掉。

**T1** 每个贪一次最大值。 然后把绝对众数的计数移到次大值上，注意到次大值对应的东西不可能在操作后 $> \frac{n}{2}$，毕竟我们绝对众数到 $\frac{n}{2}$ 就收手了。 做完了。 **T2** 对原图跑 MST，现在只有 $n - 1$ 条边。 $2^k$ 枚举不可避免。 对额外点，我们枚举…

rt，除了 uoj1005，被肘飞了想学一下/kel

在讨论《关于st表和线段树》回复：

现在你有一个位运算单调栈做到 $\Theta(1)$ 查 $\mathcal O(\omega)$ 长度区间的的做法，好了现在你要如何做 OI 意义下的 $\Theta(n)/\Theta(1)$ RMQ。

刚开始想了一个假贪心还觉得对完了。 首先，可期待点类似于树的重心，不过这是虚树的重心。 给出一个重要观察：**可期待点构成树上的一条链。** - 两个可期待点之间的点均可期待。 否则，取出该不可期待点，该点必定存在一个子树，关键点数大于它的其余子树之和。而两个可期待点至少有一个不在该子树中，该可期待点往这个子树方向走贡…

现在有一个未知的森林，给 $n$ 个数的序列，$p_i$ 代表离 $i$ 最**远**的点中编号最小的一个，根据这个信息还原出森林中有多少棵树。 --- 离一个结点最远的点 $x$ 一定是直径端点之一，否则将直径锯断连向 $x$，一定可以构造出一个更长的直径。 孤立点是平凡的，以下的树默认结点数都大于 $1$。 结点大…

> 给定 $n$ 个结点 $m$ 条边的 DAG，每个结点可能有 $k$ 种颜色，并且给定正整数 $l$。对于一个染色方案（总共 $k^n$ 种染色方案），其价值定义为每种颜色长度为 $l$ 的链的数量的平方之和，求所有染色方案的价值之和。 > > $1 \le n \le 300,\,l \le 20,\,1 \le…

先把原题的 $p$ 除 $100$。 简单来说，$x$ 开始，$p$ 概率乘 $2$，$1 - p$ 概率加 $1$，求期望末尾 $0$ 个数。 --- 最朴素想法是设 $f_{i,\,v}$ 代表 $i$ 次操作后 $x$ 变为 $v$ 的概率，当然这个状态数超级大，没啥讨论的必要。 $k$ 对比之下显得很小，接下来…

在文章《高考求生指南：能活到高考已经很厉害了！》发表评论：

很难说zc的人会不会去真的做消毒，实际上有些心理状态下可能就是为了留疤的视觉冲击

在文章《题解：P11363 [NOIP2024] 树的遍历 极简单做法》发表评论：

很高妙的东西

在文章《OI 中的群论》发表评论：

魏老师/bx

> 何时才能 知晓自己也是美丽的呢 NOI2024 补的最后一道题，也是思维难度相当大的一道题，代码难度也不低。 ### 题目大意 给定简单有向图 $G = (V,\,E)$，对于 $\forall u \in V$ 进行分类： - $u$ 是**一类点**：则 $u$ 到所有其它结点都恰好有一条简单路径。 - $u$…