2021牛客暑期多校第六场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 37/1100 | 5 | 11 | 11 |
A¶
solved by Bazoka13
题意¶
给你一堆半平面以及半平面的移动方向，每秒半平面会向这个方向移动一个单位，\(q\) 组询问，每组询问时间 \(t\) 后半平面交的面积。\(n\le 10^3, q \le 10^5, t\le 10^5\)
题解¶
我们会发现随着时间的增加，半平面中有的边就会被缩成一点，因此我们可以 \(O(n^2\log n)\) 预处理出来哪些时间节点半平面会被缩小一点。对于每个询问我们就可以 \(O(\log n)\) 确定他此时的半平面的的形状。由于在这个时间里不会有缩点的情况，因此我们可以让每个边暴力向里缩一个矩形，再减掉与相邻边形成的四边形面积即可。
B¶
upsolved by JJLeo 2sozx
题意¶
给定一个图，每条边有个出现概率 \(P_{i,j}(t) = q_{i,j} + (p_{i,j} - q_{i,j})a^{-(t-1)}\)。其中 \(a\) 是定值，保证 \(p_{i,j} - q_{i,j} \ne 0\)。
设 \(F(i)\) 是 \(t=i\) 时生成树个数的期望，求 \(\sum \limits _{i=1}^t F(i)\)。
询问 \([1, t]\) 时原图的生成树个数的期望和是多少。(\(1 \le n \le 300\)，\(0 \le m \le \dfrac{n(n-1)}{2}\)，\(1 \le t \le 10^8\))
题解¶
考虑矩阵树定理，对于特定的 \(t\)，将每条边的概率作为权值，那么矩阵树定理求出的就是每种生成树出现的概率的和，也就是生成树个数的期望，因此得到了一个 \(O(tn^3)\) 的做法。
考虑设 \(a^{-(t-1)}=x\)，直接带着 \(x\) 求行列式，最终能得到一个多项式，再把 \(a^{-(t -1)}\) 反带回来，可以发现每一项都是一个等比数列的形式，因此利用公式对 \(1\) 到 \(t\) 求和即可。
对于新的行列式 (删掉最后一行最后一列的基尔霍夫矩阵)，我们设其为 \(|xK+B|\)，由于 \(p_{i,j} - q_{i,j} \ne 0\)，如果将 \(p_{i,j} - q_{i,j}\) 作为每条边的边权那么生成树存在的概率必然不为 \(0\)，从而 \(|K| \ne 0\)，那么一定可以把 \(K\) 初等行变换到 \(I\)，我们对 \(B\) 做同样的变化，设行列式因为初等行变化的变化量为 \(C\)，则只需求 \(C|xI+A|\)，其中 \(A\) 是 \(B\) 经过相同初等行变换得到的。
\(|xI+A|\) 和特征多项式类似，可以 \(O(n^3)\) 将其化为上海森堡矩阵，再用 \(O(n^3)\) 求出特征多项式，具体如下：
首先和 \(A\) 相似的矩阵特征多项式相同：
\[ \begin{aligned} &|xI-P^{-1}AP| \newline =&|P^{-1}xP-P^{-1}AP| \newline =&|P^{-1}(xI-A)P| \newline =&|P^{-1}||xI-A||P| \newline =&|P^{-1}||P||xI-A| \newline =&|P^{-1}P||xI-A| \newline =&|xI-A| \newline \end{aligned} \]因此我们考虑将 \(A\) 相似到一个方便求特征多项式的矩阵，上海森堡矩阵 \(B\) 的定义为：
- 对于所有 \(i \ge j + 2\)，\(B_{i,j}=0\)。
我们先考虑如何将 \(A\) 为相似上海森堡矩阵：
因为是相似，所以每次初等行变换相当于右乘一个初等方阵，需要再左乘一个它的逆，三种初等方阵的逆方阵效果如下：
右乘 \(P\) 效果 左乘 \(P^{-1}\) 效果 交换第 \(i\) 行和第 \(j\) 行 交换第 \(j\) 列和第 \(i\) 列 第 \(i\) 行乘以 \(a\) 第 \(i\) 列乘以 \(a^{-1}\) 第 \(i\) 行乘以 \(a\) 加到第 \(j\) 行上 第 \(j\) 列乘以 \(-a\) 加到第 \(i\) 列上 对于第 \(i\) 列，我们用 \(A_{i,i+1}\) 把 \(A_{i,j}\) (\(j > i+1\)) 全部消成 \(0\)，每进行一次初等行变换，立刻进行依次对应的初等列变换，注意我们每次都是操作第 \(i+1\) 行和第 \(j\) 行，因此初等列变换只会影响第 \(i+1\) 列和第 \(j\) 列，其中 \(j>i+1\)，因此不会影响到第 \(i\) 列。
这样我们就在 \(O(n^3)\) 的时间内相似到了上海森堡矩阵 \(B\)，设 \(f_{i}\) 是其 \(i\) 阶顺序主子式，其中 \(f_1=B_{1,1}\)，我们依次计算 \(f_2,f_3,\ldots,f_n\)：
对于 \(f_i\)，按第 \(i\) 行展开，第 \(i\) 行只有两个数，如果选 \(B_{i,i}\)，那么剩下的即为 \(f_{i-1}\)，否则只能选 \(B_{i,i-1}\)，那么第 \(i-1\) 行也只剩两个数，如果选 \(B_{i-1,i}\)，那么剩下的即为 \(f_{i-2}\)，否则继续递推，枚举第一个选 \(B_{j,i}\) 的 \(j\) ，那么剩下的的即为 \(f_{j-1}\)，注意要乘上展开定理中的 \(-1\)。
其中只有对角线上有 \(x\)，其它都不带 \(x\)，因此递推的总复杂度为 \(O(n^3)\)。
最后，此题 corner case 不少，等比数列求和时注意公比是否为 \(1\)，并且 \(m = 0\) 时按照题意的定义是没有生成树的。
C¶
upsolved by 2sozx
题意¶
\(n\) 个点的完全图，每次可以删除一个三元环，问怎么删能让剩余的边小于 \(n\) 条。\(3\le n \le 2000\)
题解¶
删掉所有 \(i + j + k \equiv 0 \bmod n, 1 \le i < j < k\le n\)
证明：
-
\(i + j + k = n\) 时 $$ \sum_{i = 1}^{\lfloor\frac{n}{3}\rfloor}\lfloor\frac{(n - 3 * i)-1}{2}\rfloor $$
-
\(i + j + k = 2n\) 时 $$ \sum_{i = 1}^{\lfloor\frac{2n}{3}\rfloor}\lfloor\frac{(2n - 3 * i)-1}{2}\rfloor - \sum_{k = n + 1}^{2n - 3}\lfloor\frac{(2n - k)-1}{2}\rfloor $$
-
易证这两个条件下 \((i, j, k)\) 一定不相等
D¶
upsolved by JJLeo 2sozx
题意¶
一个数开始为 \(0\) ，每次随机选择一个 \(y\in[0, n]\)，如果 \(x\oplus y > x\) ，则 \(x = x\oplus y\) ，否则 \(x\) 不变，当 \(x = n\) 时停止操作，问期望操作多少次。
\(n = 2^k - 1\) ，每个数的概率通过题目给出，答案 \(\bmod 10^9 + 7\)。(\(2 \le n \le 2^{16}\))
题解¶
考虑一个推期望的式子
$$ E(x) = (E(x) + 1)S(x) + \sum_{x\oplus y > x} (E(x\oplus y) + 1)p_y\ S(x)=\sum_{i \le x} p_i $$ 化简可以得到
答案可以通过 cdq 分治计算，对于一层的计算，首先计算右半的答案，然后用 FWT 转移到左侧即可。
注意同一层中前缀相同，因此 FWT 的长度可以相应减少，从而复杂度是 \(O(n \log ^2 n)\) 的。
E¶
upsolved by JJLeo 2sozx
题意¶
起始有一个树根，每次操作选择一个节点 \(u\) 生成一个颜色为 \(c\) 的叶子结点，或者询问节点 \(u\) 子树中颜色为 \(c\) 的节点个数，强制在线。\(c, q\le 5\times 10^5\)
题解¶
通过 dfs 序转化成序列问题，只不过我们通过改变 dfs 顺序使得这个序列比较好维护。
具体来说，维护每个点子树 dfs 序中最后一个点的下一个点 \(\textit{end}\)，以及其第一个儿子。 这样，每次新增把新点当作 \(u\) 的一个新儿子即可，每个点的 \(\textit{end}\) 永远不变，新增时为其初始化为下一个点即可。
将每个点的值映射到 long long 值域内，使用替罪羊树维护每个点的权值，一旦不平衡就重构。
替罪羊树的重构不影响节点间的相对位置，因此我们只需要对每个颜色维护一个平衡树，每次加点的时候向对应颜色的平衡树加点即可，查询即为找到依靠 \(\textit{end}\) 找到对应区间进行区间查询即可。
模板里 KDTree 重构没有中序遍历，因为本来就是乱搞，这里不是乱搞是正经的排序，要中序遍历。
F¶
solved by JJLeo 2sozx Bazoka13
题意¶
西内
题解¶
西内
G¶
solved by JJLeo 2sozx
题意¶
设 \(G(n)\) 是这样一张有向图，除了点 \(n\) 外每个点都有入度，且边 \((i,j)\) 存在当且仅当 \(i=pj\)，其中 \(p\) 是质数。
\(G(12)\) 如下：
现在给定 \(n\)，求 \(G(1),G(2),\ldots,G(n)\) 的边数之和。(\(1 \le n\le10^{10}\))
题解¶
点 \(i\) 出现在 \(G(n)\) 当且仅当 \(i \mid n\)，且点 \(i\) 的出度在任意 \(G(n)\) 都是相同的，因此我们可以在每条边的初始点来计算它，显然点 \(i\) 的出度为 \(w(i)\)，即 \(i\) 的不同质因子个数，因此答案为： $$ \sum_{i = 1}^{n} \left\lfloor\dfrac{n}{i}\right\rfloor w(i) $$ 考虑如何计算 \(w(n)\)，考虑每个质因子的贡献，即为： $$ \sum_{\text{p is a prime}} \left\lfloor\dfrac{n}{p}\right\rfloor=\sum_{i=1}^n [\text{i is a prime}]\left\lfloor\dfrac{n}{i}\right\rfloor $$ 我们用 min_25 筛算出 \(n\) 的整除分块点的质数个数和，也就是 \(\sum \limits _{i=1} ^ n [\text{i is a prime}]\)，那么上式即可用数论分块来解决。这样对于 \(n\) 的每个整除分块点都需要再用一次整除分块，因此时间复杂度为 \(O\left(\sum \limits _{i=1}^n \sqrt{ \dfrac{n}{i}}\right)=O\left(n^{\frac{3}{4}}\right)\)，利用杜教筛均摊的技巧，我们可以线性筛预处理出前 \(O\left(n^{\frac{2}{3}}\right)\) 的 \(w(n)\)，对剩下的用整除分块，这样复杂度就是 \(O\left(n^{\frac{2}{3}}\right)\) 了。
另外，还要加上 min_25 筛第一部分的复杂度。
J¶
upsolved by JJLeo 2sozx
题意¶
一个无向连通图，如果联通块个数为奇数，则这个联通块 \(C\) 贡献为 \(-\sum\limits_{i\in C}a_i\) ，否则贡献为 \(\sum\limits_{i\in C}a_i\)，可以任意删除边，问总体最大贡献是多少。\(n\le 10^6, a_i\le 10^9, m\le 10^6\)
题解¶
2sozx's solution¶
联通块大小为偶数的不用考虑。
联通块大小为奇数时，我们可以证明一定只删除一个点最优。考虑删除哪个点，如果点非割点，则可以任意删除，否则看这个割点链接的其余联通块是否全为偶数，如果全是偶数则可以删除，否则不可以删除，复杂度为 \(O(n)\)。
判断割点其余联通块是否为偶数时可以在 \(tarjan\) 判断割点的时候直接进行判断。
JJLeo's solution¶
\(n\) 为偶数时不需要删边。
否则，对于任意一种方案，一定可以将其变为将其中奇数个点拆成孤立点，剩下连通块中的边不动。
可以证明最优方案只需要选择一个点将其变为孤立点：
考虑建出圆方树，将选择的孤立点拿出来建虚树，显然如果只选择一个叶子节点也是合法的，且其中一部分之前还删掉了一些点，而选择它们在一起组成一个偶数连通块，因此答案更优。
因此，我们建出圆方树，依次考虑每个点删掉后的答案即可。只需要考虑删掉这个点后剩下连通块都是偶数个点的那些点，当然就算全考虑答案也是对的，因为其它情况答案一定不优。
K¶
upsolved by JJLeo 2sozx
题意¶
一棵 \(n\) 个节点的树，\(m\) 次询问，问一条链不可以选择相邻的点的权值和最大是多少。\(n \le 5 \times 10^5, m\le 10^7\)
题解¶
这个问题显然可以用线段树做，维护两端选 / 不选的最大值进行合并，链可以用然后用重链剖分解决，复杂度是 \(O(m\log^2n)\) ，但是此题 \(m\) 过大，显然是要 \(O(1)\) 询问。
本题即为猫树在点分树上的拓展，求出每个点到点分树上每个祖先的 (不考虑祖先的) 两端选 / 不选的最大值，之后每次询问找到这两点在点分树上的 lca，显然这是它们路径上的一个点，用预处理出来的值 \(O(1)\) 合并即可。
求 lca 要用欧拉序 + ST 表来预处理。总复杂度为 \(O(n\log n + m)\)。
记录¶
0h：开始看I，ZYF想了想直接秒了，看大家都过了F，CSK ZYF看F，MJX看H，想了半天F，不会做，CSK开始直接冲A的板子暴力，MJX喂ZYF H，ZYF直接开写扫描线开冲。CSK数组开小了，然后发现暴力确实会T(只能说几何常数起飞)。ZYF写完WA了，开始De
1h：ZYF和MJX观察ZYF代码，太tm对了，MJX开始写垃圾对拍，虽然对拍完全不对，但是找到了错误的数据(x)。CSK改了改常数继续冲A模板暴力。ZYF发现就最后输出的横纵坐标反了，其它完全正确，寄！
2h：自闭F，ZYF写了个完全假的F，然后开始和出题人对线
3h：前半小时继续对线，后半小时开始换题，考虑G，MJX和ZYF开始疯狂讨论，搞了个式子出来，不会优化。然后开始测暴力的复杂度(x。ZYF把复杂度写出来，发现就是没有优化的杜教筛的复杂度，想到直接前 \(n^{\frac{2}{3}}\) 预处理复杂度就完全正确了，直接开冲。
4h：ZYF过了，然后发现F太傻逼了，CSK继续改A，ZYF先写F，直接过了。开始二分A的范围，冲冲冲！
总结¶
输出一定不要反
MJX对拍写的准点（x
Dirt¶
A(+10)：开始给了两发暴力，常数大寄了，数组还开小了，然后二分的返回值错了，但是过了大多的样例，最后TLE因为二分次数太多了(罚的好啊，+100都行)
H(+1)：经典x, y写反了