用户工具

站点工具


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! \ldots m!$这$m$个点,每个点有一个权值$w_i$,现在要求在树上选一个点$p$,最小化$\sum_{i=1}^m w_i \times dis(p, i!)$,其中$dis$为两点距离,每条边长度为1

数据范围

多组数据,$1 \le m \le 10^5$,$0 \le w_i \le 10^4$,$\sum m \le 10^6$

题解

显然这棵树上有很多点是不需要的,我们可以仿照建立虚树的方法,把需要的点拉出来建立一棵点数较少的树。因此我们需要知道某两个点的LCA,由于这棵树的性质,我们知道把一个点的编号除以它的最小质因数就到了它的父亲,所以对于两个点数,我们把他们分别质因数分解后把所有质因子从小到大排列,例如20和30,排列后为{2,2,5},{2,3,5},这是这一排列的最长公共后缀相乘得到的点就是他们的LCA,因为这是两个点不断向父亲移动最早可以到达的同一个点。对于本题,我们只需要对$1!,2!,3! \ldots m!$这几个点进行处理,当我们从$(i-1)!$进展到$i!$时,我们可以知道$i$有哪些质因子,然后我们发现$i$离他们的LCA的距离它的所有质因子个数和之前有的小于$i$最大质因子的个数,这个数量可以由树状数组查询得到,然后我们从$(i-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.1594878621.txt.gz · 最后更改: 2020/07/16 13:50 由 misakatao