[个人训练]-Codeforces Round #842 (Div. 2)-A~F

前几天vp的一场，前面的题相对水一点，干脆倒着写题解~

题目链接：https://codeforces.com/contest/1768

• F. Wonderful Jump
• E. Partial Sorting
• D. Lucky Permutation
• C. Elemental Decompress
• B.Quick Sort
• A.Greatest Convex

F. Wonderful Jump

这题是看题解补的，首先\(O(n^2)\)的dp应该是很好想的，设\(f[i]\)表示从1到i的答案，\(f_i=\min_{j=1}^{i-1} (f_j+\min(a_j,\dots,a_i)(i-j)^2)\)。然后就不会了，首先他没有那种线性的结构，但是我们看到\(\min\)后面跟着的是\((j-i)^2\)，二次方让我们觉得有点搞头（因为这是凹函数，涉及到凹凸性，我们会想到琴生不等式之类的东西）。

性质1：考虑一个j到i的转移，不妨设\(k:j\leq k\leq i\)处a取到最小值\(a_k=\min(a_j,\dots,a_i)\)。那么很自然地考察\(\min(a_j,\dots,a_k)(j-k)^2+\min(a_k,\dots,a_i)(i-k)^2-\min(a_j,\dots,a_i)(i-j)^2=a_k((j-k)^2+(i-k)^2-(i-j)^2)<0\)，这意味着\(j\to k\to i\)比\(j\to i\)更优。即我们在考虑i从哪里转移来的时候，要考虑哪些\(j<i\)呢？1、应该是那些“后缀最小值”的位置（即上文提到的k）。2、同时不要忘记一种\(k=i\)的情况，这种时候显然不能直接转移，但是也只要从后往前考虑\(a_j>a_i\)的部分就行了（依然是在\(a_i\)处取到最小值的地方），一旦遇到一个\(a_j<a_i\)的话，更前面的部分就没有必要考虑了。
嗯听起来很好，让我们来算一下这样子的复杂度…好像还是\(O(n^2)\)呢！…

性质2：这个是我一开始完全没想的东西（可能也是没看数据范围），数据范围里\(n\leq 4\times 10^5\)，以及\(a_i\leq n\)。这个数据范围就很根号（x）
考察从\(j\to i\)一步一步跳，和只跳一步的差别，即考察何时\(\min(a_j,\dots,a_i)(i-j)^2>(a_j+\dots+a_i)\)，注意到\(a_i\leq n\)的条件，所以至少在\(\min(a_j,\dots,a_i)(i-j)^2\geq n(i-j)\)的时候，右侧式子\(>(a_j+\dots+a_i)\)。这个时候起码是成立的，即\(j<i-\frac{n}{\min(a_j,\dots,a_i)}\)的时候是没有必要考虑这个转移的（因为还不如一步一步跳，所以这种\(j\to i\)的结果肯定不如某个\(j\to k\to i\)）。这个性质有什么用呢？

这里硬要说的话依然是数据范围给的启示，考虑根据数据大小分类：
1、\(a_i\geq \sqrt n\)，那么性质2里提到的条件就变成\(j<i-\sqrt n\)了，对于每个这样的\(i\)只需要考察\(O(\sqrt n)\)个j即可。
2、\(a_i< \sqrt n\)，这时候考察性质1的做法，其中第一部分的情况维护一个严格递增的单调栈，因为\(a_i<\sqrt n\)，所以单调栈的大小是\(O(\sqrt n)\)的。考察第二部分的复杂度。假设我们人为地把\(a_1,\dots,a_n\)划分成了m个严格递增的区间，第i个区间的长度不妨设为\(L_i\)，那么\(\sum L_i =n\)。第二部分在整个过程的一个时间上界是\(\sum_{i=1}^m \min(L_i,\sqrt n)L_i\leq \sqrt n\sum_{i=1}^m L_i=n\sqrt n\)。

综上所述，整个算法的复杂度就是\(O(n\sqrt n)\)的啦。

