2021牛客暑期多校训练营2¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 105/1352 | 5 | 12 | 12 |
A¶
upsolved by TYB
题意¶
给出一个长度为\(n\)的序列，求有多少个区间的数满足排序后可以形成等差数列。
\(n\le 10^5\)
题解¶
用到一个结论：若一个序列\(\{a_n\}\)排序后可以形成等差数列，则\(\gcd(a_1-a_2,a_2-a_3,...,a_{n-1}-a_n)=d\)，\(d\)为公差。
于是我们得到了一个快速判断一个区间\([l,r]\)是否满足条件的方法：\(\max(l,r)-\min(l,r)=(r-l)\times \gcd(a_l-a_{l+1},...,a_{r-1}-a_r)\)
考虑枚举右端点\(r\)，左边的部分可以用单调栈+线段树维护。而对于某个左端点，不同的右端点得到的\(\gcd\)不同取值只有\(\log\)种，所以可以在右端点移动时对变化的\(\gcd\)暴力修改。
实现时维护每个左端点\(\max(l,r)-\min(l,r)-(r-l)\times \gcd(a_l-a_{l+1},...,a_{r-1}-a_r)\)的值，由于这个值\(\ge0\)，可以维护区间最小值和最小值的出现次数，出现次数则是答案。
B¶
upsolved by JLK
题意¶
有两行棋盘，两行分别有\(x,y\)个中国象棋里的炮，对每个\(k\)求两行共进行\(k\)次炮吃炮事件的方案数。
对于两种情况分别求：不区分两行的顺序，以及先1行后2行。
\(1 \le x,y \le 5\times 10^6\)
题解¶
不难发现，一行有\(x\)个炮的时候，走一步方案数为\(2\times (x-2)\)，走\(i\)步为\(2^i\times \frac{(x-2)!}{(x-2-i)!}\)
那么第一个问题的答案为
\(\sum\limits_{i=0}^{k}2^k\frac{(x-2)!}{(x-2-i)!}\frac{(y-2)!}{(y-2-(k-i))!}C_k^i\)
\(= 2^k k!\sum\limits_{i=0}^k C_{x-2}^iC_{y-2}^{k-i}\)
\(= 2^k k!\sum\limits_{i=0}^k C_{x+y-4}^k\)（组合意义）
第二个问题的答案为
\(\sum\limits_{i=0}^{k}2^k\frac{(x-2)!}{(x-2-i)!}\frac{(y-2)!}{(y-2-(k-i))!}\)
\(=2^k\frac{(x-2)!(y-2)!}{(x+y-4-k)!}\sum\limits_{i=0}^{k}\frac{(x+y-4-k)!}{(x-2-i)!(y-2-(k-i))!}\)
\(=2^k\frac{(x-2)!(y-2)!}{(x+y-4-k)!}\sum\limits_{i=0}^{k}C_{x+y-4-k}^{x-2-i}\)
\(=2^k\frac{(x-2)!(y-2)!}{(x+y-4-k)!}\sum\limits_{i=x-2-k}^{x-2}C_{x+y-4-k}^{i}\)
现在需要快速求出\(\sum\limits_{i=x-2-k}^{x-2}C_{x+y-4-k}^{i}\)。注意到随着\(k\)移动一次，求和的左端点移动一次，组合数的参数也移动一次。考虑递推。
令\(S(n,m)=\sum\limits_{i=0}^m C_n^i\)
则\(S(n+1,m)=2S(n,m)-C(n,m)\)（考虑\(C\)的递推式或杨辉三角）
\(S(n,m+1)=S(n,m)+C(n,m+1)\)
对左右端点分别维护组合数的前缀和即可。
\(O(x+y)\)
C¶
solved by JLK
题意¶
给一个\(n\times m\)的格点图，每次可以选择一对四联通的点（没有被连过），连上一条边，要求不能构成封闭图形，不能操作者输。问先手输赢。
\(1 \le n,m \le 4\)
题解¶
游戏结束时最后一定构成一棵树，共\(n\times m-1\)条边，故判断其奇偶性即可。
D¶
solved by YZW
题意¶
按规则打牌，问双方哪方获胜。
题解¶
签到题，模拟即可。
E¶
upsolved by JLK
题意¶
给定一棵\(n\)个点的树，有点权和边权，经过点时油量加上点权，经过边时减去边权，要求每个时刻的油量大于等于0。有\(q\)个询问，问从\(x_i\)开始，不经过\(p_i\)点，且一开始的油量是\(d_i\)，能通过简单路径到达多少点。
\(1 \le n,q \le 10^5,1 \le d_i \le 10^{14},\)点权和边权\(\le 10^9\)
题解¶
能否到达完全和路径有关，而且要询问整棵树上的点，不难看出可以使用点分治解决。
那么考虑如何处理信息。假设固定了一个根，要求出从根到\(x\)在最少需要多少初始油量，以及从\(x\)到根最少需要多少初始油量。
前者可以通过比较当前油量与所需油量的差距来从上到下递推计算。
后者需要算（点权-边权）前缀和以及前缀和最大值。因为如果把油量变化画成图，那么需要的油量取决于最低点，也就是后缀最小值。用当前的前缀和减去前缀最大值就可以得到。
然后考虑在点分治的时候计算答案。将所有询问离线，然后点分治。
当扫到一个点的时候，遍历挂在上面的所有询问。先考虑没有限制条件。
要求经过当前的分治中心，那么先算出到分治中心能剩下多少油（可能无法到达），然后就是查询不在子树内，且需要油量小于等于剩下油量的点数量。
这可以用dfs序+BIT维护。把所有点按所需油量排序，然后把询问也按剩下油量排序，从小到大扫一遍即可。
去掉子树内的和经过\(p_i\)的，就再挂一或二个询问，系数为-1，把对应dfs序的答案再减掉即可。注意要讨论\(p_i\)和当前点以及分治中心的相对位置，有可能不需要减去。
\(O((n+q) log^2n)\)
F¶
solved by JLK&YZW
题意¶
给定\(A,B,C,D\)四个空间里的点，作\(P_1,P_2\)，满足\(|AP_1|\ge |BP_1|,|CP_2|\ge |DP_2|\)，求满足方案的\(P_1,P_2\)的交集的体积。
题解¶
这是阿波罗尼斯球，本质上是求两个球的交的面积。可以先计算得出圆心距离和两个半径。
Sol.1¶
用Simpson积分计算。在圆心连线上积分，积分函数为截面面积。
YZW：注意 Simpson 积分时需要保证初始采样点值不相等（
G¶
upsolved by TYB
题意¶
给定\(n\)个区间，要求将它们分成\(k\)组，每组之间有交，最大化每组交长度之和。
\(1\le k\le n\le 5000\)
题解¶
一个直接的想法是对区间进行排序，然后\(f_{i,j}\)表示前\(i\)个区间分了\(j\)组的答案，转移枚举最后一组的区间数。但这样做是错的，由于存在一个区间完全包含另外一个区间的情况。所以考虑这种区间的最优决策，一是归属到一个被它包含的区间所在的组，不影响答案；二是独自一组，长度直接算入答案，可以证明其他的决策都是不优的。因此可以提取出这些区间，再将剩下的区间按照上面的方式dp，发现这个dp可以用单调队列优化，于是时间复杂度\(O(n^2)\)。
H¶
upsolved by TYB
题意¶
给定一个长度为\(n\)的\(01\)串，其中不存在相邻的\(1\)，每次翻转一个两端为\(1\)的交替段（形如\(101010101\)），求连续翻转\(k\)次操作序列的方案数。
\(n,k\le6\times10^5\)
题解¶
每一个极长的连续段之间不会互相影响，所以只要能快速求出有\(n\)个\(1\)的交替段操作\(k\)次方案数然后合并它们的指数生成函数即可。打表发现答案为\(\tbinom{n+k}{n-k}\Pi_{i=1}^k(2i-1)\)。证明可以考虑组合意义和归纳证明。合并的话可以每次选择次数最小的两个多项式合并，也可以直接分治，具体来说是\(solve(l,r)\)表示合并第l个到第r个多项式，直接分治下去，复杂度一样，都是两个\(\log\)。
I¶
solved by JLK
题意¶
两个\(20\times 20\)的迷宫，有障碍物和道路，各有一个人，各给定起点和终点（定点），四个方向同时控制两个人，碰到障碍物就不动，输出最小步数、方案以及路径。
题解¶
记录\(20^4\)的位置状态，BFS即可。
J¶
upsolved by YZW&JLK
题意¶
\(T\) 组数据，每组数据给出可重正整数集 \(S=\{x_i\}\)，求 \(S\) 的任意 \(k\) 个元素构成子集的 \(\gcd\) 的乘积对 \(P\) 取模的值。
\(T\leq 60\)，\(10^6\leq P\leq 10^{14}\)，\(1\leq x_i \leq 8\cdot 10^4\)，\(1\leq ∣S∣\leq 40000\)，\(1\leq k\leq \min(∣S∣,30)\)。
题解¶
利用 Dirichlet 前缀和，化简可得计算卷积时的容斥系数即为组合数，即可求得 \(\gcd\) 为 \(i\) 的子集数，从而可求得答案。但注意扩展欧拉定理并不能直接 \(\bmod \varphi(P)\)，因此该做法实际上存在问题。
注意到实际上并不需要再做差分，前缀和中 \(p^\alpha\) 项的系数表明了 \(\gcd\) 是 \(p^\alpha\) 倍数的子集数，该项对答案贡献子集数个因子 \(p\)，直接计数计算即可。
K¶
solved by TYB
题意¶
1 2 3 4 5 6 | |
给定某些\(b_i\)的取值，要求构造排列\(a_i\)，使以上面的方式得到\(b_i\)满足要求。或输出无解。
\(n\le 10^6\)
题解¶
先假设每次push的\(a_i=i\)，若\(b_i\)有要求，则一直做pop操作直至满足要求。然后此时需要把栈顶位置\(+1\)到\(i-1\)这段的\(a_i+1\)，用差分实现。（感觉不太讲得清楚，看代码吧）
L¶
upsolved by JLK
题意¶
微信步数排行榜。有\(n\)个人，\(m\)对朋友关系，\(q\)个事件。每个事件中，有一个人步数增加了若干步。当一个人比他的所有朋友的步数都严格大时，他成为排行榜冠军。问每个人成为冠军的时间。
\(1 \le n,m,q \le 2\times 10^5\)
题解¶
可能算是套路题？
把度数按\(\sqrt n\)分类。对于度数小的点，每次可以直接更新周围的点。
而对于度数大的点，最多有\(\sqrt n\)个。可以直接更新周围的大点。
考虑在大点改变时更新小点。可以在小点更新的时候挂一个询问在大点上，如果大点某次更新使得步数超过了小点当前步数，就可以反过来更新小点。这可以用一个小顶堆来维护。
不需要删除操作，允许一个堆里面有不同时间的相同小点。因为更新是单调递增的，这样并不会错误。
堆里最多进入\(n\sqrt n\)个元素，复杂度合理。
注意这样更新有滞后性。在小点发生改变前的大点更新没有被记录到。因此小点改变的同时，还需要马上用所有大点更新这个小点。
记录时间，就是每次更新自己的时候记录一下时间，然后附近点更新的时候如果被顶下去就结束计时。
\(O(n\sqrt nlog n)\)
一个比较难理解的地方是，当大点连续更新两次时，有可能导致第二次没有更新到小点上。这其实已经被处理了。第二次没有更新到小点，说明第一次更新到小点了，已经比小点步数多了，计时结束，第二次可以暂时不用更新。而在小点又一次改变的时候才检查第二次更新，这时就把第二次记录了。
记录¶
9min：JLK WA C (-1)
9min：JLK AC C
中间电脑出问题
20min：YZW AC D
75min：TYB AC K
101min：JLK AC I
138min：YZW WA F 怀疑是精度问题
之后改eps，换long double等方法皆失败
261min：JLK AC F 换了积分方法
总结¶
TYB：开场开G，经历了假做法1、假做法2、暴力对拍发现结论错误的过程。原因是蜜汁自信和有点着急，过于凭感觉，找反例的能力也不高。即使是第一感觉很正确的东西也要小心。开题也不好，赛后也许发现其他的更可做。zzh建议的2h读完题应该做到。
Dirt¶
C(-1):NO写成No
F(-5):积分方式不同导致精度误差