2021牛客暑期多校第二场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 224/1353 | 4 | 12 | 12 |
A¶
upsolved by JJLeo
题意¶
给定 \(n\) 个不同数组成的序列，求有多少个区间排序后是等差数列。(\(1 \le n \le 10^5\))
题解¶
\(n\) 个不同的数 \(a_1,a_2\cdots,a_n\) 排序后是等差数列，设其公差为 \(d\)，则有 \(d = \gcd(|a_2-a_1|,|a_3-a_2|,\cdots,|a_n-a_{n-1}|)\)。
显然差值必然是 \(d\) 的倍数，因此只需证明 \(1,2,\cdots,n\) 的所有排列差分数组的 \(\gcd\) 必为 \(1\)。假设 \(\gcd \ge 1\)，那么必然存在两个模 \(\gcd\) 不同余的数相邻，其差不能被 \(\gcd\) 整除，矛盾。
设 \(d = \gcd(|a_2-a_1|,|a_3-a_2|,\cdots,|a_n-a_{n-1}|)\)，若 \((n-1)d=\left(\max \limits _{i=1} ^n a_i\right) - \left(\min \limits _{i=1} ^n a_i\right)\)，则这 \(n\) 个不同的数 \(a_1,a_2\cdots,a_n\) 排序后是等差数列。
考虑从 \(a_1\) 开始，每次都增大 \(kd\) 或减小 \(kd\)，始终处于 \(\left[\left(\min \limits _{i=1} ^n a_i\right),\left(\max \limits _{i=1} ^n a_i\right)\right]\) 的范围内，且不能和之前的某个数相同，那必然是取遍了中间所有相差为 \(d\) 的数，即为等差数列。
如果 \(n\) 个数存在相同，则不一定成立，例如 \(1,2,2,4\)。
固定一个端点往左往右不同的 \(\gcd\) 只有 \(O(\log a)\) 种，可以将上一个左/右端点对应的段和这个位置的数取 \(\gcd\) 得到新的段位置，再加上单选这一个位置的情况。
设 \(d = \gcd(|a_{l+1}-a_l|,|a_{l+2}-a_{l+1}|,\cdots,|a_r-a_{r-1}|)\)，考虑维护 \(\left(\max \limits _{i=l} ^r a_i\right) - \left(\min \limits _{i=l} ^r a_i\right)-(r-l)d=0\) 的区间个数，而 \(\left(\max \limits _{i=l} ^r a_i\right) - \left(\min \limits _{i=l} ^r a_i\right)-(r-l)d \ge 0\)：
考虑和上面类似的证法，从 \(a_1\) 开始，每次都增大 \(kd\) 或减小 \(kd\)，如果 \(\left(\max \limits _{i=l} ^r a_i\right) - \left(\min \limits _{i=l} ^r a_i\right)<(r-l)d\)，因为所有数都不相同，则不足 \(r-l+1\) 个数供选择，矛盾。
因此只需维护最小值和最小值的个数。
从左往右扫，单调栈 + 线段树区间加操作维护 \([i,r]\) 区间的最大值和最小值。同时线段树上第 \(i\) 个位置始终加着 \(i\gcd(|a_{i+1}-a_i|,|a_{i+2}-a_{i+1}|,\cdots,|a_r-a_{r-1}|)\) 的值，对于每个左端点来说，右端点移动过程中该点最多发生 \(O(\log a)\) 次变化，因此只需要进行 \(O(n \log a)\) 次单点修改操作。
查询时对于固定的右端点，对 \(O(\log a)\) 段不同的 \(\gcd\) 依次询问最小值并减去 \(rd\)，若为 \(0\) 将最小值个数加上即可。
线段树需要支持单点修改、区间加、区间查询最小值和最小值出现次数，总时间复杂度为 \(O(n \log n \log a)\)。
B¶
upsolved by JJLeo
题意¶
仅叙述核心部分，给定 \(n,m\)，对 \(k=0,1,\cdots,\min(n,m)\) 求解：
(\(1 \le n,m \le 5 \times 10^6\))
题解¶
尝试 MTT，还没等 TLE，先 MLE 了。
正解是推式子环节：
$$ \begin{aligned} &\sum_{i=0}^k\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!} \newline =&\sum_{i=0}^k\frac{n!m!}{(n+m-k)!}\frac{(n+m-k)!}{(n-i)!(m-(k-i))!} \newline =&\frac{n!m!}{(n+m-k)!}\sum_{i=n-k}^n\frac{(n+m-k)!}{(n-(n-i))!(m-(k-(n-i)))!} \newline =&\frac{n!m!}{(n+m-k)!}\sum_{i=n-k}^n\frac{(n+m-k)!}{i!(n+m-k-i)!} \newline =&\frac{n!m!}{(n+m-k)!}\sum_{i=n-k}^n\binom{n+m-k}{i} \end{aligned} $$ 设 ：
\(m\) 的增减很简单，即为和式的定义，对于 \(n\) 的增减，有：
而所求的原式为：
预处理阶乘及其逆元后，从小到大枚举 \(k\)，\(O(1)\) 维护 \(S(n+m-k,n)\) 和 \(S(n+m-k,n-k-1)\) 的值即可，时间复杂度为 \(O(n+m)\)。
E¶
upsolved by JJLeo
题意¶
给出一颗 \(n\) 个点带边权和点权的树，每经过一个点可以获得等于该点点权的油量，每经过一条边时所拥有的油量不能少于该边的边权。
给出 \(q\) 个询问，从 \(x\) 点出发，油量为 \(d\)，求不经过点 \(p\) 的情况下有可能到达点的个数。
(\(1 \le n \le 10^5\))
题解¶
题意第一段是从 这里 复制的，比赛时没有回忆起来，我老健忘症了。
把所有询问离线下来做一次静态点分治，对于一个询问中的点 \(x\) 来说，设当前分治中心为 \(r\)，考虑其跨过 \(r\) 能到达多少个点，维护每个点到达 \(r\) 所需的最小油量、到达后获得的油量、以及从 \(r\) 下去所需油量，类似上面那题进行维护，只需维护当前树链的前缀和、前缀最小值和前缀最大值，注意 \(r\) 的油量不要算两遍。
讨论 \(p\) 的位置：
- \(p\) 是 \(x\) 的父亲，那么不能到达跨过 \(r\) 的任意一个点，贡献为 \(0\)。
- \(p\) 与 \(x\) 在同一个子树，但不是 \(x\) 的父亲，则 \(p\) 没有影响，只需要考虑 \(x\) 跨过 \(r\) 能到达多少个点。
- \(p\) 和 \(x\) 不在同一个子树，那么计算跨过 \(r\) 能到达多少个点后还需要减去 \(p\) 所在子树的点。
可以发现 \(x\) 跨过 \(r\) 能到达点的个数其实就是总数减去 \(x\) 所在子树的答案，因此只需要实现一个子树中有多少个点的值小于给定值这一操作。
这可以先将所有询问离线，再进行一次 dfs 作差，同时开一个全局树状数组维护，对于每个 \(x\)，dfs进入 \(x\) 时记录一下当前的答案，每个点回溯时将该点的值加入树状数组，同时对于每个 \(x\) 用当前答案减去进入时的答案就可以得到该子树内的变化量。
时间复杂度为 \(O(n \log ^2 n)\)，本来想了个动态点分治的在线做法，后来被点分树演了，假了好几个小时，说不定能做只是太复杂我不会（x
F¶
solved by Bazoka13
题意¶
球交（？
题解¶
一血，yyds！
G¶
upsolved by 2sozx JJLeo
题意¶
给定 \(n\) 个区间，将其分为 \(k\) 组，每组交必须不为空，最大化每组交长度之和。(\(1 \le k \le n \le 5000\))
题解¶
考虑一个包含其它区间的区间，要么跟它包含的一个区间一组，要么自己单独一组，可以将这些区间全部拿出来，最后看差了 \(x\) 组就取长度最大的 \(x\) 个加上即可。需要注意的是如果有很多完全一样的区间，要留一个认为它被其他包含，不然如果它不自己单独一组就找不到对应的组了。
接下来所有区间均没有包含情况，也就是右端点随左端点增加而增加，mjx 使用数学归纳法证明了最优方案每组一定都是连续的区间。
接下来把所有区间按左端点排序，开始dp，设 \(f_{i,j}\) 为前 \(i\) 个区间分成 \(j\) 组的最大交长度，则有：
\(r_k \ge l_i\) 这个条件是因为要求每组交不能为空，使用单调队列优化即可。
最后对于每个 \(f_{n,j}\)，补上 \(k-j\) 个最大的包含其它区间的区间 (如果有的话) 即可。总时间复杂度为 \(O(nk)\)。
H¶
upsolved by JJLeo
题意¶
给定长度为 \(n\) 的 \(\texttt{01}\) 串，保证不存在两个相邻的 \(\texttt{1}\)，每次可以选择一个以 \(\texttt{1}\) 开头和结尾的交替子串，将每一位反转，问操作 \(k\) 次的方案数是多少。(\(1 \le n,k \le 6 \times 10^5\))
题解¶
间隔两个 \(\texttt{0}\) 以上的部分相互独立，可以求出每部分的方案数最后用分治 NTT 合并 EGF。
含有 \(n\) 个 \(\texttt{1}\) 的长度为 \(2n-1\) 的 \(\texttt{01}\) 串操作 \(k\) 次的方案数是 \(\dbinom{n+k}{n-k}\prod \limits _{i=1}^k (2i-1)\)：
首先使用不定方程的方法可以解出长度为 \(2n-1\) 的串中放置 \(n-k\) 个不相邻 \(\texttt{1}\) 的方案数为 \(\dbinom{n+k}{n-k}\)。
接下来可以使用数学归纳法证明操作 \(k\) 次后的逆操作可以回到 \(2k+1\) 个 \(k-1\) 次操作后的状态，因此答案即为 \(\dbinom{n+k}{n-k}\prod \limits _{i=1}^k (2i-1)\)。
最后卷起来即可，注意是 EGF，因为不同段之间的操作顺序有意义，总时间复杂度为 \(O(n \log ^2n)\)。
J¶
upsolved by JJLeo
题意¶
\(T\) 组数据，给定一个正整数集合 \(S\)，求 \(S\) 中所有大小为 \(k\) 子集 \(\gcd\) 的乘积，对 \(P\) 取模。(\(1 \le T \le 60\)，\(\forall x \in S,1 \le x \le 8 \times 10^4\)，\(1 \le |S| \le 4 \times 10^4\)，\(1 \le k \le \min(|S|,30)\)，\(10^6 \le P \le 10^{14}\))
题解¶
首先用 Pollard Rho 算法分解 \(P\)，算出 \(\varphi(P)\)。从大到小枚举值域，有：
最终答案即为 \(\prod \limits _i i^{f_i}\)，所有的 \(f_i\) 运算过程中要对 \(\varphi(P)\) 取模，用到的组合数可以在杨辉三角在 \(O(|S|k)\) 的时间内算出来，这题无视扩展欧拉定理直接模不加也能过（x
时间复杂度为 \(O(T(|S|k+m \log m))\)，其中 \(m\) 是值域。
另外因为是求的乘积，可以枚举每个质因子，算其贡献，也就是：
这样只用枚举所有质因子次幂的倍数，不会算复杂度，但快于 \(O(m \log m)\)。
K¶
upsolved by 呜呜呜
题意¶
对一个排列做单调栈，给定一些时刻栈内元素数量，其它时刻元素数量任意，构造一组合法的排列，或判断无解。
题解¶
对于那些没给出栈内元素数量的时刻，默认元素进入栈内没被弹出，据此可以连出元素之间大小关系的有向图，拓扑排序后无环即可随意构造一组解，否则无解。
正确性：如果对于那些没给出栈内元素数量的时刻，元素进入栈内被弹出，那么我们一定可以对中间这些元素进行排序使得它们不会被弹出，从而只需进行限定后再进行构造。
L¶
upsolved by JJLeo
题意¶
给定一个 \(n\) 个点 \(m\) 条边的有向无环图，代表每个人的朋友圈，共有 \(q\) 个单位时间，每个单位时间其中一个人会走一定数量的步数，如果一个人严格大于它所有朋友的步数那他就是冠军，问每个人成为冠军的时刻，保证任意时刻所有人的步数不超过 \(10000\)。(\(1 \le n,m,q \le 2\times 10^5\))
题解¶
根号分治，按度数和 \(O(\sqrt m)\) 的大小关系分为大点和小点。每个大点开一个 \(M=10000\) 的 vector，第 \(i\) 个里面存周围步数为 \(i\) 的小点冠军。
小点被更新时直接暴力判断当前是不是冠军，并更新周围人是不是冠军，如果是冠军则向周围的大点自己步数的 vector 中塞入自己，同时并不需要删掉更小 vector 中的自己。
大点被更新时暴力更新周围所有大点，接着暴力扫 vector，将所有对应的真实（指小点的步数和 vector 中的一样，没有塞入更大的 vector 中）的小点的冠军删去，最后更新自己的冠军情况。
暴力扫 vector的复杂度不超过塞入 vector 中的元素之和与 \(M\)，因此复杂度即为 \(O((q+M)\sqrt m)\)。
记录¶
0h：D题模拟签到，ZYF直接冲，C盲猜结论两行写完，F球交，CSK直接冲，I一看就是BFS一下就完事，直接开冲，暂时的rank3，本场结束(x。MJX喂了ZYF K的正解，ZYF写歪了，把正解扔了，之后一直在长时间构造K。
2h：J就是“手套”改版，直接开冲，然后看到 \(k\le30\) 完全没用上，直接寄
3-4h：寄
总结¶
Dirt¶
确实没有，所以寄了。