比赛链接

solved by 2sozx

给定一个长度为 $n$ 的排列，每次可以选择长度为 $s$ 的子序列进行随机重排，代价为 $s$ ，问将此排列重排为 $1,2\cdots n$ 的最小代价是多少。

这题正解题解出锅了

solved by

solved by

upsolved by

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$即可。

upsolved by

solved by

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$，是否前者已经大于后者，递推一波即可。

upsolved by

upsolved by JJLeo

对$1,2, \cdots , n$做$m$次操作，每次操作是做$x$次$k-$约瑟夫变换，问最后序列是什么。$(nm \le 10^6)$

用树状数组求出每次$k-$约瑟夫变换的置换序列（从上次位置往后$k$个，加上这个位置之前的，并对剩余个数取模，然后套树状数组求第k小即可），然后置换$x \mod n$次即可。

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：感觉就算了算分母和写挂了一道水题，梦游了