在讨论《k-d tree 求码风改良以及卡常》回复：

KDT 常数挺大的

在文章《NOIPlus 2025 AFO 记》发表评论：

摸摸

注意到答案不超过 $2$，因为 $a_s(a_s+1)$ 和 $a_t(a_t+1)$ 均为偶数。 判断答案为 $0$ 直接对每个点向其质因数连边即可。 判断答案为 $1$ 等价于添加某个 $a_i+1$，枚举 $i$ 并枚举 $a_i+1$ 的所有质因数，两两记录一下即可。复杂度是 $O(n\omega^2(V)\l…

字符串给定的形式是 $A,B,C,D,E$，这是相当奇怪的。 区间操作转化成差分，每次操作选一条边，花费边权的代价将连接的两个点状态取反，则有些点要求被操作奇数次，有些点要求被操作偶数次。 你的操作肯定不会成环，而一条路径只会对路径的两端造成影响。所以你本质上要对奇数点求一般图最小权完美匹配，两点边权是图上最短路。 这…

在讨论《赛场环境下如何输出代码占用空间》回复：

``` \time --format="%MKib" ./code ```

总而言之你要做的大概就是对于树上每个点 $i$ 计算 $\sum \limits_{j \in \mathrm{subtree}_i} f(j+d_i)$。 其中对 $f$ 的计算考虑在 01-Trie 上统计。你发现子树合并就是 Trie 合并，而每个点继承儿子除了合并外，$d$ 还减去了 $1$，体现为全局减 $1…

在文章《题解：CF1307E Cow and Treats》发表评论：

orz

一眼看过去这个题限制就很多，然后恰好 $2n-2$ 条边也十分奇怪，边权限定 $w_1<w_2<\cdots<w_{n-1}$ 也很诡异。 考虑从小到大依次加入每条边，加入一条边时你需要考虑图上在这两个连通块之间加边。不难注意到你必须恰好在两个连通块之间加两条边，且其中一条边权等于这条树边也就是目前的最大值，而另一条只…

当 $A,B$ 确定时，线段树优化 DP 不难做到 $O(n \log n)$。 考虑问题本质上是有若干对 $(c_1,c_2)$，$q$ 次询问给定 $A,B$，求 $\min \{A\times c_1+B\times c_2\}$。式子除以 $A$ 后即 $c1+\dfrac{B}{A}c_2$，对此我们知道只需…

神秘题。 注意到 $i,j$ 有边当且仅当 $\mathrm{popcount}(i \oplus j) = 1$，故 $\mathrm{popcount}(i)$ 与 $\mathrm{popcount}(j)$ 奇偶性必然不同，问题转化为 $O(2^n)$ 个点 $O(n2^n)$ 条边的最大权二分图匹配。 注意到…

问题是公平组合游戏，考虑计算 SG 函数。注意到任意时刻每个序列对应原序列的一个区间，所以记 $f_{l,r}$ 表示区间 $[l,r]$ 的 SG 函数，每次枚举删除的数 $x$ 并由此将 $[l,r]$ 划分为若干子区间，计算子区间游戏的 SG 函数的 $\mathrm{XOR}$，并所有 $x$ 求结果的 $\m…

注意到对于 $x_1,x_2,\cdots,x_n$，获得的代价是 $\sum \limits_{i=\frac{n}{2}+1}^n x_i - \sum \limits_{i=1}^{\frac{n}{2}} x_i$。这同时也是在 $n$ 个数中选 $\dfrac{n}{2}$ 个取 $+1$，另 $\dfrac…

令 $f_i$ 表示前 $i$ 个的答案，$\mathrm{submax}(i,j) = \max \limits_{x=i}^j s_x$。则 $f_i = \min \limits_{j \geq i - k + 1} \{ f_{j-1} + \mathrm{submax}(j,i)\}$。 直接利用线段树和单调…

这个题感觉不是很难。 分类讨论操作： 1. $1$ 变 $0$。考虑本来包含 $i$ 这个位置的区间 $[l,r]$。令 $1$ 权值为 $1$，$0$ 权值为 $-1$，$s(l,r)$ 表示 $[l,r]$ 区间权值和。则本来有 $s(l,r)=0$，所以 $s(l,i-1)+s(i+1,r)=-1$。所以 $s(…

鬼题。 我们猜测答案是 $n \bmod 2$，但是样例都过不去。这时不知道为什么有人能注意到样例是唯一的反例。 我们尝试归纳说明并给出构造。$n\leq 8$ 时，通过爆搜，不难说明必有解。 对于一般的 $n$，只要我们能将二叉树划分为若干大小为 $2$ 或 $3$ 的连通块，则自然能构造出 $n \bmod 2$，…

我们声称后手必胜当且仅当原序列存在一个子序列满足子序列内的和等于整个序列总和的一半。 显然这是充分的，因为任意时刻无论先手如何操作，后手操作另一个子序列的任意一个数。两个子序列减小量总相同，所以最后先手必败。 反之，先手每次任意操作一个数，后手操作后必定仍然不存在一个子序列和为整体的一半。这是因为你考虑若存在，容易反证…

不难看出最终每个 $i$ 的结果应该是前缀最大值和后缀最大值的较小值。 然后不难看出应该按照权值从小到大贪心。对于值域较大的问题常考虑整体操作，那么考察所有最小值变为次小值所需的花费。每一步让所有最小值 $+1$，应该先操作最左和最右的，然后操作中间的。总而言之不难用数据结构维护之。

不错的性质观察题。 先考虑判定。将过程反过来。本质等价于，对于目前串 $s$，选择一个长度 $\geq a$ 的不含 $1$ 的段，将段内的字符都变为 $\texttt{?}$，或者选择一个长度 $\geq b$ 的不含 $0$ 的段，将段内的字符都变为 $\texttt{?}$。问最终是否可能得到全 $\texttt…

此套路在不知道几场之前的梦熊模拟赛亦有记载。 将奇数位的权值 $01$ 反转。注意到现在的操作变为了，每次交换相邻两个字符，问最少多少次达到目标。 记第一个串中 $1$ 位置为 $x_1<x_2<\cdots<x_k$，第二个串中 $1$ 位置为 $y_1<y_2<\cdots<y_k$，答案显然为 $\sum \li…

很套路的题。 注意到两条边权 $w_1,w_2$ 的大小关系分界处为 $x =\dfrac{w_1+w_2}{2}$，所以只有本值不同的 $O(m^2)$ 种 MST，每种算一次预处理是 $O(m^3 \log m)$ 的，询问不难做到 $O(q \log q)$，据说能过。

在文章《SA 爬了。》发表评论：

结构化绑定不会ce吧

我们声称如果 $\forall i, 2 \mid cnt_i$，则答案为 $\lfloor \dfrac{\sum cnt_i}{3}\rfloor$。显然答案不超过其，而我们只需要每次任选三种长度并构造 $(a,b,b)$ 和 $(a,c,c)$，必定能达到这个值。 对于原问题，存在若干 $2 \nmid cnt_…

考虑只限制差分，则等价于某一列的和减去前一列开始最后一格开始的左上斜线内的和等于某值。所以 DP 中只需要记录之前每个还有用的斜线的和即可。精细分析一下状态和转移可知复杂度是 $O(n2^kk!)$，理论上不太可能跑得满，所以应该是很快的。

从前往后 DP。$f_{i,j,k}$ 表示前缀 $[1,i]$，有 $j$ 个位置爆了，还有 $k$ 个位置钦定了 $c>j$ 但还没有确定选什么数。当 $j$ 增加 $1$ 时尝试钦定若干位置值等于 $j+1$ 即可。复杂度 $O(n^3)$，原因是 $\sum cnt_i = n$。 没调出来，吐了。

问题等价于给若干字符串二元组，$q$ 次询问每次给两个字符串，问有多少二元组使得第一个是询问的第一个的后缀，第二个是询问的第二个的前缀。建 Trie 等价于查询两棵 Trie 上到根路径交，变成 DFN 序后随便维护。 不保证 $|t_1|=|t_2|$，神经病。

在讨论《linux怎么看程序动态空间》回复：

``` \time --format="%MKib" ./aaa ```

有一个 JOI 题和这个类似，贪心的方案一定是，从 $(n,m)$ 倒着走，每次选权值较小的那一侧。 那询问直接对方向切换的位置暴力做即可，线段树二分。复杂度 $O(qn \log m)$。

在讨论《关于关闭同步流》回复：

没。 `cout.tie(0)` 没用。

对 $r$ 扫描线，对于每个 $l$ 维护 $[l,r]$ 内和 $l$ 通信的最大权值。查询即在 $r$ 时查询 $[l,r]$ 区间最大值。 对于 $r$ 来说，合法的 $l$ 是一段区间，对于 $l$ 来说，合法的 $r$ 是一段区间。所以每个点相当于有一个区间 $[x_i,y_i]$，新加入 $r$ 时，考虑区…

在讨论《关于文件读写和关闭同步流》回复：

能