考虑到 DP 专题有时候并不是人打的。
因此不如来水一水 blog补一下训练记录。
平常专题就不必了，补了自己也看不懂。
因此我们只补自己做出来的题目（笑
原题链接，考虑到LUOGU最近把大量文章和剪贴板墙了，因此会在后文中拿出。
不过就学校这个 Latex 效果，估计是不会很好（所以快手动摇一摇 YY 让他更新 Latex 版本）
我们开始吧。
[T1/Unfound 5]
题面
[题目描述]
给定一个 1, 2, …, n 的排列 a_1, a_2, …, a_n，保证 a 满足特殊性质A或特殊性质 B。
你需要构造一个数列 b_1, b_2, …, b_L，使得：
- $ n ≤ L ≤ 5.5 × 10^5$。
- 对于任意 1 \leq i \leq L，1 \leq b_i \leq n。
- 对于任意 1 \leq i \leq n，b_i = i，且 b_L-n+i = a_i。
- 对于任意 1 \leq i
，如果 j – i \leq n – 2，则 b_i \neq b_j 。
如果有多个满足条件的数列 b，输出任意一个均可。
可以证明至少有一个满足条件的数列 b。
[输入格式]
第一行，一个正整数 n。
第二行，n 个正整数 a_1, a_2, …, a_n。
[输出格式]
第一行，一个正整数 L。
第二行，L 个正整数 b1, b2, …, b_L。
[Sample 1]
input
4
2 4 1 3
output
14
1 2 3 4 2 1 4 2 3 1 2 4 1 3
[Sample 2]
input
6
4 3 1 6 2 5
output
26
1 2 3 4 5 6 1 2 3 4 6 1 5 2 3 4 6 1 5 2 4 3 1 6 2 5
[数据范围与子任务]
对于所有数据，3 \leq n \leq 1000。
| 测试点 | $n \leq $ | 特殊性质 |
|---|---|---|
| 1 ~ 4 | 10 | A |
| 5,6 | 20 | A |
| 7,8 | 100 | A |
| 9,10 | 500 | A |
| 11 ~ 14 | 1000 | B |
| 15 ~ 20 | 1000 | A |
特殊性质 A：a 在所有 1, 2, …, n 的排列中随机生成。
特殊性质 B：保证恰好有两个位置 k 满足 a_k \neq k。
部分分
首先我们可以把 a 序列反序，然后就相当于要通过以上操作使其变成 [n, n – 1, n – 2, …, 1] 的一个序列，并将构造过程 反序输出 。
然后就有一个浅显的思路：
- 把 b 每隔 n 个分一段，每一段都是 1 ~ n 的一个排列。
- 对于每一个位置，填该段能填最大的数。（注意每一段必须要有 1 出现）
然后这样就构造完了，信心满满的交上去，可以获得 50 ~ 70 的高分。