2020牛客暑期多校第九场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 52/975 | 6 | 10 | 12 |
A¶
solved by Bazoka13
题意¶
给一个\(2\)进制表达式，求出十进制结果
题解¶
使用\(python\)的\(eval+replace\)，一行\(AC\)
B¶
upsolved by JJLeo
题意¶
给出一棵以\(1\)为根的有根树，节点数为\(n\)，你需要做一次dfs，每一次经过一条边都要减少权值，第一次到每个点可以增加权值，要求任意时刻权值不为负，你可以在任意点花费任意秒增加对应的权值，经过边不耗费时间，问最少需要耗费多少秒。\((n \le 10^5)\)
题解¶
处理出以每个节点为根的子树中，如果以\(0\)权值进入那么全过程所处权值最小值的最大值\(a_i\)，以及子树权值和（边两次，点一次）\(b_i\)。进入某个节点，考虑合并，即遍历子树的顺序，先走\(b_i>0\)的，再走\(b_i<0\)的，前者按\(a_i\)从大到小排序，后者按\(b_i+a_i\)从大到小排序，最后答案是\(a_1\)，正确性证明过于离谱。注意进入每个点后要考虑这条父边的负边权，进入后可以获得这个点的权值，另外每个点回溯到父亲时也要再次考虑这条边的负边权。
C¶
upsolved by JJLeo
题意¶
给定\(n\)个区间\([l_i, r_i]\)，边界均为非负整数，每个区间有\(\frac{1}{2}\)的概率被选，求选择区间交集整点个数平方的期望，对\(998244353\)取模。\((1 \le n \le 5 \times 10^5, 0 \le l_i,r_i \le 10^9)\)
题解¶
首先注意并不是求区间长度，而是整点个数，因此离散化时右端点要加一。
其次考虑如果求整点个数之和的期望怎么做，只需要离散化后扫一遍确定每个区间被覆盖了几次即可，设离散化后的一个区间出现了\(x\)次，该区间的整点个数为\(y\)，则对分子的贡献为\(y(2^{x}-1)\)，最后除以分母的\(2^n\)即可。
而本题需要求平方的期望，因此对于离散化后的一段区间，不能仅仅单独考虑它自己，还要考虑当它是交集一部分时与其它同处于交集一部分区间互相之间形成的贡献。例如对于一段区间整点个数的平方和可以进行如下分解
因此对于每一个离散化后的区间\(i\)来说，若考虑所有覆盖它的原始区间，可以得到离散化后的所有区间各被覆盖了多少次，设一个区间被覆盖次数为\(x\)，整点个数为\(y\)，则区间\(i\)对于分子的贡献即为
整个过程使用线段树来一遍扫描线，线段树维护每一段整点个数乘以权值（因此区间加的时候要乘以整点个数），通过\(\times 2 + 1\)与\(-1\times \frac{1}{2}\)即可完成对上述值的维护。最后除以分母的\(2^n\)即可。
D¶
upsolved by JJLeo
题意¶
给定一棵\(n\)个点的树，\(i\)号点上有\(i\)号人，第\(i\)条边只能允许\([l_i,r_i]\)的人通过，每个人可以强行走\(k_i\)次不允许走的边，问\(i\)号人能到达点的个数。\((2 \le n \le 10^5, 0 \le k_i \le 1)\)
题解¶
首先dfs一次确定所有点的父亲以及深度。接下来上线段树分治，启发式合并维护一个比较特殊的并查集，每个并查集里面是一个连通块，除了常规的fa和siz，还要维护连通块最浅点以及所有“儿子”的siz之和。最后答案如果\(k_i=0\)则直接返回siz否则返回siz加上最浅点父亲所在连通块大小以及所有儿子的siz之和。可以发现这几个东西都是可以撤销的，细节比较多，一定要注意每个量的具体含义以及操作的顺序。
E¶
solved by 2sozx
题意¶
求 \(\prod_{i=a}^{b}\prod_{j=c}^{d}gcd(x^i,y^j)\)，\(0\le a,b,c,d\le 3 \cdot10^5，0<x,y\le10^9\)
题解¶
先求出 \(x,y\)的所有公共质因数，枚举公共质因数 \(p\) ，考虑 \(p\) 在 \(x,y\) 中的最高次方 \(m,n\) ，枚举 \(i\in[a,b]\) ，\(j\) 的贡献可以表示为一个等差数列和多个 \(m^i\) 的和，可\(O(1)\)算出，总复杂度 \(O(a\log(x))\)
F¶
solved by JJLeo
题意¶
给定一个序列，每个数有一种颜色，现在选出任意个数使得这个序列中拥有全部颜色且选出元素的最大值与最小值的差值最小。
题解¶
滑动窗口滑就完事了。
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by 2sozx
题意¶
定义字符集大小为 \(m\) ，每一个字符有权值，定义一个字符串的值为所有字符权值的乘积。现给定一个字符串长度为 \(n\)，问添加不超过 \(k\) 个字符，所得到的所有字符串的值的和，答案模 \(998244353\)。\(n,m\le10^5,k\le10^5\)
题解¶
考虑随意向给定的字符串中添加字符，如给定字符串 \(123\)，向其中添加字符，共有 \(n+1\) 个位置可以添加字符，每个位置有 \(m\) 种方式，考虑去重。显然 \(1+123\) 和 \(1+1+23\) 是相同的情况，我们让 \(a_i\) 和 \(a_{i+1}\) 之间不能添加字符 \(a_{i+1}\) 即可去重，\(a_1\) 前不可添加字符 \(a_1\)。
令字符的权值分别为 \(b_i\)，和为 \(sum\)，\(a_i,a_{i+1}\) 间隔中若放 \(s\) 个字符即可对答案造成 \(g(i+1)=(sum-b_{a_{i+1}})^s\) 的贡献，最后一个字符后则可造成 \(g(n+1)=sum^s\) 的贡献。
考虑总计添加不超过 \(k\) 个字符，容易看出可以通过生成函数解决这个问题。每个间隙的生成函数即为 \(\sum_{i=0}^{\infty}g(j)^ix^i=\frac{1}{1-g(j)x}\) ，总的生成函数即为 \(\prod_{i=1}^{n+1}\frac{1}{1-g(i)x}\) ，对分母分治\(NTT\) 再求逆即可，前 \(k\) 项系数和再乘原串本身的贡献即为答案。
I¶
solved by 2sozx Bazoka13
题意¶
题解¶
J¶
solved by JJLeo
题意¶
给定一个\(n \times m\)的\(01\)矩阵，求有多少个子矩阵满足四边都是\(1\)，中间部分\(01\)数量相差不超过\(1\)，且长宽均大于\(1\)。\((n,m \le 500)\)
题解¶
考虑枚举两列，保证两列都是\(1\)的情况下（否则清空），维护一下全\(1\)行及其前缀和，从上往下扫一遍即可。
K¶
solved by JJLeo
题意¶
给定一棵树，两个人各在一个节点，前者以\(2m/s\)追后者，后者以\(1m/s\)速度逃离，每条边长度为\(1m\)，问最晚多久才被抓。
题解¶
以追人那个人为根dfs，枚举最后逃到哪个点，算一下距离讨论是否合法即可。
L¶
upsolved by
题意¶
题解¶
记录¶
0min：开局分题
1min：MJX 发现A签到但不会写，和CSK看I
28min：CSK AC I，冲A，MJX看E
36min：CSK AC A，MJX冲E，CSK ZYF看F
60min：MJX AC E，看B，ZYF冲F
72min：ZYF AC F，CSK,ZYF冲K，MJX 看B，J
114min：ZYF AC K，一起看B,J
189min：ZYF WA B，换看J
225min：ZYF AC J
till end：B疯狂RE，未解之谜
总结¶
- MJX：要勇于看还没看过的题
- CSK：貌似非\(C++\)题还是会暂时蒙古一会？多学习\(java python\)节省时间的特性，同时注意复杂度
- ZYF：不要纠结于一道题上太久，贪心没思路时要敢于发挥想象力。