A. Tales of a Sort
关键就是找逆序对
记一组逆序对下标为 \(l,r\),则求出最大的 \(a_l\) 即可
B. Good Arrays
记要构造的 Good Array 为 \(b\)
前置:\(\forall 1\le i\le n,b_i=1\)
然后 \(O(n)\) 扫一遍看一下有没有重复,有重复就 \(b_i\leftarrow b_i+1\)
扫完之后,记 \(sum=\sum_{i=1}^n(a_i-b_i)\),如果 \(sum\ge 0\) 就有解;反之无解
C. To Become Max
假设 \(a_i\) 变成最大值 \(x\),那么后面一定是形如 \(x-1,x-2,\cdots\) 直到某个数不需要操作也能达到要求
这样一来,就是基于试错的方法计算答案,并且答案所在位置有单调性,很容易想到二分答案
然后就是枚举答案所在位置,模拟求解
复杂度 \(O(n\log m)\),其中 \(m=\max_{i=1}^n a_i+k\)
D. More Wrong
又是交互题
其实这道交互题和前面那些牛鬼蛇神比算比较简单的了
因为是求解整个序列的最大值位置,而交互一次 ? l r
返回的结果是 \([l,r]\) 的逆序对个数
这种问题显然可以分解,所以要么 DP 要么分治
如果考虑 DP,那就应该是区间 DP,但是 \(n\le 2000\),区间 DP 的复杂度基本上在 \(O(n^3)\),没法做(事实上也很难设状态和转移方程)
考虑分治,对于 \(l=r\) 的边界情况,显然就返回 \(l\)
否则,记 \(mid=\lfloor\frac{l+r}{2}\rfloor\),对于 \([l,mid]\) 和 \([mid+1,r]\) 分别求解,设 \(a\) 为 \([l,mid]\) 的解,\(b\) 为 \([mid+1,r]\) 的解,因为我们考虑分治,所以 \(a,b\) 其中一个是最大值,另一个是次大值
接下来就交互两次,一次是 \([a,b]\),另一次是 \([a,b-1]\)(\([a+1,b]\) 也行),然后判断逆序对数量是否相等即可
总交互次数就是 \(2n^2[1+\frac{1}{2}+(\frac{1}{2})^2+\cdots]<4n^2\),可以通过
E1. PermuTree (easy version) & E2. PermuTree (hard version)
(待补)
标签:890,le,Institute,题解,sum,mid,交互,DP,逆序 From: https://www.cnblogs.com/cantorsort2919/p/17609157.html