CVBB ACM Team

--- 2020-2021:teams:alchemist:weekly_digest_6 [2020/07/17 23:05]
mountvoom [肖思炀 MountVoom]
+++ 2020-2021:teams:alchemist:weekly_digest_6 [2020/07/18 10:21] (当前版本)
mountvoom [肖思炀 MountVoom]
@@ 行 34: / 行 34: @@
 ===== 肖思炀 MountVoom =====
-无
+[[https://codeforces.com/contest/1375/problem/E|E. Inversion SwapSort]] : 构造
+题意:
+给定一个数组，对它所有逆序对的位置规定一个顺序，按照这个顺序交换以后使得数组的不严格单增的。数组长度不超过$10^3$
+题解：
+考虑数组为长度为$n$的排列的情况，不是排列可以等价的转换为一个排列。
+设逆序对为$(u, v)$，考虑先处理$v = n$的情况，看这样如果处理完成后是否能得到一个不影响结果的但是规模更小的问题。
+考虑现在比$a[n]$大的数，如果我们按照比它大的数从小到大与它进行交换，相当于把$n$放到了最后一个位置上，前面比它大的数-1，问题的规模就变小了而且对结果没有影响。
+实现是直接对逆序对排序即可。
+commet：
+开始考虑的是把最大的数和后面的数交换，但是这样可能会引起交换的混乱，不变的是逆序对的位置，而位置上的值一直在变化，应该从不变的位置入手而不是从值入手，逐步减小问题规模从而将问题解决。