考虑阶梯化贡献，即求 $$ \begin{aligned} \sum_{x = 1}^{V} \sum_{i = 1}^{n - k + 1} [\max_{j = i}^{i + k - 1}\{a_j\} >= x] &= \sum_{x = 1}^{V} \sum_{i = 1}^{n - k + 1} [\ex…

先考虑没有修改怎么做。我们注意到每一段只有最大值和最小值是有用的，并且如果我们并没有将实际上最大的选作最大值，或没有选到正确的最小值，答案一定是不优的，于是我们考虑直接钦定一个位置是否是最大值或最小值，设 $f_{i, 0/1/2}$ 表示考虑完前 $i$ 个元素，现在没开始一段（$0$）、已经选定了最大值而没选定这一…

不难发现能否胜利显然满足单调性，考虑二分确定的前缀长度。显然能保证胜利当且仅当对方采取最优策略时仍然能胜利，而对方的最优策略显然是在剩下的未确定的位置中价值尽量大的放入技能等级尽量高的球员，仅需对这一种情况考虑能否胜利。 我们很难不注意到如果放弃一局的胜利，最多仅能获得另外一局的胜利，于是我们将所有位置按照价值从高到低…

我们先考虑如果保证 $a_i = i$ 时怎样做。 不难发现如果 $i$ 与某个位置交换过了，那么其再也无法交换，于是我们称操作 $i$ 为交换 $i$ 与 $i + 1$，那么我们就要选若干个操作，使得没有任何两个操作编号相邻，设 $f_{i, 0/1}$ 表示选定了前 $i$ 个操作，第 $i$ 个选还是不选的方案…

我们发现左端点一旦变化每个点的修改次数就会完全不同，于是我们考虑枚举左端点，倒着加入每个数同时维护每个点的操作次数，将询问挂在左端点上做区间查询。 我们注意到如果 $a_{i + 1} \geq a_i$ 且 $a_{i + 1} #define mem(a, v) memset(a, v, sizeof(a)) us…

> 整个 OI 生涯都没有 AK 过一次 CSP 初赛才是 OIer 最大的失败。 # 9.20 J 不会哈夫曼，虽然最后蒙对了，但 97。S 没有题不会，但是挂飞了，仅 89。 看来我只能度过一个相对失败的人生。 # 11.01 早上吃了自己几个月没吃过的肉夹馍，馍太干了非常难吃，杯子没洗又没法喝水，最后硬撑着吃完两…

在文章《题解：P11255 [GDKOI2023 普及组] 淋雨》发表评论：

因为我赛时是智障。

更加符合该题难度等级的做法。 我们设 $f_{c, i}$ 表示考虑前 $c$ 个字符，分成了 $i$ 段的方案数，不难想到 $$ f_{c, i} = \sum_{j = 1}^{cnt_c} f_{c - 1, i - j} \times {cnt_c - 1 \choose j - 1} \times {i \c…

我们知道一个括号序列合法，当且仅当将 $\texttt{(}$ 当作 $1$，$\texttt{)}$ 当作 $-1$ 时序列每个位置前缀和非负，且最后和为 $0$。 如果 $z_{a_i} = z_{b_i} = \texttt{(}$，那么选哪个对于最后和的影响是相同的，而选较小的一个可以使更多的前缀和增加 $1$…

我们容易将问题转化为给定若干区间 $[l_i, r_i]$，求至少需要放多少个点，使得每个区间内至少有一个点，并求方案数。 首先将所有 $l_i, r_i$ 离散化得到 $\{a_i\}$，我们发现本质不同的点只有两类： 1. $x = a_i$，这就是一个普通的点。 2. $x \in (a_{i - 1}, a_i…

建议先看 [P8502](https://www.luogu.com.cn/problem/P8502)。 我们考虑设 $f_{x, y, t}$ 表示从 $x$ 恰经过 $t$ 步到 $y$，且不在途中经过 $x$ 的方案数，就有简单的转移 $$ f_{x, y, t} = \sum_{(z, y) \in E} f…

首先将所有雨点转化为 $a_i, b_i$，表示其将要在 $a_i$ 时落在 $b_i$。因为起点在变，我们考虑倒着做，即使时间倒流，这样我们就可以将起点当作一个雨点转移。设 $f_i$ 表示强制淋到 $i$ 雨时的最大答案，就有 $$ f_i = \max_{a_j > a_i, v_c \times (a_j -…

注意到 $p \leq 12$ 非常小，考虑状压。设 $f_{u, s}$ 为 $u$ 子树内建立了 $s$ 中的分部的最大答案。转移首先考虑合并子树，有 $$ f'_{u, s \cup t} \gets f_{u, s} + f_{v, t} $$ 直接枚举是 $\mathcal{O}(4^p)$ 的，显然不行，注…

在文章《题解：P12013 [Ynoi April Fool's Round 2025] 牢夸》发表评论：

@時空 为啥会是啊

考虑一条边两个端点 $u$ 和 $v$ 所在集合的贡献系数： | |$A$ |$B$ |$C$ | |:-:|:-:|:-:|:-:| |$A$ |$2$ |$0$ |$1$ | |$B$ |$0$ |$2$ |$1$ | |$C$ |$1$ |$1$ |$2$ | 我们发现这和“两集选一”问题看起来相似，考虑最小割，…

注意到该和式即求最大的 $[1, q]$ 之和加上 $[s, t]$ 之和使得 $q \notin [s, t)$。我们希望 $q$ 与 $s, t$ 无关，这样就是最大前缀和加上最大子段和（注意均可以取 $0$）。我们注意到当 $[s, t]$ 取得最大子段和时，如果 $q \in [s, t)$，使 $q = t$…

考虑分别求 $\sum H_i$ 和 $\sum h_i$，而显然 $\sum h_i = \sum 2^{n - 1}(a_i + b_i)$，仅需考虑 $\sum H_i$。 我们注意到 $H_i = \sum_{x = 1}^{V} [x \leq H_i]$，于是我们考虑从 $1$ 到 $V$ 枚举 $x$，检…

题目即求可重集排列方案数，我们知道答案为 $$ {\sum c_i \choose c_1, c_2, \dots c_n} = \frac{(\sum c_i)!}{\prod c_i!} $$ 证明是考虑其中分子为不考虑重复数的排列数，分母为相同数字的排列数。 但是我们知道模意义下除法需要逆元，而 $a$ 在模 $…

我们发现 1 操作实际上是进行长度为 $c$ 的循环移位，而循环移位有以下性质： + 两次循环移位可以合并，即做一次长度为 $x$ 的后做一次长度为 $y$ 的等同于做一次长度为 $x + y$ 的。 + 循环移位的长度可以对 $n$ 取模。 + 在移位长度为 $x$ 的数组的 $a'_i$ 等于原数组的 $a_{(i…

首先很自然的将剩下的数的和转为删去的数的和。看到 $h, w \leq 15$ 首先想到 $\mathcal{O}(2^h)$ 枚举第 $i$ 行删或不删的状态，此时删除每一列的贡献就确定了，我们需要在 $w$ 个数中选出一些数使得和为一个常数。直接考虑每个数删或不删的复杂度是 $\mathcal{O}(2^w)$ 的…

下文中一切的等号并不意味着完全相等，而是二者量级相同，不会影响证明的结果。 --- $T(n) = 2T(\frac{n}{2}) + \mathcal{O}(n)$。 不难发现 $$ \begin{aligned} T(n) &= n \times 1 + \frac{n}{2} \times 2 + \frac{n…

我们注意到 $a_x \oplus b_y = 0$ 当且仅当 $a_x = b_y$，所以能从 $(1, 1)$ 走到 $(x, y)$ 当且仅当 $$ a_1 = a_2 = \ldots = a_x = b_1 = b_2 \ldots b_y $$ 分类讨论这个值是 $0$ 还是 $1$。我们记 $s_i =…

在周五因破伤风离校查看地图时：我有如下构思： + 乘坐京港高铁广东段，至少前往阳台山线路所和东莞南站。 + 乘坐深圳公交 E17 线火车站 ~ 锦龙段和 E13 线全线。 最终我决定乘坐广深港列车到达福田站，先乘坐 E17 至锦龙，随后地铁返回罗湖，再乘坐 E13 至松岗，最后地铁回到深圳北，乘坐京港转广深线列车返回。…

注意到 $m - n$ 非常小，也就是该图是一棵树加上少量非树边。对于非树边 $(u, v)$，考虑 $u$ 是否选择：若 $u$ 选择则要求 $v$ 不选，否则不限制 $v$，即可 $\mathcal{O}(2^{m - n + 1})$ 消除非树边限制。我们在树上设 $f_{u, 0/1}$ 表示 $u$ 选或不选…

我们注意到钦定一条路径不合法是容易的，只须要求整条路径上颜色相同即可，共 $k$ 种情况。故我们考虑容斥，每次钦定 $S$ 中的路径不合法，答案即为 $$ \sum_{S} (-1)^{|S|}ans_S $$ 考虑如何计算 $ans_S$。首先，有一些边不在钦定不合法的路径中，可以在 $k$ 种颜色中任意选择。随后，…

众所周知，国铁在 2025 年 9 月 6 日将部分广深城际线列车延长至广州北站始发终到，在广州白云站 ~ 广州北站段走行京广线；同时从 8 月底开始为配合广湛高铁接入广州站施工，临时封闭京广线广州白云站 ~ 广州站段下行线，下行列车在广州站西咽喉切割正线前往上行线，在上行线逆行至白云站后切割北咽喉正线回到下行线。为了…

我们注意到对于一种数，仅有最左侧的和最右侧的有贡献，故考虑选择 $k$ 对位置 $\{l_i, r_i\}$ 分别填入 $k$ 种数。因为填的数越小一定不劣，所以显然填 $[1, k]$。 答案为 $\sum(r_i - l_i) = \sum r_i - \sum l_i$，也就是选取尽量小的 $k$ 个位置作为 $…

首先我们注意到奇数位和偶数位是独立的，将其分开考虑。我们考虑贪心地从前向后要求每一位最小，也就是从小到大枚举 $i$，将与第 $i$ 位奇偶相同的最小值移动到第 $i$ 位上，然后将其删去。 令 $n$ 为当前剩余的数字数量，最小值在第 $j$ 位上。我们发现如果 $j \neq n$，直接向前交换即可；但是 $j =…

本文基于国铁 2025 年三季度（2025 年 7 月）调整的列车运行图，仅作为个人纪录。 --- 周期：2 天。担当：北京局 CR400BF-Z 重联。 Day 1： G335：7 : 26 北京西 开往 18 : 49 福田。 G6236：19 : 09 福田 开往 19 : 43 广州南。 G6201：20 :…

要求值的类型比 $[l, r]$ 少，考虑强制要求 $[l, r]$ 中的一种值不能选。具体地，对于位置 $i$，设上一个与其相等的位置为 $pre_i$，下一个与其相等的位置为 $nxt_i$，那么答案即为 $$ \max_{i = l}^{r} \{\min\{i - l, i - pre_i - 1\}, \mi…