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 _{i=1}^{t}F(i)$。

询问 $[1,t]$ 时原图的生成树个数的期望和是多少。($1\le n\le 300$，$0\le m\le {\displaystyle \frac{n(n-1)}{2}}$，$1\le t\le {10}^8$)

题解

考虑矩阵树定理，对于特定的 $t$，将每条边的概率作为权值，那么矩阵树定理求出的就是每种生成树出现的概率的和，也就是生成树个数的期望，因此得到了一个 $O(t{n}^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{array}{rl}& |xI-P^{-1}AP|\\ =& |P^{-1}xP-P^{-1}AP|\\ =& |P^{-1}(xI-A)P|\\ =& |P^{-1}||xI-A||P|\\ =& |P^{-1}||P||xI-A|\\ =& |P^{-1}P||xI-A|\\ =& |xI-A|\end{array}$$

因此我们考虑将 $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,\dots ,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 0modn,1\le i<j<k\le n$

证明：

• $i+j+k=n$ 时 $$\sum _{i=1}^{\lfloor \frac{n}{3}\rfloor }\lfloor \frac{(n-3\ast i)-1}{2}\rfloor$$

• $i+j+k=2n$ 时 $$\sum _{i=1}^{\lfloor \frac{2n}{3}\rfloor }\lfloor \frac{(2n-3\ast 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$ ，每个数的概率通过题目给出，答案 $mod{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$$ 化简可以得到

$$E(x)={\displaystyle \frac{1+\sum _{x\oplus y>x}E(x\oplus y)p_y}{1-S(x)}}$$

答案可以通过 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 序中最后一个点的下一个点 $\mathit{\text{end}}$，以及其第一个儿子。 这样，每次新增把新点当作 $u$ 的一个新儿子即可，每个点的 $\mathit{\text{end}}$ 永远不变，新增时为其初始化为下一个点即可。

将每个点的值映射到 long long 值域内，使用替罪羊树维护每个点的权值，一旦不平衡就重构。

替罪羊树的重构不影响节点间的相对位置，因此我们只需要对每个颜色维护一个平衡树，每次加点的时候向对应颜色的平衡树加点即可，查询即为找到依靠 $\mathit{\text{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),\dots ,G(n)$ 的边数之和。($1\le n\le {10}^{10}$)

题解

点 $i$ 出现在 $G(n)$ 当且仅当 $i\mid n$，且点 $i$ 的出度在任意 $G(n)$ 都是相同的，因此我们可以在每条边的初始点来计算它，显然点 $i$ 的出度为 $w(i)$，即 $i$ 的不同质因子个数，因此答案为： $$\sum _{i=1}^n\lfloor {\displaystyle \frac{n}{i}}\rfloor w(i)$$ 考虑如何计算 $w(n)$，考虑每个质因子的贡献，即为： $$\sum _{\text{p is a prime}}\lfloor {\displaystyle \frac{n}{p}}\rfloor =\sum _{i=1}^n[\text{i is a prime}]\lfloor {\displaystyle \frac{n}{i}}\rfloor$$ 我们用 min_25 筛算出 $n$ 的整除分块点的质数个数和，也就是 $\sum _{i=1}^n[\text{i is a prime}]$，那么上式即可用数论分块来解决。这样对于 $n$ 的每个整除分块点都需要再用一次整除分块，因此时间复杂度为 $O\left(\sum _{i=1}^n\sqrt{{\displaystyle \frac{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 _{i\in C}{a}_i$ ，否则贡献为 $\sum _{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 }^{2}n)$ ，但是此题 $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写反了