用户工具

站点工具


2020-2021:teams:hotpot:2020nowcoder1

这是本文档旧的修订版!


比赛信息

  • 日期:2020.7.12
  • 做题情况:lxh(I),tyx(F),gyp(HJ)

题解

A -

solved by

written by

题意

数据范围

题解

B -

solved by -, upsolved by tyx

题意

有一颗有无限个节点的树,这棵树的根节点是1,每个数$x$的父亲是$\frac{x|{f(x)}$,其中$f(x)$是$x$最小的质因数,现在给出$m$,对于$1!,2!,3!\ldotsm!$这$m$个点,每个点有一个权值$w_i$,现在要求在树上选一个点$p$,最小化$\sum_{i=1}^m w_i \times dis(p, i!)$,其中$dis$为两点距离,每条边长度为1

数据范围

题解

C -

solved by

题意

数据范围

题解

D -

solved by

written by

题意

数据范围

题解

E - Counting Spanning Trees

solved by -, upsolved by tyx

题意

给出一个二分图,两侧分别有$x$和$y$个点,现在对于左侧点$i(1 \le i \le x)$,它与右侧的点1到点$a_i$有连边,问这个二分图的生成树有多少个,答案对$mod$取模

数据范围

$1 \le x,y \le 10^5$, $1 \le mod \le 10^9$,$1 \le a_i \le y$

题解

结论题,答案是两边的点的度数全部相乘再除以两侧分别的最大值,可以利用前缀和求出右侧点的度数,然后两侧分别排序后相乘即可。结论证明没太看懂,在这里可以看

F - Infinite String Comparision

solved by tyx

题意

给出两个无限长字符串的循环节$a,b$,问两个字符串是否相同,例如$a=zzz$,$b=zzzz$,由于两个字符串无限循环后相同所以判定为相同

数据范围

$1 \le |a|,|b| \le 10^5$,输入字符串总长度不超过$2 \times 10^6$

题解

比赛的时候猜如果两个串不同,枚举到更长的字符串两倍长度就能找到不相同,实际上结论是到长度$|a|+|b|-gcd(|a|,|b|)$一定能找到不同,两倍显然长于这个值所以可行

G -

solved by

题意

h

数据范围

题解

I -

solved by

题意

题解

J -

solved by

题意

数据范围

思路

K -

solved by

题意

数据范围

题解

Replay

第一小时:

第二小时:

第三小时:

第四小时:

第五小时:

总结

2020-2021/teams/hotpot/2020nowcoder1.1594877888.txt.gz · 最后更改: 2020/07/16 13:38 由 misakatao