date: '2023-10-08'
title: 'Solution Set -「LOC 4293」'
A. 特种训练 (train)
写不来这种 Ad-hoc 题.
B. 红色改造 (modification)
可以参考论文 万成章 - Astral Birth 解题报告
把相同连续段合并起来, 将原 $0/1$ 序列转化成一个由二元组 $(0/1, c_i)$ 组成的长度为 $m$ 的序列, 问题有转化一:
- 选出尽量长的子序列, 其段数不超过 $k+1$ ($+1$ 的原因是贡献分为三种, 打过朴素的 DP 都知道), 则子序列长度和为答案.
倒过来考虑, 我们需要从中选择一些元素删去, 有以下的 Observation:
- Observation 1: 我们不会删除相邻的元素.
那么有转化二:
- 对于每个 $k$, 选择一些价值之和为 $k$ 的元素并将它们删除, 要求元素两两不相邻, 且长度之和最小. 元素的价值就是 $1$ 或 $2$, 第一个和最后一个元素的价值为 $1$, 其余为 $2$.
然后就是一个经典的反悔贪心问题.
D. 车站爆破 (bomb)
居然可以维护操作序列... 还是见识浅薄...