2021牛客暑期多校训练营5¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 18/1284（校内3/21） | 8 | 11 | 11 |
A¶
upsolved by YZW
题意¶
给出 \(n\) 个点 \(m\) 条边的 仙~人~~掌~~~ 🌵
\(q\) 组询问，每组询问给出三个点 \(c,d,l\)，求仙人掌上的一个点 \(x\) 使得：
- \(x\) 在 \(c\) 至 \(d\) 的某条最短路径上；
- \(x\) 在 \(c\) 至 \(l\) 的某条最短路径上；
- \(c\) 与 \(x\) 的距离最大。
\(1\leq n,q\leq 10^5\)，\(n-1\leq m\leq {3\over 2}(n-1)\)
题解¶
考虑树的做法，直接求 LCA 分类讨论（\(c\) 在 \(\text{LCA}(d,l)\) 子树外？子树内：更靠近 \(d\) 还是 \(l\)？），对应的 LCA 就是答案了。
对于仙人掌，建立圆方树，如果按树的做法找到的 LCA 是圆点就是答案了，不然找到的 LCA 是环，需要继续处理。
可以很简单地对于每个方点预处理对应环的顺序，从而可以轻易求得环上任意两个点的距离。通过倍增的方法，或者考察方点在圆方树上的 parent，可以求出三个点 \(c,d,l\) 出发走到环上第一个点分别是哪个点，设其分别为 \(c',d',l'\)，需要注意这一步除了类似树的做法分类讨论外（因为这类情况都是两个点倍增 + 方点的 parent），还要特殊处理三组 LCA 相同的情况（这个情况三个点都要倍增）。
再根据环上距离推算答案，即要求 \(\text{dist}(c',x')+\text{dist}(x',d')=\text{dist}(c',d')\) 且 \(\text{dist}(c',x')+\text{dist}(x',l')=\text{dist}(c',l')\)，容易发现答案 \(x'\) 为 \(c',d',l'\) 其一，验证取最大的即可。
复杂度 \(O(n\log n+q \log n)\)。
B¶
solved by TYB&JLK
题意¶
有\(n\)个箱子，每个箱子有一个球，是黑球和白球的概率都为\(\frac{1}{2}\)，有两种操作，一种是花费\(w_i\)打开第\(i\)个箱子，二是花费\(C\)得知当前没有打开的箱子中还剩下几个黑球，求知道所有箱子中放的球的颜色的最小期望花费。
\(n\le10^5,w_i,C\le10^9\)，花费为小数。
题解¶
考虑花费\(C\)的操作，它仅有可能在一开始被使用一次，使用第二次无意义，而不在一开始使用得知的信息更少。所以策略一是不使用\(C\)，花费为\(\sum w_i\)，策略二是一开始使用\(C\)，然后后面再打开若干个箱子，直到打开所有含有黑球的箱子。由于每个箱子等价，一定是将\(w_i\)从小到大排序后，开了一个前缀，枚举最后一个有黑球的箱子在第几个被开到，简单算一下概率即可。
C¶
solved by JLK&TYB
题意¶
两个人比赛\(n\)次，给定一个长度为\(n\)的序列表示每次的输赢。类似于乒乓球等比赛的规则，如果规定赢的局数为\(i\)，当两人中至少有一人的分数大于等于\(i\)，且两人分差大于1的时候一局结束。对每个\(1 \le i\le n\)，求出赢的局数。
\(1 \le n \le 10^6\)
题解¶
显然只能枚举\(i\)，如果每次\(O(1)\)跳到下一局的结束位置，那么复杂度为\(O(nlogn)\)，可以通过。
把赢看做1，输看做-1。
首先要找到有一个人的分数大于等于\(i\)的位置。这可以把1和-1单独拉出来，找到当前位置前面总共有几个-1和1，加上\(i\)个之后最小的位置就是要求的位置。
如果这一局还没结束，那么当前区间一定是-1,0或1。这个位置再到结束的区间和可能为+1,+2,+3,-1,-2,-3。对于每个位置都预处理出这六种情况的下一个位置。这可以一开始倒着扫一遍，维护每个前缀和最近的出现位置。
\(O(nlogn)\)
D¶
solved by JLK
题意¶
给定字符串\(A\)和\(B\)，要分别从中取出两个长度一样的子序列\(a,b\)，而且\(\exists i,A_{a_i}\lt B_{b_i},\forall j\lt i,A_{a_j}= B_{b_j}\)。求方案数。
\(1 \le |A|,|B| \le 5000\)
题解¶
实际上就是让\(a\)的字典序小于\(b\)，不过题目这样说出来实际上比字典序更简单了。
预处理出两个数组，\(dp_{i,j}\)表示\(A[1..i],B[1..j]\)里选子序列，全部相同的方案数。\(DP_{i,j}\)表示在长度分别为\(i,j\)的序列里任意选相同长度的子序列的方案数。
枚举\(A_{a_i}\lt B_{b_j}\)的位置计算即可。
\(O(n^2)\)
E¶
upsolved by JLK
题意¶
给定一棵有\(n\)个点以1为根的树，每条边是or、and、xor三种位运算符之一。给定序列\(a\)。
\(q\)个询问，每次询问给出\(d,u\)，当\(i\)点权值为\(a_i+d\times i\)时，求出\(u\)点开始向下的所有链的值的or、and、xor和。链\(a,b,c\)（\(a\)深度最小）的值为\((a??(b??c) )\)。??为边的运算符。
\(1 \le n,q \le 10^5,1 \le a_i \le 10^{18},0 \le d \le 100\)
题解¶
似乎是一种套路。
首先肯定是对于每个\(d\)处理一遍所有点的答案。假设当前所有点的权值已经确定为\(A_i\)。
对每个点维护\(dp_{i,0/1/2}\)，表示从\(i\)开始向下的链的值的三种和。转移的时候就分析每一二进制位的贡献。
以边为or，要转移链值的xor和为例：
相当于求\((x|y)\oplus(x|z)\oplus\cdots\)。\(x\)为当前点的权值，\(y,z\)为儿子向下的某些链的值。
如果\(x\)的某一位是0，那么完全可以忽略\(x\)的影响，就是\(y\oplus z\)。
如果\(x\)的某一位是1，那么就没有\(y,z\)的影响，被异或的次数取决于子树大小。如果子树大小为奇数则要异或一次\(x\)，否则不异或。
可以分类讨论九种转移，通过简单的位运算来实现。
\(O(nd)\)
F¶
upsolved by YZW
题意¶
给出一个 \(n\) 个点的凸包 \(A_1A_2\dots A_n\)，求凸包内一点 \(P\)，最大化 \(\min_{1\leq i\leq n}\{\angle A_iPA_{i\bmod n+1}\}\)，输出该值。
\(4\leq n\leq 100\)
题解¶
由几何知识不难得到，对于两点 \(A,A'\)，满足 \(\angle APA'\geq \theta\) 的点 \(P\) 构成一个圆，并且利用 \(\theta\) 可以轻易求得圆心与半径。
二分 \(\theta\)，判断是否存在一个点在所有圆内。可行方法：逐一判断所有圆心和任意两个圆的交点是否满足条件。如果存在相离的两个圆则一定不存在满足条件的点。特别注意求圆的交点时两圆相含时是无交点的。
G¶
solved by YZW
题意¶
给出正整数 \(a,b,c\)，求最小的 \(x+y\) 使得 \(\text{lcm}(a+x,b+y)=c\)。
\(c\) 以 \(\prod_{i=1}^n p_i^{q_i}\) 的形式给出。
\(1\leq n\leq 18\)，\(2\leq p_i\leq 100\)，\(1\leq q_i\leq 18\)，\(1\leq a,b\leq c\leq 10^{32}\)，保证 \(\sum_{q_i}\leq 18\)
题解¶
易见 \(a+x\) 与 \(b+y\) 是 \(c\) 的因数。
\(a+x\) 与 \(b+y\) 的 \(\text{lcm}\) 为 \(c\) 当且仅当对于每个 \(p_i\)，\(a+x\) 与 \(b+y\) 二者至少其一满足：\(p_i^{q_i}\) 为其因子。
由此可以将 \(c\) 的一个因数对应 \(n\) 位二进制状态，第 \(i\) 位表示是否含有因子 \(p_i^{q_i}\)。
枚举 \(c\) 的所有因数（最多 \(2^n\) 个）分别作为 \(a+x\) 和 \(b+y\)，对于每个状态 \(s\)，记录 \(a+x\) 与 \(b+y\) 达成这个状态的最小的 \(x\) 与 \(y\)，记为 \(x(s),y(s)\)。
答案即为 \(\min_{s_1\wedge s_2 = 11\dots 1} \{x(s_1)+y(s_2)\}\)。
可以设 \(\hat x(s)=\sum_{s\wedge s' = s} x(s')\)，答案就是 \(\min_{s} \{x(s)+y(\sim s)\}\)。
\(\hat x(s)\) 可以像 FWT 一样在 \(O(n2^n)\) 的时间内求出，听说这个叫 FMT。
时间复杂度 \(O(n2^n)\)。
H¶
solved by TYB
题意¶
构造一个\(n\times m\)的\(01\)矩阵，使得不存在连续三个横着、竖着或者斜着的格子中都是同一个数。
\(n,m\le1000\)
题解¶
构造形如：
\(0011\)
\(1100\)
\(0011\)
的矩阵即可。
I¶
solved by JLK
题意¶
给定一个长度为\(n\)的序列\(A\)，每次询问给定\(l,r,k\)，要对\(0 \le i \lt k\)求出\(f(A[l-i+1..r+i-1])\)。其中\(f(S)\)为最长的连续权值区间。
例：\(f(\{1,2,4,5,6\})=3\)。
\(1 \le n,q \le 10^5,1 \le A_i \le n,\le \sum k \le 10^7\)
题解¶
队友扔给我一个分块做法，看起来合理。实际上似乎叫“回撤莫队”？
因为普通数据结构并不好维护删除，故无法直接莫队或分块。如果只加入和撤销就很好维护。
所有询问按左端点分块。对于左端点位于一个块的询问\(q_i\)，一起处理。从块的右端点开始向右扫，同时维护一个数据结构。然后碰到某个\(q_i\)的右端点之后，在左边暴力扫，加上需要的数。对于每个\(k\)也是暴力加上。然后再把所有操作都撤销，回滚到刚到\(q_i\)右端点的状态。
那么只需要一个可以撤销的数据结构。比赛时想到的是按秩合并的并查集，加入和撤回都是\(O(logn)\)的。
实际上可以直接用类似链表的东西，因为是一段连续的区间。在左端点记录右端点的位置，在右端点记录左端点的位置。这样就可以\(O(1)\)维护了。
\(O(n\sqrt n+\sum k)\)
J¶
solved by TYB
题意¶
\(n\)个物品，第\(i\)个有参数\((x_i,y_i,z_i,v_i)\)，在\([0,n-1]\)每个整数时刻获取一个未获取的物品，代价为\({x_i}^2+{y_i}^2+(z_i+t_iv_i)^2\)，求获取所有物品的最小代价。
\(n\le300,z_i,v_i\ge0\)
题解¶
一开始被骗了，以为是个玄妙的贪心或者排序题，后来发现是裸的二分图最大权匹配，直接上KM。
\(O(n^3)\)
K¶
solved by YZW
题意¶
给出长为 \(n\) 的正整数序列 \(\{a_i\}\)，\(m\) 次询问，每次询问给出 \(k\)，询问满足子段极差严格大于 \(k\) 的子段个数。
\(1\leq n\leq 10^5\)，\(1\leq m\leq 200\)，\(1\leq a_i,k\leq 10^9\)
题解¶
对于每个询问，双指针+两个单调栈（单增，单减）扫一次序列即可求得：每个位置作为左端点时，满足条件的右端点数量，求和即为答案。
\(O(nm)\)
记录¶
开局HKBD都一发过，感觉良好。(0:41)
JLK写C，细节没处理好WA了。换YZW试一个J的贪心做法，WA两次。
之后改C过了(1:41)。
TYB说J是费用流，又T了。找到KM板子，遂AC。(2:40)
YZW写G，答案为0的时候没处理好，WA后AC(3:08)。
JLK用大复杂度做法写I，先T，优化后AC(4:38)。
然后YZW卡在F，一直交也没搞出来。
总结¶
JLK：对板子不够熟练。可能需要多做一些应用。 TYB：思维不够灵活，没看出来裸的二分图最大权匹配模型，看出来后又因为较少使用KM，选择了复杂度不够优秀的费用流，浪费了较多时间；然后抄模板的时候不太熟悉，最好还是手打一遍，变成自己的风格；需要学习一些基本的计算几何知识，至少做到会做签到题水平的计算几何题。
Dirt¶
C(-1)
G(-1)
I(-1)