2020-2021:teams:hotpot:2020nowcoder6
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder6 [2020/07/31 11:54] misakatao 更新 |
2020-2021:teams:hotpot:2020nowcoder6 [2020/07/31 16:51] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| ===题解=== | ===题解=== | ||
| - | ====B - ==== | + | ====B - Binary Vector==== |
| - | ===solved by === | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 从0和1构成n维向量里随机选n个，求这n个线性无关的概率 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1\le n\le 2\cdot 10^7$ | ||
| ===题解=== | ===题解=== | ||
| - | ====C - ==== | + | 只需算有多少组线性无关的向量。已经选出m个线性无关的向量。这m个向量可以张成m维空间，因此下一个有$2^n-2^m$种选择。最终答案是$2^n\cdot \prod{i=1}^{n-1} (2^n-2^i)$ |
| - | ===solved by === | + | ====C - Combination of Physics and Maths==== |
| + | |||
| + | ===solved by gyp=== | ||
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给定一个由正整数构成的矩阵。取它的一个子矩阵，使得这个子矩阵的元素之和除以最后一行的元素之和最大。求这个最大值 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1\le m,n \le 200$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 最终一定是选一列中靠上的所有。O(mn)枚举即可。 | ||
| ====D - ==== | ====D - ==== | ||
| 行 85: | 行 97: | ||
| ===题解=== | ===题解=== | ||
| - | ====H - ==== | + | ====H - Harmony Pairs==== |
| - | ===solved by === | + | ===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<b<n，S(a)-S(b)+1000=j的方案数 | ||
| + | |||
| + | dp2[i][j]表示前i位a<b=n，S(a)-S(b)+1000=j的方案数 | ||
| + | |||
| + | dp3[i]表示前i位，a=b<n的方案数。这里S(a)-S(b)+1000一定等于1000 | ||
| + | |||
| + | 前i位a=b=n的方案数为1，S(a)-S(b)+1000一定等于1000。 | ||
| + | |||
| + | 对每一位，枚举a,b这一位的值，然后暴力分类转移即可。时间复杂度$O(100000\cdot l)$，其中l为n的长度。 | ||
| ====I - ==== | ====I - ==== | ||
2020-2021/teams/hotpot/2020nowcoder6.1596167646.txt.gz · 最后更改: 2020/07/31 11:54 由 misakatao
