Codeforces 2267D Backrooms Hill - Solution

给定 1~n 的排列,每次只能交换下标相差 2 的元素(即同奇偶位置内任意重排),判断能否变成「山形」。关键结构刻画:值 ≥ v 的位置必须构成连续区间。区间 DP 的转移只依赖区间长度与左端奇偶性,故按平移 2 格不变性坍缩成 n 层 × 2 状态,O(n) 判定;文中附「前 m 大值奇偶计数始终不失衡」的等价闭式证明,与官方扫描解法完全等价。

题解

本站由 zaochen 使用 Stellar 2.0.0 主题创建。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
全站访问量 - 次 · 访客数 - 人 · 本页面浏览 - 次

站内搜索

没有找到内容!