2020牛客暑期多校第四场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 54/1112 | 4 | 7 | 10 |
A¶
upsolved by 2sozx
题意¶
给定一颗 \(n(n\le 2\cdot 10^5)\) 个节点， \(1\) 为根节点的树，设置 \(k\) 个关键点，定义一个点的值为这个点与根节点的路径中与这个点距离最近的关键点的距离，如果没有关键点则距离为 \(+\infty\) ，则这 \(k\) 个关键点的价值为每个点的值的最大值。对与所有 \(k\in [1,n]\) 找到一种设置关键点的方案使得价值最小，求 \(k=1\cdots n\) 的价值的最小值的和。
题解¶
我们考虑答案为 \(ans\) 时最少设置几个关键点，从树的最深处开始向上找第 \(ans\) 个祖先，将这个祖先的子树删除，并重复这个过程，删除的次数即为关键点的个数。可以用线段树维护即可。因此我们只需枚举 \(ans\) 即可在 \(O(n\log n)\) 时间内找到结果，最后统计一下答案即可。官方题解为枚举关键点的个数去二分答案计算，复杂度稍高。
这个官方题解复杂度是不是假的啊
B¶
solved by 2sozx
题意¶
\(f_c(x)=\max c\cdot f_c(gcd(i,x)) (i=1\cdots n-1,x>1),f_c(1)=1\)，\(T(T\le 10^6)\) 组询问，每组给出 \(n,c\) 求 \(f_c(n)\)
题解¶
显然将 \(n\) 每次都除以一个质因子就可以的到最后的答案，可以直接统计每个数可以除的次数，每个 \(c\) 用快速幂求一下即可。
C¶
upsolved by JJLeo
题意¶
给定字符串\(s\)，字符集为前\(10\)个小写字母。将任意一个子串求前缀最大值得到字符串\(a\)，问所有子串所得到的\(a\)的本质不同子串有多少个。\((|s| \le 10^5)\)
题解¶
考虑将可能的字符逆序放在广义后缀自动机上求本质不同字符串。计算每一位有可能是什么，当这一位是\(x\)时后一位是什么，从前往后扫一遍即可处理。然后从后往前直接枚举每一位可能是什么，然后向后一位对应字符的位置加点即可。
D¶
solved by 2sozx
题意¶
\(t\) 组数据，每组给出一串数字，将其分成非空的至少两组，求每组所组成的数字的最大值和最小值的差的最小值，注意数字不能含有前导零。序列长度 \(n\le10^5\)
题解¶
将每一位都成一组，显然答案 \(\le9\)，之后枚举分组的每组数字的长度即可，显然最长和最短位数一定 \(\le1\) ，因此枚举长度即可。如果恰好能均有同一长度构成，找到最大和最小相减一下即可。如果最长与最短的位数相差为 \(1\) ，那么位数长的一定为 \(10\cdots0a\)，位数短的一定是 \(9\cdots9b\) ，记录一下最后一位即可。再扫的过程中判断合法性和前导零即可。
E¶
upsolved by
题意¶
题解¶
F¶
solved by Bazoka13
题意¶
两条平行线，上端是\(A,B\)两点，下侧是\(C,D\)两点，给定\(AC,AD,BC,BD\)长度，确定四个点顺时针顺序
题解¶
根据到\(C,D\)的距离大小可以判断\(A\)与其中垂线的位置关系，如果不同侧直接可判，同侧就比较到同一点的长度，显然越长距离中垂线越远
G¶
upsolved by
题意¶
题解¶
H¶
solved by JJLeo
题意¶
将\(1\)到\(n\)两两分组，要求每组两个数不互质，问最多能分几组。
题解¶
首先将从\(3\)开始的质数\(x\)的所有倍数两两配对，如果多一个把\(2x\)留下来，最后把所有\(2\)的倍数没有配对的进行配对即可。
I¶
upsolved by JJLeo
题意¶
乱搞题，随机生成\(n\)个元素的分组情况，将两两元素是否属于同一个集合的信息告诉你，每个信息有\(\dfrac{1}{S}\)的概率是相反的，现在让你还原分组情况。
题解¶
将邻接矩阵存储，考虑两个点如果在同一集合那么那两行所有的\(1\)对应重合度应该是很高的，因此设一个阈值进行并查集合并即可。
J¶
upsolved by
题意¶
题解¶
记录¶
0min：分题，MJX发现B签到开冲
6min：MJX WA+2，CSK冲F
9min：CSK AC F
15min：MJX AC B，MJX ZYF 冲 H
32min：MJX ZYF WA+2 后找到正解
51min：ZYF AC H，MJX CSK ZYF冲D
233min：在疯狂 debug 中 AC D，后冲C
中途：大家一起来看I ，完全不懂这题在说啥。
till end：没了
after end：I乱搞，S没用，三人卒
总结¶
- MJX发病的第一天，模数写错，迭代器 \(i,j\) 写错，忘记初始化，出大问题。
- ZYF要加强乱搞题的训练和对广义后缀自动机的更多用法。
- CSK划水的第\(n\)天，出了个签到题就开始划水