目录
2020牛客暑期多校第六场
比赛地址
[A] African Sort
题意
给一个排列p,每次可以选一个下标集合进行等概率打乱并花费集合大小的代价,求将p变成升序所需的最小代价的期望.
题解
队友推的式子,其中有一个$ans_{n}=\sum_{i=2}^{n-1}\frac{ans_{i}}{i}+n$
把环找出来计数下就行了.
[B] Binary Vector
题意
随机生成$n$个$n$维的,由01组成的向量,求他们线性无关的概率.
题解
结论题.
$f_{n}=\frac{2f_{n-1}+(2^{n}-1)}{2^{2n-1}}$
队友说是抽象代数课期末考试原题…然后现成回忆里一波结论就给秒了.
[C] Combination of Physics and Maths
题意
给出一个矩阵,求它的一个子矩阵,使得子矩阵的和除以最后一行的和尽可能大.
题解
显然,最后的子矩阵只有一列,且确定了底边后,上面所有数都会被选中.直接枚举所有的情况取最大值就行了.
[E] Easy Construction
题意&题解
签到题
[G] Grid Coloring
题意
给出一个$n\times n$的方格,要求用$k$种颜色对每条边进行染色.要求所有颜色出现的次数必须相同,不能构成同色环,每一横以及每一竖必须包含两种及以上的颜色,输出染色方案.
题解
简单构造.
至少队友是这么说的,榜被带歪了,这题真的不难
[H] Harmony Pairs
题意
求$1$到$n$内有多少对数满足$A<html><B$且$d(A)></html>d(B)$.$d(x)$表示$x$的数位和.
题解
数位DP.同时枚举两个数的数位情况,多开两个变量,一个用来记录两数的数位差,另一个用来记录是否已经确定了两个数的大小关系.这题不需要考虑前导零的影响,所以不需要lead参数.
比赛的时候用的是两数各自的数位和表示的状态,于是毫无悬念地T了.姿势水平有待提高.
[K] K-Bag
题意
一个序列被称为是K-Bag当且仅当它可以被看做是一堆长度为$k$的$1$到$k$的排列的拼接.现在给出一个长度为$n$的序列,判断它是不是一个K-Bag序列的子列.
题解
显然,给出的序列的开头与末尾可能含有一段不完整的排列,前后缀的合法性可以用map预处理出来.将前后缀去掉后,剩下的就可能是一个K-Bag序列了.接下来枚举这个序列的开头位置,假设是第$i$位,那么$i$到$i+k-1$,$i+k$到$i+2k-1$,等这些区间都要是合法排列.依次检查一遍即可.
快速判断合法排列有一个技巧,先给$1$到$k$赋一个$2^{64}$以内的数,然后算一下排列的异或值,再预处理一下给出序列的前缀异或值.这样,通过将一段区间的异或值与算好的排列异或值进行比较就可以判断它是不是排列了,正确性极高(好像错误率是$\frac{1}{2^{64}}$来着?).
总结
栽在了H题上,用差来简化状态的手法应该很快就要想到的,看了题解后才发现距离正解真的只有一步之遥.前,中期没什么大的问题,后期的时间主要集中在想A和H上了.其实在发现H题实在没思路后应该开新题的,万万没想到J题的通过人数在封榜后暴增.A题推出来是一个意外之喜,希望之后可以保持状态.
