2021HDU暑期多校第五场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 63/750 | 5 | 10 + (E 假了) | 13 |
A¶
upsolved by JJLeo
题意¶
给定一棵 \(n\) 个节点的树，根节点为 \(1\)，每个点有一种颜色，两点之间的边权取决与两个点是否颜色相同，相同为 \(1\) 不同为 \(0\)。初始所有点颜色均不同，有 \(m\) 次以下四种操作之一：
- 把 \(x\) 到 \(1\) 上所有点染成一种全新的颜色。
- 输出 \(x\) 到 \(y\) 的距离。
- 输出 \(x\) 子树中所有点到 \(x\) 的距离之和。
- 设 \(f_i\) 是距离点 \(i\) 最远的祖先，满足其到 \(i\) 距离为 \(0\)。输出 \(\sum \limits _{i=1}^n f_i\)。
(\(1 \le n,m \le 10^5\))
题解¶
由于每次都是全新的颜色，可以发现操作 \(1\) 就是 LCT 的 access 操作，一条边边权为 \(1\)，当且仅当它是虚边。
对于操作 \(2\)，维护每个点到根节点的距离，虚实变换时相当于子树加减，查询时即为两点到根距离减去两倍它们 lca 到根节点的距离。
对于操作 \(3\)，维护每条边的贡献，其贡献即为对应的子树大小，虚实变换时单点修改即可，查询时即为子树去除自己这个点后求和。
对于操作 \(4\)，可以每条长度为 \(l\) 的实链其贡献为 \(\dfrac{l(l+1)}{2}\)，虚实变换时维护即可。
在 access 时利用一个树状数组维护，总时间复杂度为 \(O\left(n \log ^2 n\right)\)。
注意 access 时我们需要求出每个实链深度最浅的点，可以维护每个 Splay 中的深度最小点，也可以偷懒直接暴力跳 Splay 到最左边的点，注意这里一定要将这个点 splay 上来复杂度才是对的，因为 Splay 的复杂度是均摊 \(O(\log n)\) 的，当然这题数据弱不 splay 上来也能过。
B¶
upsolved by 2sozx
D¶
solved by JJLeo
题意¶
给定一个长度为 \(n\) 的字符串，将其分为一个非空前缀 \(A\) 和一个非空后缀 \(B\)，对一共 \(n-1\) 种分割方案，求解有多少个字符串对 \((a,b)\) 满足其长度相同且不超过 \(k\) 个位置不同，其中 \(a\) 是 \(A\) 的子串，\(b\) 是 \(B\) 的子串。(\(2 \le n \le 3000\))
题解¶
枚举两个匹配字符串的右端点的下标差 \(i\)，再枚举前面那个字符串的右端点 \(r\)，双指针往后移，维护前面那个字符串左端点最左能到哪里，如果不匹配位置超过了 \(k\) 或者两个字符串重叠了就往前移动。
假设现在状态为 \((l,r)\) 和 \((l+i,r+i)\)，可以发现所有前面那个字符串右端点为 \(r\) 且下标差为 \(i\) 的匹配方案对分割处在 \([r,r+i-1]\) 的有贡献，且对中间空的部分贡献为 \(r-l+1\)，从 \(l+i\) 开始依次减少 \(1\)，相当于一个公差为 \(-1\) 的等差数列，用二阶差分维护即可。
总时间复杂度为 \(O\left(n^2\right)\)。
E¶
upsolved by SB出题人
题意¶
矩阵不保证可逆，std 里面 assert 其可逆。
题解¶
爬。
H¶
upsolved by JJLeo
题意¶
给定集合大小为 \(n\) 的每个子集的出现次数 \(a_0,a_1,\ldots,a_{2^n-1}\)，设 \(A_i=\sum \limits _{i \subseteq j}a_j\)，求解：
(\(1 \le n \le 20\))
题解¶
首先高维前缀和求出 \(A_i\)，考虑对于一个 \(i\) 如何求出 \(\sum \limits _{j=0}^{2^n-1}A_{i \cup j}\)，可以发现其等于 \(2^{\operatorname{popcount}(i)}\sum \limits _{i \subseteq j} A_j\)，也就是先考虑 \(j\) 除了 \(i\) 是 \(1\) 的那些位，而 \(i\) 是 \(1\) 的那些位显然 \(i \cup j\) 也是 \(1\)，因此有贡献的都是 \(i\) 的超集，同时 \(j\) 的 \(i\) 是 \(1\) 的那些位可以随便选，所以每一个的贡献都是 \(2^{\operatorname{popcount}(i)}\)。因此可以再使用一次高维前缀和求出答案，总时间复杂度为 \(O\left(n2^n\right)\)。
I¶
upsolved by JJLeo
题意¶
给定一个长度为 \(n\) 的序列，求有多少个子区间其众数出现次数超过一半。(\(1 \le n \le 10^6\))
题解¶
单独考虑每个数，将这些数标为 \(1\)，其它数标为 \(-1\)，转化为求和为正的区间数量。
考虑如何快速跳过一堆 \(-1\) 的区间，新增的前缀和值是一个区间，而新增的答案即为小于某个值的前缀和都被算了数次，其中较大的一些被算的数量依次减少 \(1\)。换句话说，设前缀和为 \(i\) 的有 \(a_i\) 个，需要维护 \(a_i\) 和 \(ia_i\) 的区间和，可以用线段树完成。
这样复杂度是很大常数的 \(O(n \log n)\) 死活卡不过去，可以发现这两个东西树状数组也能维护，题解说树状数组就能卡过去，不过正解是 \(O(n)\) 的：
考虑如果当前的前缀和比之前的前缀和都小，那么显然不会有答案，可以发现如果有 \(m\) 个 \(1\)，有可能的位置至多有 \(O(m)\) 个。
因此我们如果遇到连续 \(-1\) 且接着走前缀和会比之前都小，可以直接跳过，利用一个差分数组完成这一段的 \(+1\)。
否则根据这一位是 \(1\) 或 \(-1\) 进行移动，移动时每次只会左右移动 \(1\)，向右移动的时候把差分数组的值加上，同时将其值加到下一位的差分数组，并将这一位的差分数组清空，向左移动则不用管差分数组，因为左侧的差分数组一定都处理完了。
移动时记录当前的位置，以及比当前位置小的前缀和数量即可。
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by
题意¶
题解¶
L¶
upsolved by JJLeo
题意¶
两个矩阵 \(A_{n\times r}\) 和 \(B_{r \times n}\)，每个位置取值都是 \([0,m]\) 间的整数。问有多少对 \(A\) 和 \(B\) 使得 \(C_{n\times n}=AB\) 中所有元素的和恰为 \(d\)，对 \(d=0,1,\ldots,m\) 求解，其中 \(r=n^m\)。(\(1 \le n,m \le 10^5\))
题解¶
括号里面的东西分别是 \(A\) 某一行的和以及 \(B\) 某一列的行，均相互独立，设 \(f_i\) 是其为 \(i\) 的方案数，即为 \(\left[x^i\right]{\left(\sum \limits _{i=0}^m x^i\right)}^n\)，这可以多项式快速幂求解。但注意到 \(d \le m\)，因此只需要 \(i \le m\) 的 \(f_i\)，前 \(m\) 项每个元素的取值相当于没有上界限制，因此等价于经典的不定方程求解，即 \(f_i= \dbinom{i+n-1}{n-1}\)。
设 \(g_i\) 为 \(\left(\sum \limits _{i=1}^nA_{i,k}\right)\left(\sum \limits _{j=1}^nB_{k,j}\right) =i\) 的方案数，\(f_if_j\) 可以贡献到 \(g_{ij}\)，因此可以调和级数 \(O(m \log m)\) 求解。然而这里有一个坑，那就是 \(g_0\) 并不是这个值，如果其中一个为 \(0\)，那么另外一个是什么都可以，并不一定要 \(\le m\)，所以需要修正一下，即为前者为 \(0\) 的方案加后者为 \(0\) 的方案减掉均为 \(0\) 的方案，即 \(g_0=2(m+1)^n-1\)。
最后答案即为 \(\left[x^d\right]{\left(\sum \limits _{i=0}^m g_ix^i\right)}^r\)，\(r\) 很大，且 \(g_0\) 不一定为 \(1\)，洛谷搜索「多项式快速幂（加强版）」即可。
大致为将整个多项式除以一个 \(x^i\) 使得常数项不为 \(0\)，再总体除以常数项即可让其成为 \(1\)，最后将这些除的东西再快速幂后乘回去，需要保留三个东西，原始指数 \(r\) (如果很大设为极大值即可)，\(r \bmod p\)，\(r \bmod \varphi(p)\)。
总时间复杂度为 \(O(m \log m)\)。
M¶
solved by JJLeo
题意¶
\(n\) 个点的树，每个点有一个权值 \(p_i\)，每条边有边权，每个点可以将其相邻的一条边的边权减少 \(p_i\)，如果比 \(0\) 小变为 \(0\)。要求最小化直径。(\(1 \le n \le 10^5\))
题解¶
二分答案 \(\textit{mid}\)，类似一次求直径的 dp，维护当前点 [用 / 没用] 子树中最深的点，合并的时候不能超过当前 \(\textit{mid}\)，最后方案则存在说明 \(\textit{mid}\) 是可以的，总时间复杂度为 \(O(n \log n)\)。
记录¶
寄！
前3h一直关注clarification，后2h卡I常数，顺便ZYF出了M，MJX看clarification出现了嘉然小姐，欲罢不能。
寄！