2025年9月

题解：P7402 [COCI 2020/2021 #5] Sjeckanje

0 条评论 OI 无标签 SunJude
SolutionCF484D 的带修版本。关键观察：最优方案里，划分完的每个区间一定是单调的。证明是显然的。那么，划分点一定在每个波峰和波谷。考虑原数组的差分序列，则单调区间就转化成了同号区间，答案就是区间和的绝对值。对于修改，我们要做的是单点修改和查询全局答案。考虑线段树，pushup 如何合并两个区间？若两个子区间合起来是单调的，答案显然就是他们的和；若不是，就要讨论一下波峰和波谷选不选...

题解：P14015 [ICPC 2024 Nanjing R] 生日礼物

0 条评论 OI 无标签 SunJude
当时 sdcpc 之前和同学 vp 了这场，大战这个题 1h+ 未果，最后破防跑路去吃饭了。Solution我们不妨先考虑没有 $2$ 的情况。首先有一个 trick：将所有偶数位置取反，把 $0$ 变成 $1$，把 $1$ 变成 $0$。这样删除两个相邻的 $0$ 或 $1$ 就变成了删除一个 $01$ 或 $10$ 子串。我们惊奇地发现，由于只要有相邻不同的元素就能删除，所以这样操作后，...

题解：P13391 [GCJ 2010 #1A] Make it Smooth

0 条评论 OI 无标签 SunJude
Solution考虑 dp。设 $f_{i, v}$ 表示考虑到前 $i$ 位最后一个保留的元素是 $v$ 的最小代价。删除是显然的：$f_{i, v} = \min(f_{i, v}, f_{i - 1, v} + D)$。考虑修改为 $x$，这时候要考虑与前一个像素的距离不超过 $m$ 这一限制。那么距离超过 $m$ 的话我们应当往前面插入若干个元素，代价即为 $\mathrm{cost...