Warning: session_start(): open(/tmp/sess_6cff2ebfd2dbea64d188f53a7576f9eb, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
======2020牛客暑期多校第六场======
[[https://ac.nowcoder.com/acm/contest/5671|比赛链接]]
=====A.=====
**solved by 2sozx**
====题意====
给定一个长度为 $n$ 的排列，每次可以选择长度为 $s$ 的子序列进行随机重排，代价为 $s$ ，问将此排列重排为 $1,2\cdots n$ 的最小代价是多少。
====题解====
这题正解题解出锅了
=====B.=====
**solved by**
====题意====
====题解====
=====C.=====
**solved by **
====题意====
====题解====
=====D.=====
**upsolved by **
====题意====
====题解====
=====E.=====
**solved by 2sozx JJLeo**
====题意====
给定$n,k$，构造一个$1$到$n$的排列使得存在长度为$1,2, \cdots , n$的连续子序列的和对$n$取模为$k$。$(n \le 5000)$
====题解====
如果$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.=====
**upsolved by **
====题意====
====题解====
=====G.=====
**solved by**
====题意====
====题解====
=====H.=====
**upsolved by JJLeo**
====题意====
问有多少个数对$(A,B)$满足$0 \le A \le B \le N$且$A$各数位之和大于B各数位之和。$(1 \le N \le 10^{100})$
====题解====
数位dp，设$f_{i,j,k,l}$表示从高位算第$i$位，两者数位之差为$j$，是否紧贴上界$N$，是否前者已经大于后者，递推一波即可。
=====I.=====
**upsolved by **
====题意====
====题解====
=====J.=====
**upsolved by JJLeo**
====题意====
对$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：开局分题感觉没有很签到的题\\
30min：MJX ZYF 构造E AC，MJX看C\\
45min：MJX WA，发现输出忘换行了，AC，看K\\
80min：ZYF 冲 K\\
91min：ZYF AC，CSK找B规律，MJX冲B\\
107min：MJX TLE，换int AC，一起冲G\\
153min：CSK WA2，MJX换思路\\
186min：MJX AC，看A\\
255min：MJX 推规律找到规律，WA\\
270min：MJX 数组开小了 AC\\
after end：CSK思路是对的，好像写挂了，A题貌似题出锅了\\
=====总结=====
* MJX：这场又有点犯病
* ZYF：数位dp没写过两个数的，完全想歪浪费了大把时间。全场梦游+犯病。
* CSK：感觉就算了算分母和写挂了一道水题，梦游了