2020-2021:teams:farmer_john:2020牛客暑期多校第六场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第六场 [2020/07/31 14:25] 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** |
| ====题意==== | ====题意==== | ||
| 行 56: | 行 56: | ||
| 对$1,2, \cdots , n$做$m$次操作，每次操作是做$x$次$k-$约瑟夫变换，问最后序列是什么。$(nm \le 10^6)$ | 对$1,2, \cdots , n$做$m$次操作，每次操作是做$x$次$k-$约瑟夫变换，问最后序列是什么。$(nm \le 10^6)$ | ||
| ====题解==== | ====题解==== | ||
| + | 用树状数组求出每次$k-$约瑟夫变换的置换序列（从上次位置往后$k$个，加上这个位置之前的，并对剩余个数取模，然后套树状数组求第k小即可），然后置换$x \mod n$次即可。 | ||
| + | =====K.===== | ||
| + | **solved by 2sozx JJLeo** | ||
| + | ====题意==== | ||
| + | 给出一个长度为$n$的序列，问该序列能否是一个连续数个$1$到$k$排列组成的序列的一个子序列。$(n \le 5 \times 10^5, k \le 10^9)$ | ||
| + | ====题解==== | ||
| + | 从后往前固定$k$个$k$个地扫，如果当前$k$个（或不足$k$个）是一个合法的$k$排列或合法结尾不完整的一部分，就将该元素与该部分的下一个元素用并查集进行合并，最后从前往后扫，判断所有合法的前缀对应的末尾元素的下一个是否与$n+1$处于同一个集合，存在一个则合法，否则不合法。本题卡常，unordered_map+启发式合并路径压缩才过。 | ||
| =====记录===== | =====记录===== | ||
| 0min：开局分题感觉没有很签到的题\\ | 0min：开局分题感觉没有很签到的题\\ | ||
| 行 75: | 行 82: | ||
| =====总结===== | =====总结===== | ||
| * MJX：这场又有点犯病 | * MJX：这场又有点犯病 | ||
| + | * ZYF：数位dp没写过两个数的，完全想歪浪费了大把时间。全场梦游+犯病。 | ||
| + | * CSK：感觉就算了算分母和写挂了一道水题，梦游了 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第六场.1596176758.txt.gz · 最后更改: 2020/07/31 14:25 由 jjleo
