官方题解｜排位赛#4题解Q5、Q6
前情提要：排位赛#4题解Q1-Q4
赛事地址：排位赛#4
直播预告：1月20日（周六）下午4点-6点 B站ACGO官方账号 排位赛#4复盘（欢迎观看大型翻车现场）
直播主讲：アイドル老师 ：小码王C++ 信奥算法讲师，3年C++算法竞赛教学经验，第47届国际大学生程序设计竞赛亚洲区域赛铜奖。
Q5 排列
提示
不考虑整齐度，如何交换元素让所有元素归位，能够使得交换的次数最少？
题目解析
如果不考虑整齐度，交换元素让所有元素归位，我们可以考虑让每个元素直接回到他的位置试试看。以样例 [2, 1, 4, 5, 3] 为例，为了方便我们令 t 为待交换元素（搁置元素）。
令 t = 2，放回到它的位置 i = 2，此时 a[2] = 1，把 1 设为搁置元素。
此时 t = 1，数组为 [2, 2, 4, 5, 3]；
然后我们再将搁置元素 t = 1 放到 i = 1，此时数组为 [1, 2, 4, 5, 3]，下标为 1, 2 的元素已归位。
同理我们可以使用以上方法使剩余元素归位。
不难发现，每一轮交换总是从一个位置 iii 开始，然后回到 iii 结束，形成一个环。
每个元素只会与其所在环内的元素交换，且让一个有 mmm 个元素的环的所有元素归位，只需要 m−1m-1m−1 次交换。
接着我们考虑交换次数受限制的情况。比如对于一个大小为 mmm 的环，我们可以交换元素的次数只有 k(1≤k<m−1)k(1 \le k < m - 1)k(1≤k<m−1) 次，那么对于这个大小为 mmm 的环，我们最多只能使 kkk 个元素归位。
由于题目中我们让每个元素归位获得的 整齐度 是不一样的，所以对于一个环我们如果只能归位有限个元素，显然应该选择优先归位权重（ 整齐度 ）更大的元素。所以归位一个环内的元素时，可以将环内元素按照权重从大到小排序，优先归位权重更大的元素。
接下来问题便可以转化成：数组中不在自己位置上的元素形成 nnn 个环，对于每个环可以选择归位若干个元素 bi(1≤i≤n)b_i (1 \le i \le n)bi (1≤i≤n)，限制为 b1+b2+⋯+bn≤kb_1 + b_2 + \cdots + b_n \le kb1 +b2 +⋯+bn ≤k 。
那么由于每个元素归位的权重不同，对于每个大小为 mmm 的环，实际上我们只需要关注在环中选择归位元素的数量即可，不需要枚举环中具体归位哪些元素。即选择 环中归位的元素数量 即可。
那么这里问题便转化为了一个 分组背包 问题：
有 nnn 个环，最多操作 kkk 次。
每个环可以选择归位元素的数量。
环 iii 选择归位 jjj 个元素的操作次数为
vij={j−1,if j = mj,if j < mv_{ij} = \begin{cases} j - 1, &\text{if j = m}\\ j, &\text{if j < m} \end{cases} vij ={j−1,j, if j = mif j < m
获得的 整齐度 为 sumijsum_{ij}sumij 即环 iii 中权重最大的 jjj 个元素的 整齐度 之和。
求解每个环选择归位多少个元素，操作次数总和不超过 kkk，且获得的 整齐度 最大。
对于本题的答案就是分组背包处理完后的答案加上已经在位置上的元素的 整齐度 之和。
AC代码
复杂度分析
找出整个数组的所有环的时间复杂度为 O(n)O(n)O(n)。
对于分组背包的问题，时间复杂度为 所有物品数量的总和 ×\times× 背包容量，本题 所有物品数量的总和 显然不超过 nnn，总的时间复杂度为 O(n⋅k)O(n \cdot k)O(n⋅k) 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Q6 相似排列
提示1
设 p[x]p[x]p[x] 是 xxx 在排列 aaa 中的位置（下标）。
由于 MEX([ap[0]])=1MEX([a_{p[0]}])=1MEX([ap[0] ])=1，所以 000 在排列 bbb 中的位置只能是 p[0]p[0]p[0]。
提示2
111 可以放在排列 bbb 中的什么位置？
提示3
假设 p[0]<p[1]p[0] < p[1]p[0]<p[1]；
如果 p[2]<p[0]p[2] < p[0]p[2]<p[0]，222 可以放在排列 bbb 中的哪些位置？
如果 p[2]>p[1]p[2] > p[1]p[2]>p[1]，222 可以放在排列 bbb 中的哪些位置？
如果 p[0]<p[2]<p[1]p[0] < p[2] < p[1]p[0]<p[2]<p[1]，222 可以放在排列 bbb 中的哪些位置？
题目解析
令 p[x]p[x]p[x] 为 xxx 在排列 aaa 中的位置（下标）。
由于 MEX([ap[0]])=1MEX([a_{p[0]}])=1MEX([ap[0] ])=1，所以 000 在排列 bbb 中的位置只能是 p[0]p[0]p[0]。
接下来讨论 111 可以放在排列 bbb 中的位置。
假设 p[0]<p[1]p[0] < p[1]p[0]<p[1]，那么
对于所有区间 [l,r](l≤p[0]<p[1]≤r)[l, r](l \le p[0] < p[1] \le r)[l,r](l≤p[0]<p[1]≤r)，有 MEX([bl,…,br])>1MEX([b_l, \ldots, b_r]) > 1MEX([bl ,…,br ])>1;
对于其他区间 [l,r](p[0]≤l≤r≤p[1])[l, r](p[0] \le l \le r \le p[1])[l,r](p[0]≤l≤r≤p[1])，有 MEX([bl,…,br])≤1MEX([b_l, \ldots, b_r]) \le 1MEX([bl ,…,br ])≤1 。
所以，111 必然只能放在 p[1]p[1]p[1] 这个位置。
我们以一个更具体的例子来说明：
> 假设 p[0]<p[1]p[0] < p[1]p[0]<p[1]，不难发现以下性质:
> A. 对于区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]], 有 MEX([bp[0],…,bp[1]])>1MEX([b_{p[0]}, \ldots, b_{p[1]}]) > 1MEX([bp[0] ,…,bp[1] ])>1；
> B. 对于区间 [p[0],x](p[0]<x<p[1])[p[0], x](p[0] < x < p[1])[p[0],x](p[0]<x<p[1])，有 MEX([bp[0],…,bx])=1MEX([b_{p[0]}, \ldots, b_{x}]) = 1MEX([bp[0] ,…,bx ])=1。
> 若 bp[1]≠1b_{p[1]} \neq 1bp[1] =1，令 xxx 为 111 在 bbb 中的位置，考虑以下两种情况：
> 1. x<p[0]x < p[0]x<p[0] 或 p[1]<xp[1] < xp[1]<x:
> 此时 xxx 在区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]] 外，此时 MEX([bp[0],…,bp[1]])=1MEX([b_{p[0]}, \ldots, b_{p[1]}]) = 1MEX([bp[0] ,…,bp[1] ])=1 与 AAA 矛盾。
> 2. p[0]<x<p[1]p[0] < x < p[1]p[0]<x<p[1]:
> 此时 xxx 在区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]] 内，此时 MEX(bp[0],…,bx)>1MEX(b_{p[0]}, \ldots, b_{x}) > 1MEX(bp[0] ,…,bx )>1 与 BBB 矛盾。
将区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]] 作为当前区间 [l,r][l, r][l,r] 并继续考虑 222 可以放在排列 bbb 中的位置。
若 p[2]∈[l,r]p[2] \in [l, r]p[2]∈[l,r]，那么
对于所有区间 [x,y](x≤l<r≤y)[x, y](x \le l < r \le y)[x,y](x≤l<r≤y)，有 MEX([bx,…,by])>2MEX([b_x, \ldots, b_y]) > 2MEX([bx ,…,by ])>2；
对于其他区间 [x,y](l<x≤y<r)[x, y](l < x \le y < r )[x,y](l<x≤y<r)，有 MEX([bx,…,by])≤2MEX([b_x, \ldots, b_y]) \le 2MEX([bx ,…,by ])≤2。
只要 222 在区间 [l,r][l, r][l,r] 内就能够满足以上两个条件，所以 222 可以放在区间 [l,r][l, r][l,r] 内的任何一个位置（除了已经被占用的位置），所以当 p[2]∈[l,r]p[2] \in [l, r]p[2]∈[l,r] 时，222 可以放置的位置数量为 (r−l+1)−2(r - l + 1) - 2(r−l+1)−2。
否则，222 只能放在排列 bbb 中的 p[2]p[2]p[2] 这个位置上。并且当前区间被扩展至包含 p[2]p[2]p[2]，变为 [p[2],r][p[2], r][p[2],r] 或 [l,p[2]][l, p[2]][l,p[2]]。
容易看出后续的数字 3,4,…,n−13, 4, \ldots, n - 13,4,…,n−1 都可以这样处理。
令 kkk 为当前处理的数字，若 k∈[l,r]k \in [l, r]k∈[l,r]，说明 kkk 可以放置的位置数量为 (r−l+1)−k(r - l + 1) - k(r−l+1)−k。否则将当前区间扩展至包含 p[k]p[k]p[k]。
最终问题的答案就是每个元素可以放置位置数量的乘积。
AC代码
复杂度分析
对于数字 000 可以放在排列 bbb 中的位置唯一，并可以将当前区间 [l,r][l, r][l,r] 初始化为 [p[0],p[0]][p[0], p[0]][p[0],p[0]]，之后按照顺序处理剩余的 n−1n-1n−1 个数字即可，时间复杂度为 O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
