2020-2021:teams:i_dont_know_png:multi2020-nowcoder-6
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-6 [2020/07/28 17:05] qxforever [A - Portal] |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-6 [2020/08/01 01:00] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 32: | 行 32: | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| - | 设 $n$ 阶 $01$ 矩阵满秩的数量为 $f_n$ ，有递推关系 $f_i=f_{i-1}\times2^i\times (2^i-1)$ ，然后除上 $2^{i^2}$ 就是概率。$n$ 的范围很大，$O(n\log n)$ 是不能通过此题的。需要预处理 $2$ 的幂次以及逆元的幂次做到线性。 | + | 设 $n$ 阶 $01$ 矩阵满秩的数量为 $f_n$ ，有递推关系 $f_i=f_{i-1}\times2^{i - 1} \times (2^i-1)$ ，然后除上 $2^{i^2}$ 就是概率。$n$ 的范围很大，$O(n\log n)$ 是不能通过此题的。需要预处理 $2$ 的幂次以及逆元的幂次做到线性。 |
| 行 53: | 行 53: | ||
| 签到题 | 签到题 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== G - Grid Coloring ===== | ||
| + | |||
| + | Solved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个 $n \times n$ 的网格，用 $k$ 种颜色给每条网格边框涂色，使得： | ||
| + | |||
| + | - 所有颜色出现次数相同 | ||
| + | - 不存在同色的环 | ||
| + | - 一行或一列边框至少有两种颜色 | ||
| + | |||
| + | 构造方案，或说明无解。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 首先应当满足 $k \mid 2(n+1)n$，且 $n \geq 2$ 和 $k \geq 2$ 时才有解。 | ||
| + | |||
| + | 一种构造方法是，先依次把所有横边填满，再把纵边填满。若 $k \mid n$，就在奇数行用 $1, 2, \ldots, k, 1, 2, \ldots, k$ 把横边填满，在偶数行用 $2, 3, \ldots, k, 1, 2, 3, \ldots, k, 1$ 把横边填满。对纵边也这么处理，这样相邻行的横边不会有相同颜色。 | ||
| + | |||
| + | 否则 $k \nmid n$，直接 $1, 2, \ldots, k$ 一行接一行地连续填下去，不需要对相邻行额外去错开一个颜色，也能让相邻行的横边不会有相同颜色。 | ||
| + | |||
| + | 这样做出来的图，一个方格中最多有两条边相同颜色，且任意两条横向相邻或纵向相邻的边颜色不同，手玩发现这样的性质是搞不出同色的环的，因此满足条件。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== H - Harmony Pairs ===== | ||
| + | |||
| + | Solved by nikkukun & Potassium. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 令 $S(x)$ 表示 $x$ 的十进制表示的数位和，求 $S(A) > S(B)$ 且 $0 \leq A \leq B \leq N$ 的 $(A, B)$ 个数，其中 $N \in [0, 10^{100}]$。 | ||
| + | |||
| + | |||
| + | ==== 解题思路 1 ==== | ||
| + | |||
| + | 数位 DP。令 $n$ 为 $N$ 的长度，$f(p, x, f_1, f_2)$ 表示处理好了 $[p, n]$ 区间的位置，$S(A) - S(B) = x$，且 $f_1 = [A \leq B],\ f_2 = [B \leq N]$ 时的方案数，则 DP 过程和转移就很好写了。总时间复杂度 $O(n \cdot dn \cdot d^2)$，其中 $d$ 表示十进制数位大小。 | ||
| + | |||
| + | |||
| + | ==== 解题思路 2 ==== | ||
| + | |||
| + | 奇怪的数位 DP。比赛时忘记咋写正常的数位 DP 了，写了一个不正常的数位 DP。 | ||
| + | |||
| + | 考虑 $A$ 和 $B$ 公共前缀相同时，实际只需要令不同的后缀位置满足 $A < B$（不取等），且数位和 $S(A) > S(B)$ 即可。假设第一个不同的位置上 $B$ 的值为 $c$，则从小到大枚举 $c$，对于当前枚举到的 $c$ 而言，之前所有计算的 $c'$ 都能对 $c$ 做出贡献（都比它小），只要能维护所有 $c' < c$ 且数位和为 $> x$ 的数的个数，即可 $O(x)$ 完成单个 $c$ 的统计与维护。 | ||
| + | |||
| + | 令 $f(n, x, f_1)$ 表示仅考虑 $[p, n]$ 区间的数 $C$，数位和为 $x$，且 $f_1 = [C \leq N]$ 的数的个数。这个东西是可以和上面无关独立计算的，当考虑 $[p, n]$ 且枚举 $c$ 时，只需要用已经计算出来 $f(p + 1, x - c, f_1)$ 就可以得到满足条件的数的贡献。 | ||
| + | |||
| + | 总时间复杂度同上。 | ||
| + | |||
| + | |||
| 行 88: | 行 147: | ||
| - | ==== 赛后总结 ==== | + | ===== 赛后总结 ===== |
| - | === nikkukun === | + | ==== nikkukun ==== |
| 一开始 H 读错题，写完才发现不对劲。后来写的时候也没想清楚数位 DP 的写法，占了大约一个多小时的思考时间。而且码力很弱，中途卡了好几次，以后开到细节题一定要和队友讨论下咋写。主要是对数位 DP 不熟，需要加强相关练习与 DP 技巧。 | 一开始 H 读错题，写完才发现不对劲。后来写的时候也没想清楚数位 DP 的写法，占了大约一个多小时的思考时间。而且码力很弱，中途卡了好几次，以后开到细节题一定要和队友讨论下咋写。主要是对数位 DP 不熟，需要加强相关练习与 DP 技巧。 | ||
| 行 98: | 行 157: | ||
| - | === qxforever === | + | ==== qxforever ==== |
| 前面发挥还比较正常。最后 10min 脑子进水，遇到不确定的还是要和队友确认下，厘清思路。 | 前面发挥还比较正常。最后 10min 脑子进水，遇到不确定的还是要和队友确认下，厘清思路。 | ||
| - | === Potassium === | + | ==== Potassium ==== |
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-6.1595927130.txt.gz · 最后更改: 2020/07/28 17:05 由 qxforever
