SunJude's Blog !

在万物匆忙荣枯中 短暂留下属于我的印记。

云斗国庆集训

0 条评论 OI 无标签 SunJude
Day 1100 + 0 + 100 + 0，唉唉被绿题战胜了。A QOJ2957设 $dp[i][j][k][l][3]$ 表示现在在 $(i,j)$ 位置，走到第 $k$ 个数字串的第 $l$ 位，上一步是从左边/右边/上面过来的最小值。枚举下一步往哪走，判断是否存在数字串满足条件，随便转移一下即可。B P6884我们递归地计算每个子表达式的最大值。假设一个表达式 $A$ 是由子表达式 ...

题解：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...

题解：P5679 [GZOI2017] 等差子序列

0 条评论 OI 无标签 SunJude
第一次见到这种题，感觉还挺妙的。Solution设 $\{a_i, a_j, a_k\}(i < j < k)$ 构成长度为 $3$ 的等差数列。先来考虑一下 $\mathcal{O}(n ^ 2)$ 的暴力。开个桶存一下序列 $a$，暴力枚举 $a_i, a_j$，这样就能算出 $a_k$ 的值，判断一下桶里有没有这个值就好了。考虑优化。这是一个有点类似可达性的东西，于是想到桶...