2021牛客暑期多校第十场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 29/1015 | 4 | 10 | 11 |
A¶
solved by JJLeo 2sozx
题意¶
给你 \(n\) 个串，串长 \(\le100\) ，对于每个 \(i\) 寻找最少的字符串构成的集合使得前 \(i\) 个串都能在字符集中找到一个串为自己的前缀，\(i + 1 \sim n\) 个串都找不到这样的串，对每个 \(i\) 输出最小的字符集大小。空间32MB，\(n \le 10^5\)
题解¶
待脑子精神点写下。
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by
题意¶
题解¶
D¶
upsolved by 2sozx
题意¶
求 \(n\) 个有标号点所有树的直径和。(\(1 \le n \le 500\))
题解¶
考虑这样一种算直径的算法：每次删掉所有叶子直到剩不超过 \(2\) 个，设删了 \(x\) 次，如果最后剩了两个节点则答案为 \(2x+1\)，否则答案为 \(2x\)。
我们考虑这个算法的逆过程，不断加叶子，设 \(f_{i,j}\) 为 \(i\) 个点 \(j\) 个叶子的树数量。考虑转移，从 \(f_{i,j}\) 转移到 \(f_{i+k,k}\) 即为先选择 \(k\) 个点当叶子，之后将这 \(k\) 个叶子插到树上，必须保证原本的 \(j\) 个叶子都至少被插上一个叶子。
因此我们需要再处理出一个数组 \(g_{i,j,k}\) 表示其方案数，令 \(j\) 个旧叶子上各有一个新叶子作为关键叶子，最后只要有 \(j\) 个关键叶子就是合法的。考虑转移，如果这个新叶子是关键叶子，则其对应插的旧叶子有 \(j\) 种方案，删掉这个点后就是一个子问题，从而方案数为 \(j \times g_{i-1,j-1,k-1}\)；否则，这个点可以想插哪里插哪里，即为 \(i \times g_{i,j,k-1}\)。
那么 \(f\) 的转移即为：
考虑如何统计直径长度，设 \(h_{i,j}\) 为 \(i\) 个点 \(j\) 个叶子的树直径和。考虑上述 \(f\) 的转移，同样可以写出 \(h\) 的转移，随着叶子节点新增，新增了 \(g_{i-k,j-k,k}\) 个树，那么之前直径就需要再多算这么多次；而新增的叶子贡献 \(2\) 的数量，因此有：
总时间复杂度为 \(O\left(n^3\right)\)，需要特判只有一个点和两个点的情况。
E¶
upsolved by
题意¶
题解¶
G¶
upsolved by 2sozx
题意¶
\(n\) 个人每个人会随机向其它人开枪，成功概率是 \(p\)，求恰好有 \(k=0,1,\ldots,n\) 个人存活的概率。(\(2 \le n \le 3 \times 10^5\))
题解¶
给定 \(k\) 个人，设 \(f_k\) 是恰为这 \(k\) 个人死了的概率，\(g_k\) 是死的人恰是这 \(k\) 个人子集的概率。\(g_k\) 可以比较容易求出，每个人只要别打死这 \(k\) 个人之外的人即可，那么对于这 \(k\) 个人概率为 \(\dfrac{k-1}{n-1}+\dfrac{(1-p)(n-k)}{n-1}\)，对于其它 \(n-k\) 个人概率为 \(\dfrac{k}{n-1}+\dfrac{(1-p)(n-k-1)}{n-1}\)，从而有：
另有：
根据二项式反演，有：
可以通过卷积获得，最后存活 \(k\) 个人的答案即为 \(\dbinom{n}{k}f_{n-k}\)。
I¶
upsolved by 2sozx
题意¶
给 \(n\) 维超立方体黑白染色，要求一个点相邻的同色点不超过 \(\left\lceil\sqrt n\right\rceil\) 个，且黑白染色数量不能相同。(\(1 \le n \le 22\))
题解¶
当 \(n=1\) 的时候直接染两个黑色，下面考虑 \(n \ge 2\)。
令 \(m=\left\lceil\sqrt n\right\rceil\)，将长度为 \(n\) 的 \(01\) 串写成一个 \(m \times \left\lceil\dfrac{n}{m}\right\rceil\) 的矩阵，没有的位置补 \(0\)。
对 \(1\) 个数为奇数的，如果有一行是全 \(1\)，将其设为黑色 (设有 \(A\) 个)，否则为白色 (设有 \(B\) 个)。
对 \(1\) 个数为偶数的，如果有一行是全 \(1\)，将其设为白色 (设有 \(C\) 个)，否则为黑色 (设有 \(D\) 个)。
易得同色必然将一行多了一个 \(1\) 使其全 \(1\)，最多有 \(m\) 种可能，下面证明这样染色数不同，即 \(A+D \ne B+C\)。
首先 \(A+B=C+D=2^{n-1}\)，\(B+D=(2^{\left\lceil\frac{n}{m}\right\rceil+1}-1)^{n \bmod m}(2^{\left\lceil\frac{n}{m}\right\rceil}-1)^{m-n \bmod m}\) 是一个奇数，不妨设 \(B\) 是奇数，则 \(A\) 是奇数且 \(D\) 是偶数，所以 \(A+D\) 是奇数，因为 \(A+B+C+D=2^n\) 是 \(4\) 的倍数，所以 \(A+D\) 想等于 \(B+C\) 必须都是偶数，从而必然不等。
J¶
solved by Bazoka13 JJLeo
题意¶
给定一个凸包和凸包外一圈点，每个点会发光，照射到凸包上的一些边，问凸包所有边全被覆盖最少要找哪些点，输出方案。\(n\le 2\times 10^5\)
题解¶
套模板求的凸包外每个点的切线，然后跑一个最小的区间覆盖即可，赛场上用的是 \(ST\) 表跑的。
赛后学长提出了个 \(O(n)\) 扫的做法，还没实现。
K¶
upsolved by 2sozx
题意¶
给定起点，在 \(n \times m\) 的矩阵里面走 \(t\) 步，每次可以上下左右移动一步，不能走出边界，求方案数。(\(1 \le t,n,m \le 5 \times 10^5\))
题解¶
行列是独立的，设 \(f_t\) 和 \(g_t\) 是行和列走 \(t\) 步的方案数，最后答案即为：
现在考虑求 \(f_i\)，\(g_i\) 是完全同理的：
-
算法 1，直接 dp，设 \(F_{i,j}\) 是从起点走 \(i\) 步到 \(j\) 的方案数，则 \(f_i=\sum \limits _{j=1}^nF_{i,j}\)，时间复杂度为 \(O(nt)\)。
-
算法 2，考虑 \(F_{i,j}\) 的递推式，有 \(F_{i,j}=F_{i-1,j-1}+F_{i-1,j+1}\)，则 \(f_i=F_{i-1,1}+F_{i-1,n}+2\sum \limits _{j=2}^{n-1}F_{i,j}\)，从而有 \(f_i=2f_{i-1}-F_{i-1,1}-F_{i-1,n}\)，如果能快速求出 \(F_{i-1,1}\) 就好了，\(F_{i-1,n}\) 同理。
现在问题相当于数轴上从一个点出发，每次向左走向右走，最左最右不能超过边界，走 \(i\) 次到达一个定点的方案数。我们可以进行如下的容斥，先算出没有边界限制的方案数，再加上越过左边界和越过右边界的方案数，再减掉先越过左边界再越过有边界和先越过右边界再越过左边界的方案数，依次类推。
没有边界限制的方案数，很好算，就是一个组合数。之后越过左边界的方案数，考虑一个折线图，纵坐标是走到的位置，横坐标是走的步数，将第一次与左边界的位置之后和左边界对称，那么终点也会和左边界对称，可以发现每一条这样的折线都对应一条不合法方案，因此不合法方案即为将终点和左端点对称后不加边界限制的方案数。
右边界同理，先左后右则相当于先找到和第一个和左边界交点，再找到第一个和右边界交点，分别对之后的位置进行对称，这样终点也对称了两次，因此容斥过程就是不断来回对称，每次对称都会增加 \(n\) 的距离，因此至多进行 \(O\left(\dfrac{t}{n}\right)\) 次。
这样做时间复杂度就是 \(O\left(\dfrac{t^2}{n}\right)\) 的。
最后，对 \(n\) 进行根号分治，可以做到 \(O\left(t \sqrt t\right)\) 的时间复杂度。