在文章《noip2025 游记》发表评论：

hyw

在文章《noip2025 游记》发表评论：

hyw

在文章《noip2025 游记》发表评论：

hyw

这题的特殊性质很有引导性，会了全部特殊性质基本就会正解了。 首先考虑 $|a_i|$ 互不相同怎么做。 发现一个数最后的符号只和它移动距离的奇偶性和原来的符号有关，并且最终序列的绝对值是先递减后递增。 那么自然考虑，按绝对值从大到小，在序列两端填数。设 $f_{i, 0/1}$ 表示考虑了绝对值 $\ge i$ 的数，…

在文章《题解：P12730 [KOI 2021 Round 2] 美食推荐》发表评论：

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

在文章《题解：P12730 [KOI 2021 Round 2] 美食推荐》发表评论：

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

在文章《题解：P12730 [KOI 2021 Round 2] 美食推荐》发表评论：

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

我们每次询问需要求的是，初始矩阵的一个子矩阵 $[x, x + h] \times [y, y + h]$ 作为金字塔的最底层，塔顶的颜色是什么。 手玩 $n \le 5$ 的矩阵很难不发现，塔顶是黑色当且仅当： - 对角线是同一种颜色； - 不在对角线上且和对角线曼哈顿距离 $\le 2$ 的点都是不同种颜色。 如下…