code:https://pastebin.ubuntu.com/p/NdPz3TPqDb/

E. Partial Sorting

数数题，首先简单摸一下会发现\(f(p)\leq 3\)：因为121这个操作总是可以排完序。那就变成统计\(f(p)=0,1,2,3\)的方案数了。
1、\(f(p)=0\)只有一种，即\(p_i=i(\forall i)\)。
2、\(f(p)\leq 1\)要么1操作要么2操作，单独算一种1操作就能解决的，即\([2n+1,3n]\)是正常顺序，前面的任意排，\((2n)!\)种。那么算上2操作的，以及容斥原理去掉重复部分的（即\([1,n],[2n+1,3n]\)都是正常顺序的），这一部分\(2(2n)!-n!\)
3、\(f(p)\leq 2\)，要么12操作，要么21操作。先看12操作就能解决，意味着\([2n+1,3n]\)这个区间内不含值在\([1,n]\)的数（即只包含\([n+1,3n]\)内的数）（这一点是充要的，自行check），方案数\(\binom{2n}{n}(n!)((2n)!)\)，另一部分21操作也一样。
然后容斥原理考虑去掉重复的部分，即\([1,n]\)区间只含\([1,2n]\)的数，并且\([2n+1,3n]\)只含\([n+1,3n]\)的数，满足这一条件的排列。设\([1,n]\)内包含了k个\([1,n]\)的数字，则\(n-k\)个\([n+1,2n]\)的数字，\([1,n]\)这一区间有\(\binom{n}{k}\binom{n}{k}\binom{n}{n-k}n!\)种方案，而后还剩n-k个\([1,n]\)的数字之能放在\([n+1,2n]\)，方案数是\(\binom{2n-k}{k}n!\)，而剩下的\([2n+1,3n]\)这一段直接\(n!\)。
4、\(f(p)\leq 3\)，一共(3n)!种。
就算完啦

D. Lucky Permutation

这题就稍微套路一点，是个排列，交换任意两次操作相当于做了一次对换(ij)，置换拆成轮换，长度为k的轮换可以拆成k-1个对换，这些应该都是很经典的东西。
然后再看，他说要逆序对数恰好为1，那一共只有n-1种可能，就是把\(1,2,\dots,n\)的序列调换任意两个相邻位置。既然这样不妨先考虑把序列变成\(1,2,\dots,n\)，置换就是$$\binom{p_1,p_2,\dots,p_n}{1,2,\dots,n}$$，画成有向图来看，答案就是n-连通块个数（因为每个连通块贡献=点数-1）。而交换相邻位置相当于把某个\(p_i\to i\)改成\(p_i\to i+1\)，以及\(p_{i+1}\to i+1\)改成连向i，看图很直观，如果i和i+1连通的话，改完之后不连通，如果原来不连通的话改完之后就连通了。所以用并查集维护就行了。

C. Elemental Decompress

这题题解证了好几个性质，当时想的时候其实是直接贪心想的，因为p，q其实是对称的，那么直接从前往后扫，如果p中没有出现a[i]就放p里，否则放q里，如果q里也出现了a[i]那么必然是无解。最后再根据\(p_i,q_i\leq a_i\)的约数确定没填的位置（这里依然是贪心，根据\(a_i\)从小到大填）。正确性感觉很直观就不证了（感觉挺无聊的东西x）

B.Quick Sort

这题vp的时候卡了一会x，没看样例可能真没往这边想。首先恰好k次其实和不超过k次没区别对吧，那想的时候就稍微自然一点。因为最后一定是\(1,2,\dots,n\)的顺序，这些数字的相对顺序如果能保持就尽量不动，同时最优策略也只能是这样子。也就是说找一个最长的\(1,2,3,\dots,k\)的子序列就行，剩下的部分一定是要动的。

A.Greatest Convex

样例其实很明显看出来了，\(k!+(k-1)!=(k-1)!(k-1+1)=(k-1)!k\)。