TH911 Blog

Posted by TH911 on August 20, 2025

题解：[ZJOI2007] 仓库建设

洛谷P2120

题目传送门朴素 DP 记 $\textit{dp}_i$ 表示第 $i$ 个工厂必须建仓库，第 $1\sim i$ 个工厂的总花费。则有： \[\begin{aligned} \textit{dp}_i&=c_i+\min_{j=0}^{i-1}\left(\textit{dp}_j+\sum_{k=j+1}^i(x_i-x_k)p_k\right)\\ &...

Posted by TH911 on August 20, 2025

斜率优化 DP 详解

例题：洛谷P3195

传统斜率优化 DP 例题：洛谷 P3195 [HNOI2008] 玩具装箱。给定正整数 $n,L$ 和数列 $a_1,a_2,a_3,\cdots,a_n$。$1\leq n\leq5\times10^4$。将 $a$ 划分为 $k$ 段，设第 $i$ 段为 $a_{l_i},a_{l_i+1},\cdots,a_{r_i}$，则记 $\displaystyle x_...

Posted by TH911 on August 19, 2025

题解：[HNOI2004] 敲砖块

洛谷P1437

题目传送门题意分析发现一块砖 $(i,j)$ 被打掉之后，第 $j$ 列在 $i$ 上面的砖都会被打掉。设 $\textit{dp}_{i,j,k}$ 表示第 $i$ 列中，打掉的最下面的砖为 $(j,i)$，一共打掉了 $k$ 块砖的答案。则有： \[\textit{dp}_{i,j,k}=\max_{l=0}^{j+1}\textit{dp}_{i-1,l,k-...

Posted by TH911 on August 19, 2025

题解：[SDOI2015] 约数个数和

洛谷P3327

题目传送门题意分析不妨令 $n\leq m$。首先，答案为： \[\sum_{i=1}^n\sum_{j=1}^md(ij)\] 这个 $d(ij)$ 表示 $ij$ 的约数个数，很不好处理。因此可以考虑 $d(ij)$ 能否化简，有： \[d(ij)=\sum_{x\mid i}\sum_{y\mid i}[x\perp y]\] 证明参见此处。因此可以...

Posted by TH911 on August 18, 2025

题解：[HEOI2016/TJOI2016] 排序

洛谷P2824 | ODT 维护。

题目传送门问题转化发现询问有且仅有一次，且仅询问一个位置。因此无需得出整个序列，得出排序后的 $a_q$ 即可。区间排序实在不好做，因此考虑能否找到一种方式转化。答案与 $a_q$ 正相关，其余其实并不重要。因此不妨有： \[a_i\leftarrow \begin{cases} 1&a_i\geq a_q\\ 0&a_i<a_q \end{c...

Posted by TH911 on August 18, 2025

题解：Physical Education Lessons

CF915E

题目传送门题意分析操作即区间赋值为 $0$ 或 $1$，求 $1$ 的个数。显然可以 ODT 维护。注意不要滥用 perform 操作，而应当维护全局标记。因为不存在 perform 操作，故有时间复杂度：$\mathcal O(q\log n)$。 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2...

Posted by TH911 on August 16, 2025

题解：序列

洛谷P5350

题目传送门 ODT 珂朵莉树如果你不会，你可以看看：ODT 珂朵莉树。数据随机，且有区间赋值，因此考虑 ODT。操作 $1\sim3$ 是简单的，考虑操作 $4\sim6$。操作 $4$：区间复制区间不交，分别 split 操作后，暴力记录 $[l_1,r_1]$ 的信息，删除 $[l_2,r_2]$ 的信息再插入记录信息即可。同时注意区间端点需要偏...

Posted by TH911 on August 16, 2025

ODT 珂朵莉树详解

例题：CF896C

珂朵莉树（ODT）是一种在随机数据下复杂度优秀的维护存在区间赋值操作的数据结构。在随机数据下，期望不同的值的个数并不多，因此可以合为一个节点处理，便得到了珂朵莉树。 ODT 珂朵莉树例题：CF896C Willem, Chtholly and Seniorious 给定序列 $a_1,a_2,\cdots,a_n$。维护操作：将 $a_l,...

Posted by TH911 on August 16, 2025

题解：[CSP-S2019] Emiya 家今天的饭

洛谷P5664

题目传送门题意分析原来的 $a$ 可以视为一个矩阵。接下来的「行」「列」即矩阵意义下的行/列，「行」代表「烹饪方法」，「列」代表「主要食材」。不考虑小于等于 $\left\lfloor\dfrac k2\right\rfloor$ 的限制，不难发现，所有的方案数为： \(\prod_{i=1}^n\left(\sum_{j=1}^ma_{i,j}+1\right)-1...

Posted by TH911 on August 16, 2025

TH911 Blog

李超线段树

例题：洛谷P4097

题解：[ZJOI2007] 仓库建设

洛谷P2120

斜率优化 DP 详解

例题：洛谷P3195

题解：[HNOI2004] 敲砖块

洛谷P1437

题解：[SDOI2015] 约数个数和

洛谷P3327

题解：[HEOI2016/TJOI2016] 排序

洛谷P2824 | ODT 维护。

题解：Physical Education Lessons

CF915E

题解：序列

洛谷P5350

ODT 珂朵莉树详解

例题：CF896C

题解：[CSP-S2019] Emiya 家今天的饭

洛谷P5664

FEATURED TAGS

ABOUT ME

FRIENDS