首先直接在序列上不好做，因为要时刻考虑跳到的点 $\le a_v$。 所以转而从值域考虑，令 $(u, v) \to (a_u, a_v)$，设 $b_i$ 为 $i$ 在 $a$ 中的位置。然后对于一个数 $x$，我们能求出一个 $c_x$ 表示在序列上，位置 $b_x$ 能跳到所有位置在 $[b_x + 1, c_…

独立做出的 *3500。 首先扫描线，然后考虑加速模拟过程。 题面中的除 $2$ 下取整是突破口。如果有一堆数，它们的极差 $d \ge 2$，那么进行一次除 $2$ 操作后，$d$ 至多变成 $\left\lceil\frac{d}{2}\right\rceil$。所以我们模拟 $O(\log V)$ 次，就可以使所…

T1 10min。 T2 纠结了 20min $O(nk2^k \alpha(n))$ 能不能过，最后写了发现飞快。 T3 我有一个神秘 AC 自动机 + fail 树上倍增的做法，浪费了好多时间卡常，甚至把普通倍增改成斜二倍增然而成效甚微，最后发现瓶颈在读入。 T4 想了 5min 感觉不可做，再想了 5min 发现…

考虑 $tp = 1$。枚举连通块在 $T_{\max}$ 的根 $x$，只保留 $T$ 两端都在 $x$ 子树内的边。发现 $T$ 中每条边覆盖 $T_{\max}$ 的一条祖孙链，且每条边至少被覆盖一次。 然后有一个比较深刻的观察是，把选连通块看成断一些边，一条边能断当且仅当它只被覆盖一次，感性理解就是如果被覆盖两…

完全不想思考怎么办？ 打个表，通过惊人的注意力可以观察出先后手的操作策略。 设 $a_{-1} = a_{n + 2} = 1$，$a_0 = a_{n + 1} = 0$。 先手的操作策略是： - 若存在两个相邻 $1$，就选择任意一对相邻 $1$； - 否则，若存在 $a_i = 1$ 满足 $i$ 的前一个 $1…

一个边集都是好的的充要条件是，边集构成一条链，且边集中的任意一条边都满足，它两端子树大小都 $\ge k$。 按 $k$ 从大到小扫描线，不断加入两端子树大小 $\ge k$ 的边。那么求一个边权和最大的好的边集，相当于求已经加入的边的直径。 我们需要一个支持单点修改边权，查树的直径的数据结构。用 [P6845 [CE…

在文章《P10896 移言丁真：Unavoided linyue》发表评论：

第一步可以参考其他题解吧，感觉我的方法比较神秘就不放了

首先删障碍不好考虑，转化为初始没有障碍，要在指定的 $m - k$ 个位置加入障碍，要求中间有障碍的城堡对数最大。 发现加入一个障碍最多使得两对城堡产生贡献：横向的一对和纵向的一对。所以我们优先加入能使得两对城堡产生贡献的障碍，再加入能使得一对城堡产生贡献的障碍，最后若还有剩余就随便加入。 将横向相邻的一对城堡看做左部…

首先如果每次给的是直接的一个串，那么建出所有串，正串和反串的 Trie，那么开头和结尾的限制相当于在两棵 Trie 上，集合串都要位于询问串的子树内，可以描述成二维偏序。加上时间维就是三维偏序，可以 $O(q \log^2 q)$ 解决。 现在我们的问题是不能把整棵 Trie 建出来。考虑只建出所有串结尾结点的虚树。建…

逐位确定答案。假设已经确定答案的前 $m$ 位分别为 $b_1, b_2, \ldots, b_m$。同时维护一个 DP 数组 $f_i$，表示一个子序列匹配了 $b$ 的前 $m$ 位，另一个子序列匹配了 $b$ 的前 $i$ 位是否可行。 首先如果存在 $i$ 使得 $f_i = 1$ 且 $a_{i + m +…

根据[经典结论](https://rushcheyo.blog.uoj.ac/blog/6704)，在第 $i$ 次操作后，我们这样计算答案： - 选一条没有被覆盖的树边和其他边，设没有被覆盖的树边数量为 $c_0$，有贡献 $c_0 \times (n - 1 + i - c_0)$； - 选一条恰好被覆盖一次的树边…

考虑 DP。设 $f_{u, i}$ 为 $u$ 子树内有 $k$ 个工厂的答案。加入一个边权为 $d$ 的儿子 $v$ 时，有转移： $$ f_{u, i + j} = \max(f_{u, i + j}, f_{u, i} + f_{v, j} + d \times j \times (k - j)) $$ 显然…

构造还是 2 hard 4 me。 首先令 $a_{i, j} = w_{i, j} - v_{i, j}$，目标变成让 $a$ 清零。然后发现边权和不变，所以若边权和 $\ne 0$ 则无解。 然后这种构造的一个通解应该是，组合一些题目给出的操作，得到较为简单的操作。 初步的观察是，进行 $(a, b, c, d,…

2025.10.13 upd：原来的代码复杂度疑似有问题，现已修正。 ---- 翻译官方题解。 首先红点形成一个连通块，然后观察最优解中选出的连通块有什么性质。 不妨令边权互不相同。发现对于任意 $e_1$ 使得其两端都是红点，和任意 $e_2$ 使得其恰好有一端是红点，都满足 $w(e_1) > w(e_2)$。证明…

翻译官方题解的一个可以拓展到 Hard Version 的做法。 首先红点形成一个连通块，然后观察最优解中选出的连通块有什么性质。 不妨令边权互不相同。发现对于任意 $e_1$ 使得其两端都是红点，和任意 $e_2$ 使得其恰好有一端是红点，都满足 $w(e_1) > w(e_2)$。证明考虑出现了一对 $w(e_1)…

线性规划对偶秒了。 由于 $q \le 10$，考虑 $O(n)$ 解决单次询问。 首先显然红点形成一个连通块。可以写出线性规划（令 $C$ 表示一个连通块）： $$ \begin{aligned} \text{minimize}\quad & \sum\limits_{i = 1}^n x_i \\ \text{s.…

在文章《题解：P11834 [省选联考 2025] 岁月》发表评论：

%%%%%%%

在文章《题解：P11834 [省选联考 2025] 岁月》发表评论：

%%%%%%%%%%%%%%%%%%

在文章《题解：P11834 [省选联考 2025] 岁月》发表评论：

%%%%%%%%%%%%%%%%%%%%%%

在讨论《Hack》回复：

改了，感谢/bx

在文章《CF2034H 题解》发表评论：

诶，好像是

在文章《CF2127G2 Inter Active (Hard Version)》发表评论：

确实，感谢