#P18788. [KOI2026 二轮] 数列操作
[KOI2026 二轮] 数列操作
[KOI2026 二轮] 数列操作(수열 연산 / Sequence Operations)
题目描述
给定长度为 的排列 和长度为 的数列 。 包含 到 各一次; 的元素互不相同,均在 到 之间。
初始令数列 。可以对 进行零次或多次以下操作。若当前长度为 :
- 交换:选择 ,且满足 ,交换这两个相邻元素。
- 合并:选择 ,把相邻的 替换为一个数 ,使数列长度减少 。
判断能否使 与 完全相同。若能,输出任意一个操作序列,操作数不超过 。无需最小化操作次数。可以证明,只要可以变成 ,就存在满足该操作次数上限的方案。
输入格式
第一行两个整数 。
第二行 个整数 。
第三行 个整数 。
输出格式
若无解,输出一行 NO。
若有解,第一行输出 YES,第二行输出操作数 (),接下来 行按执行顺序输出操作:
1 i:交换当前的第 个元素,执行前必须满足 ;2 i:合并当前的第 个元素,保留较小值。
每个位置编号均针对该操作执行前的当前数列,从 开始。所有操作的位置必须有效,最终数列必须精确等于 。多种合法方案都可接受。
样例 1
4 2
1 4 2 3
3 1
YES
6
1 1
1 2
1 3
2 1
1 1
2 2
数列依次变为 $[4,1,2,3]\to[4,2,1,3]\to[4,2,3,1]\to[2,3,1]\to[3,2,1]\to[3,1]$。
样例 2
2 1
1 2
2
NO
样例 3
4 4
3 2 1 4
3 1 2 4
NO
样例 4
4 2
1 3 2 4
1 3
NO
数据范围与子任务
所有输入均为整数,。 是 的排列, 的元素互不相同且属于 。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 7 | |
| 2 | 8 | |
| 3 | 12 | |
| 4 | 10 | 所有 |
| 5 | 13 | |
| 6 | 15 | 是 的子序列 |
| 7 | 30 | |
| 8 | 5 | 无附加限制 |
满分 100 分。时限 2 秒,内存 1024 MiB。使用 SPJ 验证方案。