设最优解中购买的宝石集合为 $B$，免费获得的宝石集合为 $F$，满足 $|F| \le k\land \sum_{i \in B} w_i \le W$，目标最大化总美丽度 $\sum_{i \in B} v_i + \sum_{i \in F} v_i$。 假定此时一组不做任何相对花费约束的集合 $B$ 和 $F$…

## 2025.11.26 前几天过了一堆板子，做了点 NOIP 真题，没做什么杂题。 ### [CF1408D Searchlights](https://codeforces.com/problemset/problem/1408/D) 两个操作之间没有偏序关系。所以所有操作可以视为每个人进行： $$ a_i'\l…

## 2025.11.21 ### [P4954 [USACO09OPEN] Tower of Hay G](https://www.luogu.com.cn/problem/P4954) 考虑先搭塔顶，再往下搭。 一个贪心的想法是，当前层宽度越小越优。 于是设 $f_i$ 为考虑了 $i\sim n$ 的物品能搭出的…

在文章《算法入门：K-D Tree》发表评论：

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

观察到如果 $p_i>p_{i+1}$ 就必定需要分开读；否则直接把 $p_{i+1}$ 跟在 $p_i$ 后面读一定不劣。 设 $f(k)$ 为钦定 $k$ 个 $>$ 的方案数，$g(k)$ 为恰好 $k$ 个 $>$ 的方案数，则： $$ g(i)=\sum_{j=i}^{n}(-1)^{j-i}\binom{j…

## 2025.11.17 ### [P10207 [JOI 2024 Final] 马拉松比赛 2 / Marathon Race 2](https://www.luogu.com.cn/problem/P10207) 设把所有球所在的位置去重后有 $m$ 个。 有几个观察： 观察 $1$：至少需要 $1+2+\cd…

## [ARC210](https://atcoder.jp/contests/arc210) 前言：这场没有 $\text{VP}$，而是直接参加了。做出了 $A\sim C$，死磕 $D$ 题博弈论没磕出来。 ### [ARC210A Always Increasing](https://atcoder.jp/co…

### [P14382 [JOISC 2017] 开荒者 / Cultivation - 洛谷](https://www.luogu.com.cn/problem/P14382) 发现经过一系列操作后，原本每株草会导致一个矩形区域都覆盖上草。 考虑每个原本的草 $(x,y)$，经过操作后能覆盖矩形左上角为 $(x-a,…

## [ARC163](https://atcoder.jp/contests/arc163/tasks) 前言：$\text{VP}$ 了，做出了 $A\sim D$ 并没有吃罚时。 ### [ARC163A Divide String](https://atcoder.jp/contests/arc163/task…

## [ARC162](https://atcoder.jp/contests/arc162/tasks) 前言：$\text{VP}$ 了，做出了 $A\sim C+E$ 并在 $C$ 题因看错题吃了 $4$ 次罚时。 ### [ARC162A Ekiden Race](https://atcoder.jp/cont…

## 2025.11.13 ### [P1121 环状最大两段子段和](https://www.luogu.com.cn/problem/P1121) 记 $1$ 为取，$0$ 为不取，则整个序列的可能取数方案为： - $000111000111000$ - $111000111000111$ 对于第一种情况，实际上就…

## [ARC161](https://atcoder.jp/contests/arc161/tasks) 前言：$\text{VP}$ 了，做出了 $A\sim D$ 并在 $C$ 题吃了 $5$ 次罚时。 ### [ARC161A Make M](https://atcoder.jp/contests/arc161…

## [ARC160](https://atcoder.jp/contests/arc160/tasks) ### [ARC160A Reverse and Count](https://atcoder.jp/contests/arc160/tasks/arc160_a) 考虑 $f(l_1,r_1)$ 和 $f(l_…

### [P14365 [JOISC 2018] 高速公路建设 / Construction of Highway - 洛谷](https://www.luogu.com.cn/problem/P14365) 查询相当于查根到 $A$ 路径上的顺序对。 最终树的形态是固定的。考虑离线操作，得到整棵树后树剖。 发现每次查…

~~瞪了半天发现这不是树而是链。~~ 考虑每次从 $A$ 到 $C$ 的最优策略，显然是直接从 $A$ 向 $C$ 走，如果走不了就等待或者用技能直到能走，不会走回头路。 特判 $A=C$。 不妨先令 $A \min\{r_i\}$，那么使这条路消耗最小的走法是固定的。 对于每个区间，记录一个四元组 $(o,l,r,w…

### [P8338 [AHOI2022] 排列 - 洛谷](https://www.luogu.com.cn/problem/P8338) 显然 $P^{(k)}$ 即对集合 $\{1,2,\cdots,n\}$ 进行 $k$ 次置换 $\sigma$，其中 $$ \sigma=\begin{pmatrix} 1 &…

### [P14340 [JOISC 2019] 考试 / Examination - 洛谷](https://www.luogu.com.cn/problem/P14340) 每个人的信息 $(S_i,T_i)$ 视为 $(S_i,T_i,S_i+T_i)$，直接套三维偏序，排序一维，归并一维，数据结构维护一维。 `…

#### 单调队列优化dp 转移方程形如： $$ f[i]=\min(f[j]+a[i]+b[j]),0\le j pi(n, 0); for (int i = 1, j = 0; i 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) ++j; pi[i] = j;…

在文章《看不懂题意怎么办》发表评论：

我本来是满心期待地想看看如何看懂题目做法的。

#### 题目链接：[link](https://www.luogu.com.cn/problem/U609461) > **性质 $1$：进行该操作 $1$ 和 $2$后，依旧满足 $\{x_i\}$ 单调不减和 $\{y_i\}$ 单调不增。** > > 这是因为，对于每次操作，假设其为 $1$，则在 ${x_i}…

在文章《[ABC420F] kirinuki 解题报告》发表评论：

%%%

在文章《P12568 An Array and Range Additions 题解》发表评论：

%%%

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

%%%

## [题目链接](https://www.luogu.com.cn/problem/CF1806E) ## 题意简述 给定一棵带权树，多次查询两个节点 $x$ 和 $y$，要求计算从 $x$ 和 $y$ 到根节点 $1$ 路径上每组节点对的权值乘积之和。 形式化的，对于每组询问 $x\ y$： - 初始化 $\mat…

## 题目链接 ## 题意简述 给定一个长度为 $n$ 序列 $a$，有 $m$ 次询问，每组询问输入两个数 $t\ k$，要求 $a_t+a_{t+k}+a_{t+2\times k}+...$ 的值。 ## 思路 离线+根号分治。 先将离线后的询问按 $t$ 的大小排序，建立一个二维数组 $s$，初始时 $s_{i…

## [题目链接](https://www.luogu.com.cn/problem/U542594) ## 题意简述 **操作：** 1. 等概率从 $[1,n]$ 选取整数位置 $x$ ，并建立变量 $t\leftarrow0$。 2. 记 $P=a_{x-1}+a_{x+1}$ ，有 $\Large\frac{a…

## [题目链接](https://www.luogu.com.cn/problem/U541372) ## 题意简述 有 $a$ 个白石子，$b$ 个黑石子。现随机拿出一个石子，观察其颜色，再放回去，重复 $n$ 次。 问所有操作中，存在连续两次拿出黑石子的概率为多少。答案对 $998244353$ 取模。 ## 思…

## [题目链接](https://www.luogu.com.cn/problem/U541710) ## 题意简述 有两组数，$A$ 和 $B$，$n=|A|$，$m=|B|$。 求：$\Large\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{k=1}…

## 后缀排序 后缀排序，即将字符串 $S$ 的所有后缀按字典序排。 明确两个数组： - $sa_i$ 表示排名为 $i$ 的后缀在 $S$ 中的起始位置。 - $rk_i$ 表示在 $S$ 中以 $i$ 为起始位置的后缀在排序后的排名。 举个例子，对于字符串 $aabab$，其两个数组分别为： |-|1|2|3|4|…

**参考资料：https://oi-wiki.org//graph/virtual-tree/** # 目录 1. __虚树__ 1-1. __引入__ 1-2. __朴素做法__ 1-3. __优化做法__ 1-3-1. __观察__ 1-3-2. __虚树__ 1-3-2-1. __二次排序+LCA连边__ 1-3…