2022 Beihang Spring Training 10¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 2/？ | 8 | 8 | 10 |
A¶
solved by JLK
题意¶
题解¶
签到，略
B¶
solved by TYB
题意¶
\(n\)个点的树，初始所有点为白色，进行以下操作直至所有点都为黑色：
\(\bullet\) 等概率随机选择一条路径，将路径上所有点染黑。
求期望操作次数。
\(n\le50\)
题解¶
显然要\(\min-\max\)容斥。
那么需要求出对于每个点集，将点集中至少一个点染黑的期望操作次数。
考虑怎么算这个东西。对于一个点集，它在树上将不在点集中的点分为了若干个连通块。设分为了\(k\)个连通块，第\(i\)个连通块大小为\(sz_i\)，那么不经过点集中任意一个点的路径条数为\(\sum_{i=1}^k\frac{sz_i(sz_i+1)}{2}\)。总的路径条数为\(\frac{n(n+1)}{2}\)，所以在一次操作中，将点集中至少一个点染黑的概率为\(1-\frac{\sum_{i=1}^ksz_i(sz_i+1)}{n(n+1)}\)，期望次数就是其倒数。
可以发现，我们只需要知道\(\forall j\in[0,\frac{n(n+1)}{2}]\)，使得\(\sum_{i=1}^k\frac{sz_i(sz_i+1)}{2}=j\)的选点集方案有多少。这个东西显然可以用树形背包算。\(f_{x,y,z,0/1}\)表示以\(x\)为根的子树，\(x\)所在连通块的大小为\(y\)，当前\(\sum_{i=1}^k\frac{sz_i(sz_i+1)}{2}=z\)，点集中有偶数/奇数个点（为了算容斥系数）的方案数。转移分两种情况，若\(x\)在点集中，那么要把儿子节点所在连通块的贡献加进\(z\)中；否则只需要把儿子节点所在连通的大小加进\(y\)中。
复杂度\(\mathcal{O}(n^6)\)，但常数很小，可以通过。
C¶
solved by YZW
题意¶
签到。
题解¶
略。
D¶
solved by TYB
题意¶
签到。
题解¶
略。
E¶
upsolved by YZW
题意¶
字符集 \(\Sigma\)，有串 \(S_0, T\) 以及 \(R_c (c\in\Sigma)\)，考虑以下迭代：
求 \(\min \{k\mid T\in S_{k}\}\) 或是判断不存在 \(k\) 满足条件。
\(|S_0|, |T|, \sum |R_c|\leq 1000\)，并且有 \(|R_c|\geq 2\)。
题解¶
容易发现对于一个字符 \(c\)，迭代至多 \(10\) 次后长度超过 \(|T|\)。
不妨假设 \(T\) 在 \(S_k\) 中出现，若 \(k>10\)，则 \(T\) 在 \(S_k\) 中出现的位置必定是由 \(S_{k-10}\) 中的一个或两个字符迭代产生的。此处的 \(k-10\) 是一个下界，也即可能由 \(k-9, k-8\) 中字符迭代产生。
预处理 \(trans_{x,c,p}\)，表示若之前匹配到 \(T\) 的第 \(p\) 个字符，接下来尝试继续匹配字符 \(c\) 迭代 \(x\) 轮后产生的字符串，最终会匹配到 \(T\) 的哪个字符。特殊地，不妨记完全匹配 \(T\) 时的值为 \(|T|\)。
BFS 求出每个字符以及每个字符对第一次出现的迭代次数。接下来分三种情况（原串迭代，单字符迭代，双字符迭代）求答案即可。
记 \(N=1000\)，时间复杂度 \(O(N^2\log N)\)。
F¶
solved by YZW
题意¶
Python 签到。
题解¶
略。
G¶
solved by JLK
题意¶
给定一棵\(n\)个点的树，用它生成一个新图，点集相同，新图里的边是树上两个点的距离。求两两作为起点和终点的最大流之和。
\(2 \le n \le 10^5,1 \le w_i \le 1000\)
题解¶
对于选定起点和终点的情况，结论是最大流为起点出边的流量之和与终点入边的流量之和较小值。
因为对于不是起点和终点的点，他们之间有很多流量，可以到处转移，最后一定能满足起点所有流量或者终点所有流量。具体不会证。
那么就只需要求出每个点到其他所有点的距离和即可，最后排序一遍计算每个点作为较小值的贡献。
\(O(n\log n)\)
注意爆long long
H¶
**solved/upsolved by **
题意¶
题解¶
I¶
solved by TYB
题意¶
略。
题解¶
不想写啥了。
J¶
solved by JLK
题意¶
给定一个随机数生成器，生成\(n\)个unsigned int，求两两lcm的最大值。
\(1 \le n \le 10^7\)
题解¶
由于是随机数，互质的概率比较大，只要取最大的若干个数枚举即可。
善用nth_element()。
\(O(n)\)
记录¶
JLK过A(0:10)，TYB过D(0:18)，YZW过C(0:35)。
JLK写J，TLE一次WA一次后AC(0:44)。
TYB写I，JLK猜了个G的结论。
TYB TLE了，换JLK写G。
JLK WA了，两边debug。
I一直在卡常，本地还是跑的比较慢，于是换写法。
G发现爆ll，改过了(1:58)。
I又WA了三次后过了(2:21)。
YZW过F(3:00)。
然后看BEH，TYB会一点B，但是感觉时间爆炸。后来JLK估错了时间复杂度，TYB冲过去了(4:43)。
总结¶
TYB：对拍的时候看一眼输出的数据，防止输出优化写错；能离散化就尽量不要用动态开点线段树；离散化注意去重；要在排序后去重。
JLK：背包常数好小
YZW：think twice, code once
Dirt¶
B(-1)
G(-1)
I(-5)
J(-2)