2020-2021:teams:alchemist:weekly_digest_6
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_6 [2020/07/17 23:03] hardict [龙鹏宇 Hardict] |
2020-2021:teams:alchemist:weekly_digest_6 [2020/07/18 10:21] (当前版本) mountvoom [肖思炀 MountVoom] |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| + | 本周主要做了两场牛客，和zzh队一起训练了一套区域赛。 | ||
| + | 自己随便做了点cf，这周学的有点少。 | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ===== 陈铭煊 Max.D. ===== | ===== 陈铭煊 Max.D. ===== | ||
| 行 32: | 行 33: | ||
| min25筛的一道https://vjudge.net/contest/361072#problem/E | min25筛的一道https://vjudge.net/contest/361072#problem/E | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| - | 无 | + | |
| + | [[https://codeforces.com/contest/1375/problem/E|E. Inversion SwapSort]] : 构造 | ||
| + | |||
| + | 题意: | ||
| + | |||
| + | 给定一个数组，对它所有逆序对的位置规定一个顺序，按照这个顺序交换以后使得数组的不严格单增的。数组长度不超过$10^3$ | ||
| + | |||
| + | 题解： | ||
| + | |||
| + | 考虑数组为长度为$n$的排列的情况，不是排列可以等价的转换为一个排列。 | ||
| + | |||
| + | 设逆序对为$(u, v)$，考虑先处理$v = n$的情况，看这样如果处理完成后是否能得到一个不影响结果的但是规模更小的问题。 | ||
| + | |||
| + | 考虑现在比$a[n]$大的数，如果我们按照比它大的数从小到大与它进行交换，相当于把$n$放到了最后一个位置上，前面比它大的数-1，问题的规模就变小了而且对结果没有影响。 | ||
| + | |||
| + | 实现是直接对逆序对排序即可。 | ||
| + | |||
| + | commet： | ||
| + | |||
| + | 开始考虑的是把最大的数和后面的数交换，但是这样可能会引起交换的混乱，不变的是逆序对的位置，而位置上的值一直在变化，应该从不变的位置入手而不是从值入手，逐步减小问题规模从而将问题解决。 | ||
2020-2021/teams/alchemist/weekly_digest_6.1594998210.txt.gz · 最后更改: 2020/07/17 23:03 由 hardict
