2020-2021:teams:farmer_john:2020牛客暑期多校第六场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第六场 [2020/07/31 14:35] jjleo [题解] |
2020-2021:teams:farmer_john:2020牛客暑期多校第六场 [2020/10/07 21:24] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020牛客暑期多校第六场====== |
| [[https://ac.nowcoder.com/acm/contest/5671|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5671|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| - | **upsolved by** | + | **solved by 2sozx** |
| ====题意==== | ====题意==== | ||
| + | 给定一个长度为 $n$ 的排列，每次可以选择长度为 $s$ 的子序列进行随机重排，代价为 $s$ ，问将此排列重排为 $1,2\cdots n$ 的最小代价是多少。 | ||
| ====题解==== | ====题解==== | ||
| + | 这题正解题解出锅了 | ||
| =====B.===== | =====B.===== | ||
| **solved by** | **solved by** | ||
| 行 15: | 行 15: | ||
| =====C.===== | =====C.===== | ||
| - | **upsolved by ** | + | **solved by ** |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| =====D.===== | =====D.===== | ||
| - | **solved by ** | + | **upsolved by ** |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| 行 30: | 行 30: | ||
| 如果$n$为偶数则$k$必须为$\dfrac{n}{2}$否则$k$必为$0$。奇数时构造$n, n-1,1,n-2,2,\cdots$即可，偶数时构造$n, \dfrac{n}{2},n-1,1,n-2,2,\cdots$即可。 | 如果$n$为偶数则$k$必须为$\dfrac{n}{2}$否则$k$必为$0$。奇数时构造$n, n-1,1,n-2,2,\cdots$即可，偶数时构造$n, \dfrac{n}{2},n-1,1,n-2,2,\cdots$即可。 | ||
| =====F.===== | =====F.===== | ||
| - | **solved by ** | + | **upsolved by ** |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| =====G.===== | =====G.===== | ||
| - | **upsolved by** | + | **solved by** |
| ====题意==== | ====题意==== | ||
| 行 60: | 行 60: | ||
| **solved by 2sozx JJLeo** | **solved by 2sozx JJLeo** | ||
| ====题意==== | ====题意==== | ||
| - | 给出一个长度为$n$的序列，问该序列能否是一个连续数个$1$到$k$排列组成的序列的一个子序列。 | + | 给出一个长度为$n$的序列，问该序列能否是一个连续数个$1$到$k$排列组成的序列的一个子序列。$(n \le 5 \times 10^5, k \le 10^9)$ |
| ====题解==== | ====题解==== | ||
| 从后往前固定$k$个$k$个地扫，如果当前$k$个（或不足$k$个）是一个合法的$k$排列或合法结尾不完整的一部分，就将该元素与该部分的下一个元素用并查集进行合并，最后从前往后扫，判断所有合法的前缀对应的末尾元素的下一个是否与$n+1$处于同一个集合，存在一个则合法，否则不合法。本题卡常，unordered_map+启发式合并路径压缩才过。 | 从后往前固定$k$个$k$个地扫，如果当前$k$个（或不足$k$个）是一个合法的$k$排列或合法结尾不完整的一部分，就将该元素与该部分的下一个元素用并查集进行合并，最后从前往后扫，判断所有合法的前缀对应的末尾元素的下一个是否与$n+1$处于同一个集合，存在一个则合法，否则不合法。本题卡常，unordered_map+启发式合并路径压缩才过。 | ||
| 行 83: | 行 83: | ||
| * MJX：这场又有点犯病 | * MJX：这场又有点犯病 | ||
| * ZYF：数位dp没写过两个数的，完全想歪浪费了大把时间。全场梦游+犯病。 | * ZYF：数位dp没写过两个数的，完全想歪浪费了大把时间。全场梦游+犯病。 | ||
| + | * CSK：感觉就算了算分母和写挂了一道水题，梦游了 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第六场.1596177332.txt.gz · 最后更改: 2020/07/31 14:35 由 jjleo
