TH911 Blog

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

Splay 之区间操作

Splay 维护区间操作

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

题解:Perishable Roads

CF773D

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

题解:[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...

题解:Towering Arrays

CF2071F

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

题解:Trapmigiano Reggiano

CF2071C

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

李超线段树

例题:洛谷P4097

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

题解:[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)\\ &...

斜率优化 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_...

题解:[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-...

题解:[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]\] 证明参见此处。 因此可以...