2020牛客暑期多校第六场 ¶

排名	当场过题数	至今过题数	总题数
64/1019	6	8	11

A¶

solved by 2sozx

题意¶

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

题解¶

这题正解题解出锅了

B¶

solved by 2sozx JJLeo Bazoka13

题意¶

多少个不同的 \(n\) 维矩阵他们的秩为 \(n\)

题解¶

答案是 \(\frac{(2^n - 1)(2^{n - 1} - 1)}{2^{\frac{n(n+1)}{2}}}\)

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\)即可。

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

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

2020牛客暑期多校第六场 ¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

记录¶

总结¶

2020牛客暑期多校第六场¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

记录¶

总结¶

2020牛客暑期多校第六场 ¶