OI

CF2133D 题解

0 条评论 OI 无标签 SunJude
Solution首先考虑最简单的情况，每次只杀栈底的怪物：对于第 $1$ 个怪：需要 $h_1$ 刀。对于第 $i(i \geq 2)$ 个怪：在第 $i - 1$ 个怪死后，它会掉 $1$ 点坠落伤害，于是就需要 $\max(0, h_i - 1)$ 刀。此时的答案是 $\textrm{base} = h_1 + \sum_{i = 2} ^{n} \max(0, h_i - 1)$。然后...

CyOI 追忆 题解

0 条评论 OI 无标签 SunJude
我们发现本题只与每个数的相对大小有关，故每次操作开始前先将点权离散化，以下不再赘述。原 std 做法Subtask #1暴力做法。直接维护这个序列显然不可行，遂考虑用桶来维护，记录 $D$ 序列中每个值的出现次数。操作 1 就是把 $x$ 到 $y$ 的简单路径上的点的点权对应的出现次数 $+k$；操作 2 求出桶内元素总和即为 $D$ 序列的元素个数，遍历找到中位数即可；操作 3 就是将桶...

UVA1626 题解 / test

0 条评论 OI 无标签 SunJude
Solution采用 区间 dp。对于串 $s$，$f_{l,r}$ 表示使 $[l,r]$ 区间变为正规括号序列所需添加的最少括号数量。初始化：$l = r$ 时，区间 $[l,r]$ 中只有一个括号，添加一个与之匹配的括号即可，故 $f_{l,r} = 1$。$l > r$ 时，不存在这种情况，$f_{l,r} = 0$。$l < r$ 时，由于需取最小值，故 $f_{l,r...