2020-2021:teams:farmer_john:2020牛客暑期多校第七场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第七场 [2020/08/07 17:09] jjleo [题解] |
2020-2021:teams:farmer_john:2020牛客暑期多校第七场 [2020/10/07 21:24] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020牛客暑期多校第七场====== |
| [[https://ac.nowcoder.com/acm/contest/5672|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5672|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 8: | 行 8: | ||
| =====B.===== | =====B.===== | ||
| - | **solved by 2sozx** | + | **solved by 2sozx JJLeo** |
| ====题意==== | ====题意==== | ||
| $t$ 个询问，每个询问包含两个数 $n,m$，问将 $n\times m$ 个数分成最少多少个数使得这些数能够组合成 $n$ 个 $m$ 和 $m$ 个 $n$。$n,m\le 10^4$ | $t$ 个询问，每个询问包含两个数 $n,m$，问将 $n\times m$ 个数分成最少多少个数使得这些数能够组合成 $n$ 个 $m$ 和 $m$ 个 $n$。$n,m\le 10^4$ | ||
| 行 58: | 行 58: | ||
| 直接数论分块即可。注意细节！！！ | 直接数论分块即可。注意细节！！！ | ||
| =====I.===== | =====I.===== | ||
| - | **upsolved by JJLeo** | + | **upsolved by 2sozx JJLeo** |
| ====题意==== | ====题意==== | ||
| - | $n$个不同的点的生成森林中，每个点权值为该点的度数和平方，问所有生成森林的所有点的权值和是多少。$(n \le 5000)$ | + | $n$个不同的点的生成森林中，每个点权值为该点的度数和平方，问所有生成森林的所有点的权值和是多少，$T$组数据。$(n,T \le 5000)$ |
| ====题解==== | ====题解==== | ||
| - | 每个点都是对称的，因此只需固定一个点最后乘以$n$即可。首先设$h_i$为$i$个不同的点的生成森林数量，利用purfer序列可以得到$O(n^2)$递推式$h_i= \sum_{j=0}^{i-1}\binom{i-1}{j}j^{(j-2)}$。 | + | 每个点都是对称的，因此只需固定一个点最后乘以$n$即可。首先设$h_i$为$i$个不同的点的生成森林数量，利用purfer序列可以得到$O(n^2)$递推式$$h_i=\sum_{j=0}^{i-1}\binom{i-1}{j}j^{(j-2)}$$接下来设$g_i$为我们所考虑的点所在的树大小为$i$时所有情况该点贡献的权值和，考虑将该点固定为根，然后枚举该点的度数，利用prufer序列算出方案数，再乘以度数的平方和，得到$O(n^2)$递推式$$g_i=\sum_{j=1}^{i-1}\binom{i-2}{j-1}{(i-1)}^{i-2-(j-1)}$$最后设$f_i$为节点数为$i$时一个固定节点对答案的贡献，考虑枚举该点所在树的大小，则剩下的节点组成森林，可以得到$O(n^2)$递推式$$f_i=\sum_{j=2}^{j=i}\binom{i-1}{j-1}g_jh_{i-j}$$对于每个询问，我们只需$O(1)$输出$nf_n$即可。 |
| =====J.===== | =====J.===== | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| 行 83: | 行 83: | ||
| * MJX要练练英语加快读题速度 | * MJX要练练英语加快读题速度 | ||
| * CSK重写J到最后RE了（悲），并且比赛前一定要休息好，不然就会$2h$就宕机 | * CSK重写J到最后RE了（悲），并且比赛前一定要休息好，不然就会$2h$就宕机 | ||
| + | * ZYF要练习更好地理解题意（尤其是大模拟），避免和空气斗智斗勇。另外要加强知识的理解，例如因为对prufer序列一知半解而把I题完全想歪。 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第七场.1596791391.txt.gz · 最后更改: 2020/08/07 17:09 由 jjleo
