=====比赛信息===== * **日期：2020.7.27** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5671#rank|传送门]] * **做题情况：lxh(-)，tyx(EJK)，gyp(BC)** =====题解===== ====A - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====B - Binary Vector==== ===solved by gyp=== ===题意=== 从0和1构成n维向量里随机选n个，求这n个线性无关的概率 ===数据范围=== $1\le n\le 2\cdot 10^7$ ===题解=== 只需算有多少组线性无关的向量。已经选出m个线性无关的向量。这m个向量可以张成m维空间，因此下一个有$2^n-2^m$种选择。最终答案是$2^n\cdot \prod{i=1}^{n-1} (2^n-2^i)$ ====C - Combination of Physics and Maths==== ===solved by gyp=== ===题意=== 给定一个由正整数构成的矩阵。取它的一个子矩阵，使得这个子矩阵的元素之和除以最后一行的元素之和最大。求这个最大值 ===数据范围=== $1\le m,n \le 200$ ===题解=== 最终一定是选一列中靠上的所有。O(mn)枚举即可。 ====D - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====E - Easy Construction==== ===solved by tyx=== ===题意=== 构造一个$1$到$n$的排列，使对于任意$1 \le i \le n$，可以从这个排列中取出一个连续的长度为$i$的部分，它们的和$\mod \ n = k$，若没有解输出-1 ===数据范围=== $1 \le n \le 5000$，$0 \le k < n$ ===题解=== 首先我们发现$n$是奇数的时候必须有$k=0$，$n$是偶数的时候必须有$k=\frac{n}{2}$，其余情况均无解。$n$是奇数的时候，构造$n,1,n-1,2,n-2 ...$，$n$是偶数时构造$n,\frac{n}{2},1,n-1,2,n-2 ...$即可 ====F - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====G - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====H - Harmony Pairs==== ===solved by gyp=== ===题意=== S(x)表示十进制数x每一位数字之和。给定n，求$0\le a\le b\le n$,$S(a)>S(b)$的数对(a,b)的个数。 ===数据范围=== $n\le 10^100$ ===题解=== dp1[i][j]表示前i位a n$的时候，这个序列最多被分成前一半后一半分别是两个排列的一部分，单独判断一下即可，当$K \le n$时，我们考虑在$O(n)$的时间内求出某个位置以及它之前的$K-1$个位置能否组成一个完整的排列，然后从头和尾分别找到一个最长的部分可以作为一个排列的一部分，然后我们从头上开始$K$个一步跳，如果能跳到尾部的部分就说明可以，如果都不行就不行 =====Replay===== 第一小时：tyx和gyp开始想E，lxh开始想D，tyx先猜了一个结论但是WA，后来发现有问题并找到正解通过，lxh写出了一个版本D但是超时 第二小时：lxh开始想G，tyx开始想K，gyp连续通过了B和C题 第三小时：tyx写出了K但是WA，在找问题的时候lxh开始构造G但是一直WA，tyx找到了K的问题并通过 第四小时：tyx开始想J，gyp开始想H，tyx想出了J并开始写但是一直超时，后来发现因为多组数据有一个部分没有初始化，修改后通过 第五小时：gyp开始写H，lxh继续构造G但是没有通过，gyp最后没能写完H =====总结===== * 要注意各种细节从而尽量避免罚时 * 多组数据一定要注意初始化