2021牛客暑期多校训练营6¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 46/1100（校内3/19） | 4 | 11 | 11 |
A¶
upsolved by JLK
题意¶
给定逆时针凸包上的\(n\)个点，第\(i\)个点到第\(i\%n+1\)个点为一个半平面。每过一秒，所有半平面会向自己的方向移动一个单位（也就是全部往面积缩小的方向移动）。\(q\)个询问，每次询问\(t\)秒后的凸包面积。
\(1 \le n \le 10^3,1 \le q \le 10^5\)
题解¶
在半平面移动的过程中，会有一些半平面在某个时刻后完全被另外两个半平面盖住。而且这样的情况一定发生在相邻的三条直线之间。即：中间的直线被两边的直线挤压，直至消失。
那么考虑按时间从小到大维护这个凸包。对每三个相邻的直线求出中间直线被覆盖的时刻，然后就可以维护了。
具体来说，两条直线的交点的移动轨迹在他们的角平分线上，对相邻的两条角平分线求交点就是中间直线被覆盖的点。在计算这个交点时，也可以得到到达这个点的时刻。按被覆盖的时刻从小到大删除。
删除了一条直线之后，相当于把这条直线的两边合并，会有两个新的直线组，再计算他们的删除时刻。显然，在删除中间直线之后，两侧直线的角平分线就是之后的交点运动轨迹，而且这个点在中间直线被完全覆盖的时候，恰好在中间直线上。直接当做一开始就没有中间直线来算就行了。
每次取时刻最小的可以用堆维护，每条直线的前驱、后继可以用链表维护。
现在考虑计算面积。在两次删除中间，凸包的形状是一样的。面积的减量可以看做是若干梯形和三角形组成。根据面积公式，只需要维护周长的变化即可。不难发现，在求角平分线的时候，可以顺便求出对于这个角，移动一个单位会减少多少周长。对所有的角维护一个减量和即可。
注意在删到只剩两个点以后，答案都是0。以及要避免删除重复的直线，这可以用一个数组来标记删除的直线，并在每次删除时检查堆里的时刻和最新的更新的时刻是否对得上（因为有可能被旁边的直线删除而影响）。
对于询问，可以采取二分找到最近的关键时刻，或者排个序然后随着删除直线而计算答案。
\(O((n+q)logn)\)
B¶
upsolved by YZW
题意¶
给出 \(n\) 个点 \(m\) 条边的无向图。
总共有 \(t\) 天，在第 \(i\) 天中第 \(j\) 条边出现的概率为 \(q_j+(p_j-q_j)a^{-(i-1)}\)，\(a\) 为给定常数。
每天的贡献为当天可以取到的不同生成树个数，求 \(t\) 天贡献之和的期望对 \(998244353\) 取模的结果。
\(1\leq n\leq 300\)，\(1\leq t\leq 10^8\)，\(1\leq a\leq 10^8\)，\(0\leq p_j,q_j\leq 1\)，\(p_j\neq q_j\)
题解¶
线性代数题（确信
对于第 \(i\) 天，设 \(\lambda=a^{-(i-1)}\)，边出现的概率即为 \(q_j+(p_j-q_j)\lambda\)，在模 \(998244353\) 意义下为整数，可视为两点之间有对应整数条边。
由 Matrix-Tree 定理，可以求得度数矩阵减邻接矩阵即为 Kirchhoff 矩阵 \(M\)，\(\det M\) 即为第 \(i\) 天的贡献。
将含 \(\lambda\) 项与不含 \(\lambda\) 项分写，分别得矩阵 \(B\) 与 \(A\)，此时有 \(M=\lambda B+A\)，并且由于 \(p_j\neq q_j\)，若无向图联通则 \(B\) 一定满秩。
于是 \(\det M=\det (\lambda B+A)=\det B\cdot \det B^{-1}(\lambda B+A)=\det B\cdot \det \left(\lambda I-(-B^{-1}A)\right)\)。
\(\det B\) 可以直接通过初等变换在 \(O(n^3)\) 内求得，而 \(\det \left(\lambda I-(-B^{-1}A)\right)\) 为 \(-B^{-1}A\) 的特征多项式 \(\varphi(\lambda)\)，利用 Upper Hessenberg 矩阵 可在 \(O(n^3)\) 内求得。
\(t\) 天的贡献之和即为 \(\det B\sum_{i=1}^t \varphi(a^{-(i-1)})\)，对于 \(\varphi(\lambda)\) 的每一项，其对答案的贡献均为 \(t\) 项的等比数列之和，求和即可得到答案。
注意 corner case：\(a\) 可能等于 \(1\)，此时需要特判；\(n=1\)，\(m=0\) 时答案为 \(0\)。
\(O(n^3)\)
C¶
upsolved by YZW
题意¶
有 \(n\) 个点的完全图，每次删去一个三元环，需要你把它删到只剩下少于 \(n\) 条边，输出方案。
\(3\leq n\leq 2000\)
题解¶
我们希望能构造一个与 \(n\) 有关的满足交换律的二元运算 \(\circ\)，使得对于绝大部分 \(0\leq i,j,k< n\) 有：
- \(i\circ j=k\)
- \(i\circ k=j\)
- \(j\circ k=i\)
构造 \(i\circ j=\begin{cases}n-i-j&,i+j\leq n\\2n-i-j&,i+j>n\end{cases}\)
依次枚举 \(i,j\)，若三元环 \(i,j,i\circ j\) 存在就将其删去，注意此处的顶点编号是 \(0\)-indexed 的。
不会证，但是能 AC。
\(O(n^2)\)
D¶
upsolved by TYB
题意¶
一个游戏，开始时拥有的数是\(0\)，目标是将其变为\(2^k-1\)，每次随机以\(p_i\)的概率生成一个\([0,2^k)\)的数\(i\)，设当前拥有的数是\(x\)，若\(x\bigoplus i>x\)，则将\(x\)变为\(x\bigoplus i\)，否则不变，求到达目标的期望次数。
\(k\le 16\)
题解¶
设\(f_x\)为\(x\)开始到结束的期望次数，容易写出转移方程： $$ f_x=1+\sum_{y>x}f_yp_{x\bigoplus y}+\sum_{y\le x}f_xp_{x\bigoplus y} $$ 化简一下可以得到： $$ f_x=\frac{1+\sum_{y>x}f_yp_{x\bigoplus y}}{\sum_{y>x}p_{x\bigoplus y}} $$ 那坨东西是个异或卷积的形式，容易想到用FWT之类的东西处理，但是有大小关系的限制。这时候有个套路是用分治来处理大小关系，类似分治FFT，对于\([l,r]\)，先求出\([mid+1,r]\)这一段\(f\)的值，在考虑它们对\([l,mid]\)的影响，最后再递归\([l,mid]\)这个区间。设一开始是第\(0\)层，当分治到第\(i\)层的时候，\([l,r]\)这个区间的数二进制下前\(i\)位是完全相同的，所以可以不用每次都做满的FWT，复杂度是正确的，为\(O(2^kk^2)\)。
E¶
upsolved by JLK
题意¶
动态维护一棵树，每个点有颜色。修改为在把一个新点（自带颜色）接到一个已经存在的点。询问为求出一个点子树内给定颜色的点数。一开始只有一个点，有\(m\)个操作。
\(1 \le m,color \le 10^5\)
题解¶
如果能够维护dfs序的大小关系，那么就可以把每种颜色扔到对应平衡树上的指定位置，查询也可以直接在平衡树上查找了。
现在考虑如何维护dfs序的大小关系。首先肯定要把一个点拆成首尾两个点，一个代表子树dfs序的开始，一个代表子树dfs序的结尾。现在就是要在插入点的同时维护dfs序。
Sol.1¶
块状链表维护dfs序。修改\(O(\sqrt m)\)，每次查找指定点的dfs序\(O(1)\)。总复杂度为\(O(m\sqrt m+mlogm)\)（据出题人说这种做法被卡了）。
Sol.2¶
std做法：用替罪羊树维护。一种普通的想法是，每次插入一个点，他的dfs序是树上相邻的两个点的dfs序的平均数。但这样显然会变成很小的小数，在极端数据下一定会炸。但是如果用替罪羊树对所有点dfs序的映射不断重构，在值域够大的情况下，肯定能保证每个数都是整数。
把初始值域设置为\([0,10^{18}]\)，每次插入到替罪羊树，如果有两个点挨的很近，子树就会不平衡，会触发重构。
这样插入\(O(logm)\)，查询dfs序\(O(1)\)，总复杂度为\(O(mlogm)\)。
Sol.3¶
这是参考逆十字队的做法，比较巧妙。
其实dfs序的相对大小是可以用倍增维护的。对于一个点，钦定子树的dfs序顺序取决于儿子的编号（即编号较小的儿子所在的子树拥有较小的dfs序）。
判断dfs序相对大小，可以先判断一个点是另一个点祖先的情况。如果不是祖先关系，那么跳到LCA的下一层，判断LCA的儿子的编号大小关系。
稍微更改一下判断条件，就可以判断一个点是不是在子树结尾的dfs序前，是不是在子树开头的dfs序前。那么询问也类似了。
插入\(O(logm)\)，查询dfs序大小关系\(O(logm)\)，总复杂度为\(O(mlog^2m)\)，但是实现较为方便。
Sol.4¶
更为暴力的一种方法，但实际上有人通过了。定期重构这棵树，然后对（颜色，dfs序）这样的二元组排序，询问的时候二分。对于还没重构的操作就暴力判断。
调整块大小可以做到\(O(m\sqrt{mlogm})\)。
F¶
solved by YZW&TYB
题意¶
有\(n\)块牛排\(m\)口锅，第\(i\)块牛排需要烤\(t_i\)时间，每块牛排可以选择在一口锅烤\(t_i\)，或者在两口锅分别烤\(a_i\)、\(b_i\)，\((a_i,b_i>0,a_i+b_i=t_i)\)，注意\(a_i\)与\(b_i\)的时间段不能有重叠，即一块牛排不能同时在两口锅上烤。求烤完所有牛排的最短时间并给出一组方案。
\(n,m\le 10^5\)
题解¶
最短时间\(T\)的下界为\(\max(\max t_i,\lceil \frac{\sum t_i}{m}\rceil)\)，考虑构造一组方案满足这个下界。其实只要从第一口锅开始，依次烤牛排即可（顺序无所谓）。\(T\ge\max t_i\)，保证了一块牛排最多在两口锅烤，且时间段不会有重叠；而\(T\ge \lceil \frac{\sum t_i}{m}\rceil\)保证了在不浪费任何时间的情况下，能把所有牛排烤完。
G¶
upsolved by TYB
题意¶
\(H_n\)为这样一个图：图中有\(d_n\)个点，\(d_n\)为\(n\)的因数个数，两个点\(u,v\)间有一条边当且仅当存在一个质数\(p\)使\(u=pv\)，\(f(n)\)表示\(H_n\)这张图的边数，求\(\sum_{i=1}^nf(i)\)。
有\(T\le5\)组数据，\(n\le10^{10}\)
题解¶
考虑用\(n\)的最小质因子\(p\)转移（不是最小质因子也可以，仅为了方便），设\(p^e\mid n,p^{e+1}\nmid n\)，则\(f(n)=(e+1)f(\frac{n}{p^e})+ed(\frac{n}{p^e})\)。
大概就是把\(n\)的因子分为两部分，一部分是含\(p\)的，另一部分是不含\(p\)的。这样由质因子贡献的形式可以用min_25筛做，具体可以看min_25筛学习笔记。
H¶
solved by JLK
题意¶
二维平面内，有一只兔子，初始在一个格子内，每次可以往四个方向跳\(d\)格。有\(n\)个矩形，表示不能让兔子落在这些矩形内。求兔子可能的初始位置。
\(1 \le n,d \le 10^5\)
题解¶
可以把所有限制条件转化到一个\(d\times d\)的矩形内。
分类讨论，如果横纵坐标差值都大于等于\(d\)，那么肯定无解。有一个大于等于\(d\)，则会覆盖一整条。否则会被拆成几段。对\(d\)取模后分类拆成矩形，然后扫描线判断是否有没有被矩形覆盖的点即可。
\(O(nlogn)\)
I¶
solved by JLK
题意¶
有一个环，给定若干不相交的区间，要求构造出一些区间，使得构造出的区间满足他们的交集恰好是给定区间的并集。
\(1 \le n \le 1000\)
题解¶
假设给定的区间覆盖的点是1，否则是0。那么可以让1被所有区间覆盖，0被少一个区间覆盖。也就是，对于所有0，在\([x+1,x-1]\)（循环）放一个区间即可。
J¶
solved by TYB
题意¶
给出一个\(n\)个点\(m\)条边的无向连通图，点有点权，删去若干条边后得到若干个连通块，最大化大小为偶数的连通块点权和\(-\)大小为奇数的连通块点权和。
\(n,m\le10^6\)
题解¶
\(n\)为偶数时答案就是所有点权和。\(n\)为奇数时，可以证明最优方案一定是删去一个点和它连出去的所有边。首先最优方案不会出现大小为奇数且不是\(1\)的连通块，因为这样可以再从中删去一个点使答案更优；然后孤立点（即大小为\(1\)的连通块）个数一定为奇数，若为偶数，那么大小\(>1\)的连通块的大小总和为奇数，至少存在一个大小为奇数的连通块，与上一个结论矛盾；最后孤立点一定只有一个，否则可以通过去掉两个孤立点，把几个连通块拼起来使答案更优。所以我们只需要枚举删去哪个点，可以用点双连通分量实现。比赛时写复杂了，建出了点双树，实际上只要在Tarjan的过程中求答案即可。
K¶
upsolved by TYB
题意¶
给一棵\(n\)个节点的树，点有点权，\(m\)次询问，每次询问树上两点\((x,y)\)路径上，选择若干不相邻的点权值最大是多少。
\(n\le5\times10^5,m\le10^7\)
题解¶
就是猫树在树上问题拓展的裸题。
具体实现的时候，需要记录下点分树上每个点到子树内所有点的信息，这个不太好直接记录。考虑点分树的深度是\(\log\)级别的，所以可以直接记录每个点到它在点分树上的第\(i\)个祖先的信息。但这样有个问题，找到LCA后还要知道它是第几个祖先，这个理论上来说可以通过hash之类的做到\(O(1)\)，但参考了已通过的代码以及考虑常数问题，发现还是直接for一遍比较好，这部分其实可以当做常数。
记录¶
开局看题，没有特别签到的。YZW看I，和TYB讨论了错误解法WA了两发。JLK改过来后T了一发才AC(0:37)。
TYB写F，WA1后AC(0:54)。
然后JLK写H，TYB和YZW讨论J。交了两发都WA了，本地写了个对拍和checker，但是由于随机数据过弱，没有对拍出来。YZW手造了一个数据，然后改对了。(1:51)
TYB写J，一发过(2:24)。
此时排名靠前，剩下C/D过的人比较多。但是C始终没有构造出来，D也没有想到。3h多一点时换题，TYB去莽K的log解法，毕竟有12s。JLK与YZW讨论E，想了个根号做法（赛后发现被出题人卡了）。
K一直TLE，卡常无果，直到结束。
总结¶
JLK：不是特别签到的简单题还是需要几个人多验证一下。上次沈阳也是第二简单的题思路错了。还有K这种题看起来像是钓鱼的（12s，1e7），以后不会什么科技的话还是不要写了。
Dirt¶
F(-1)
H(-2)
I(-3)