2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7 [2020/08/07 01:46] qxforever |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7 [2020/08/20 17:36] (当前版本) nikkukun add CGIJ |
||
|---|---|---|---|
| 行 142: | 行 142: | ||
| \\ | \\ | ||
| + | |||
| + | |||
| + | |||
| ===== B - Mask Allocation ===== | ===== B - Mask Allocation ===== | ||
| 行 154: | 行 157: | ||
| 将 $n,m$ 进行类似辗转相除的过程即可保证组数最小。 | 将 $n,m$ 进行类似辗转相除的过程即可保证组数最小。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== C - A National Pandemic ===== | ||
| + | |||
| + | Upsolved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一棵 $n$ 个结点的树，初始所有节点权值都为 $0$，接着有 $q$ 次操作： | ||
| + | |||
| + | - 给定 $u$ 和 $w$，将树中所有节点 $v$ 的权值加上 $w - \mathrm{dis}(u, v)$； | ||
| + | - 给定 $u$，将 $u$ 的权值与 $0$ 取最小值； | ||
| + | - 给定 $u$，询问 $u$ 的权值。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 操作 2 实际就是一个单点加减，查询后记录一个变化量就行。 | ||
| + | |||
| + | 对于操作 1，$w - \mathrm{dis}(u, v) = w - \mathrm{dep}(u) - \mathrm{dep}(v) + 2 \cdot \mathrm{dep}(\mathrm{lca}(u, v))$，其中前三项都可以通过全局记录一个变化量维护，关键在后者。这里考虑一个很 tricky 的技巧，每次将 $u$ 到根的路径全部加 $2$，那么查询 $v$ 到根的路径和时，获得的就是 $2 \cdot \mathrm{dep}(\mathrm{lca}(u, v))$，树剖做一下即可。 | ||
| + | |||
| + | 树上两点路径相关的东西，可以先考虑固定其中一个点到根的路径，然后在走另一个点到根的路径上维护相关信息，它们第一次相遇的位置正是 LCA。例如 [[https://atcoder.jp/contests/agc047/tasks/agc047_d|AGC047 D - Twin Binary Trees]] 和本题就是这样的思路。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| ===== D - Fake News ===== | ===== D - Fake News ===== | ||
| 前缀平方和是完全平方数的正整数只有 $1$ 和 $24$ | 前缀平方和是完全平方数的正整数只有 $1$ 和 $24$ | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== G - Topo Counting ===== | ||
| + | |||
| + | Upsolved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | {{.:drg-example.png}} | ||
| + | |||
| + | 给一个以参数 $n \leq 5\ 000$ 控制的烤肉架图（如上图），求它的拓扑序个数模一个给定的质数 $P$ 的值。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 题解和[[https://blog.nowcoder.net/n/67dd005e3ff4477aab7b75b2bc028883|这篇博客]]讲得非常清楚了，实际就是根据不同状态下烤肉架由哪些位置的点控制得到转移关系，进而计算即可。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| ===== H - Dividing ===== | ===== H - Dividing ===== | ||
| 行 167: | 行 226: | ||
| 定义 Legeng Tuple 如下， | 定义 Legeng Tuple 如下， | ||
| - | - (1, k) 是 | + | - $(1, k)$ 是 |
| - | - 如果 (n, k) 是，那么 (n + k, k) 也是 | + | - 如果 $(n, k)$ 是，那么 $(n + k, k)$ 也是 |
| - | - 如果 (n, k) 是，那么 (n * k, k) 也是 | + | - 如果 $(n, k)$ 是，那么 $(nk, k)$ 也是 |
| 给定 $N,K$ ，问对任意 $1\le n\le N,1\le k \le K$ 一共有多少 Legeng Tuple。 $N,K\le 10^{12}$ | 给定 $N,K$ ，问对任意 $1\le n\le N,1\le k \le K$ 一共有多少 Legeng Tuple。 $N,K\le 10^{12}$ | ||
| 行 177: | 行 236: | ||
| 分两种情况考虑 | 分两种情况考虑 | ||
| - | - 进行过 *k 操作，那么可以表示为 p * k | + | - 进行过 $\times k$ 操作，那么可以表示为 $p \times k$ |
| - | - 没有进行过 *k 操作，那么可以表示为 p * k + 1 | + | - 没有进行过 $\times k$ 操作，那么可以表示为 $p \times k + 1$ |
| 答案是 $\sum_{i=1}^{k}(\lfloor\frac{n-1}{i}\rfloor+\lfloor\frac{n}{i}\rfloor +1)$ ，可以平方分块，也可以暴力算到 $\sqrt n$ ，后面就是一些 $0$ 和 $1$ 。 | 答案是 $\sum_{i=1}^{k}(\lfloor\frac{n-1}{i}\rfloor+\lfloor\frac{n}{i}\rfloor +1)$ ，可以平方分块，也可以暴力算到 $\sqrt n$ ，后面就是一些 $0$ 和 $1$ 。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== I - Valuable Forest ===== | ||
| + | |||
| + | Upsolved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给定质数 $P$，接着 $q \leq 5\ 000$ 次询问，每次询问求 $n \leq 5\ 000$ 个点的森林中，每个点度数的平方和模 $P$ 的值。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 首先显然所有点地位相同，只要随便算一个点再让结果乘 $n$ 即可。和度数相关的东西可以想到 [[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:nikkukun:pruefer-sequences|Prufer 序列]]，令 $f(n)$ 表示 $n$ 个点的树中，1 号点对答案的总贡献，则有 | ||
| + | |||
| + | $$ | ||
| + | f(n) = \sum_{d=1}^n d^2 \binom {n-2}{d-1} (n-1)^{(n-2) - (d-1)} | ||
| + | $$ | ||
| + | |||
| + | 实际就是钦定序列中哪 $d-1$ 个位置是 1 号点，其他点随便放。记 $g(n)$ 为 $n$ 个点的带标号森林个数，枚举 1 号点所在连通块的大小，则总答案为 | ||
| + | |||
| + | $$ | ||
| + | \sum _{i=1}^n f(i) \cdot g(n-i) | ||
| + | $$ | ||
| + | |||
| + | 现在考虑如何计算 $g(n)$。记 $h(n)$ 为 $n$ 个点的带标号树个数，由 Cayley 定理有 $h(n) = n^{n-2}$，故类似地枚举森林中 1 号点所在连通块的大小，有 | ||
| + | |||
| + | $$ | ||
| + | g(n) = \sum _{i=1}^n h(i) \cdot g(n-i) | ||
| + | $$ | ||
| + | |||
| + | 综上，总时间复杂度为 $O(\sum n^2)$。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== J - Pointer Analysis ===== | ||
| + | |||
| + | Upsolved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 很长，摸了，请参考原题。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 暴力记录每个指针能指向的变量分别都有啥，每次都用所有赋值关系更新至无法更新即可。 | ||
| + | |||
| + | 赛场上写麻烦了，而且最后只过了 99.04% 的数据也太惨了吧。 | ||
| + | |||
| + | |||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-7.1596736016.txt.gz · 最后更改: 2020/08/07 01:46 由 qxforever
