2020牛客暑期多校训练营第六场

发表于 2021-05-02 分类于 ACM ，刷题实战，比赛阅读次数： 15 本文字数： 1.4k 阅读时长 ≈ 1 分钟

next hexonext butterfly volantis yearn yilia shoka indigo apollo landscape cactus matery icarus fluid material

比赛链接

https://ac.nowcoder.com/acm/contest/15880?&headNav=www

B Binary Vector

题意

随机n个n维01向量，询问这个n个向量线性无关的概率

题解

考虑第一个向量，可以有 $2^{n} - 1$ 选择，你不可以选择全为0的向量

然后考虑与第一个向量线性无关的向量，可以有 $2^{n} - 2^{1}$ 个，因为第一个向量的0倍和1倍不能选。

然后考虑与第一个和第二个向量线性无关的向量，可以有 $2^{n} - 2^{2}$ 个

于是最终的方案数为 $\begin{array}{r} \prod_{i = 0}^{n} 2^{n} - 2^{i} \end{array}$ ，考虑分母为 $2^{n \cdot n}$ $\begin{aligned} \frac{\begin{array}{r} \prod_{i = 0}^{n - 1} 2^{n} - 2^{i} \end{array}}{2^{n \cdot n}} \\ = \begin{array}{r} \prod_{i = 0}^{n - 1} 1 - \frac{2^{i}}{2^{n}} \end{array} \\ = \begin{array}{r} \prod_{i = 1}^{n} 1 - 2^{- i} \end{array} \end{aligned}$

C Combination of Physics and Maths

题意

给你一个矩阵，你可以选择他的任意行删掉，任意列删掉，你要使最后剩下的矩阵元素和除以这个矩阵最底下一行的的元素和的商最大。输出这个矩阵。

数据范围

矩阵元素行列数小于200，共计100组输入。输入恒正。

题解

剩下的矩阵，一定是原始矩阵的上缀。

由于不等式 $\frac{s_{1}}{a_{1}} \geq \frac{s_{1} + s_{2}}{a_{1} + a_{2}}$ 和 $\frac{s_{2}}{a_{2}} \geq \frac{s_{1} + s_{2}}{a_{1} + a_{2}}$ , 所以我们不必选择多列。只需要生下来一列姐可以了。追后直接暴力。

E Easy Construction

题意

你要构造一个长度为n的排列，对于所有的长度 $d \in [1, n]$ ，这个排列满足他存在一个子串其和模n为k

题解

直接考虑长度为n的子串，其实就是他自身，其和为 $\frac{n \cdot (n + 1)}{2}$

如果n为奇数，则k必须为0，然后这样构造，我们的偶数前缀满足模n为0，我们的奇数后缀满足模n为0

1	1,n-1,2,n-2,3,n-3...,n

如果n为偶数，则k必须为 $\frac{n}{2}$ ，考虑到n的后缀和到n/2的后缀

1	1,n-1,2,n-2,3,n-3...,n/2,n

J Josephus Transform

题意

给你一个长度为n的排列，输入m个操作，每个操作以a为基数，将约瑟夫环的出环顺序作为新的排列。一共做b次。问你最后排列变成了什么。

题解

使用数组数组维护约瑟夫环对应的置换，然后使用置换快速幂，最后乘起来得到最后的排列。

K K-Bag

题意

如果一个序列可以被分成多个不重叠子串，每个子串都是一个1到k的排列，则这个序列被称为是一个K-Bag，给你一个序列，问你他有没有可能是某个K-Bag的子串。

题解

预处理每一个长度为k的子串，判断他是不是排列，然后枚举序列开头非排列的长度。