TH911 Blog

「光阴不可测，岁月亦无歌。」

Splay 之区间操作

Splay 维护区间操作

例题链接。 您需要写一种数据结构（可参考题目标题），来维护一个有序数列。 其中需要提供以下操作：翻转一个区间，例如原有有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。 前置知识：Splay 参见Splay 树详解。 平衡树维护区间信息 无论是 Splay 还是 FHQ Treap，亦或是其他...

Posted by TH911 on August 25, 2025

题解：Perishable Roads

CF773D

题目传送门 题意分析 考虑最终的生成树，一定包含了权值最小边。设该边为 $(u,v)$，若生成树中不包含 $u,v$，则一定有两条边分别到达 $u,v$。显然这两条边有一条换为 $(u,v)$ 更优。 那么生成树一定形如从 $t$ 到达最小边，之后便是从最小边出来的一些子树（实际上也可以是链，都是等价的）。 为了到达最小边，成为一条链是最优的，否则会有不必要的花费。 确定最...

Posted by TH911 on August 22, 2025

题解：[PA 2020] Malowanie płotu

洛谷P9108 | 前缀和优化 DP

题目传送门 绝世前缀和优化 DP 好题。 题意分析 即找出长度为 $n$ 的序列 $\langle[l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\rangle$ 的个数，且满足： $l_i,r_i$ 为整数，且 $1\leq l_i\leq r_i\leq m$。 对于 $1\leq i<n$，有 $[l_i,r_i],[l_{i...

Posted by TH911 on August 22, 2025

题解：Towering Arrays

CF2071F

题目传送门 VP 场切。 题意分析 二分答案 显然，条件 $b_j\geq p-\vert i-j\vert$ 成立的 $p$ 具有单调性。即若 $p=p_0$ 时该条件成立，则 $p<p_0$ 时也成立。 因此可以二分答案 $p$，取最大值即可。 线段树维护 $p$ 已经确定，那么便是判断条件。显然绝对值并不好处理，考虑拆开。 即需要满足条件： \[\b...

Posted by TH911 on August 20, 2025

题解：Trapmigiano Reggiano

CF2071C

题目传送门 题意分析 记起点为 $s$，终点为 $t$。 原树没有根，考虑人为设定一个根。不妨以 $t$ 为根节点。 那么求排列等价于求一种移动顺序，使得老鼠最后停留在根节点。 移动可以分两种：向上和向下。显然向上是更优的。 设老鼠当前位于节点 $p$，如果在 $x$ 处生成一个奶酪： 若 $x$ 是 $p$ 的祖先节点，则这是优的。 若 $x$ 是 $p$ ...

Posted by TH911 on August 20, 2025

李超线段树

例题：洛谷P4097

例题链接 要求在平面直角坐标系下维护两个操作： 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。 特别地，如果线段是竖直的，则取最上面的点。线段若不存在，则输出 $0$。 ...

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

FEATURED TAGS
树状数组 题解 省选/NOI− 提高+/省选− DP 基础算法 普及+/提高 数学 线段树 贪心 普及/提高− 组合数学 字符串 未完 二分 图论 平衡树 数论 树形 DP Tarjan 位运算 搜索 Trie 二分答案 状态压缩 无聊时候的一点思考 最短路 FHQ Treap NOI/NOI+/CTSC 前端 前缀和 树链剖分
ABOUT ME

要做一个优秀的 OIER

FRIENDS