2024.5 刷题笔记
CF1972D2
题意
给定 $n,m(1\le n,m\le2\cdot 10^6)$，求满足 $1\le a\le n,1\le b\le m$ 且 $b\cdot \gcd(a,b)$ 是 $a+b$ 的倍数的有序对 $(a,b)$ 的个数。
做法
- 记 $g=\gcd(a,b)$。由于 $bg$ 和 $a+b$ 都是 $g$ 的倍数，尝试把 $g$ 约去，得 $b=yg$ 是 $x+y$ 的倍数，其中 $a=xg,b=yg$
- 此处还有一个容易忽略的重要性质，即 $\gcd(x,y)=1$，进而有 $\gcd(x+y,y)=1$。也就是说，$y$ 中不含 $x+y$ 的质因子，可以从式子中移除，得到 $g$ 是 $x+y$ 的倍数
- 由于 $x+y<g$ 且 $xg\le n,yg\le m$，可以发现无论是 $g$ 较小时还是 $g$ 较大时，$x+y$ 都较小。因此尝试先枚举 $g$ 再枚举 $x+y$ 再枚举 $x$，发现枚举次数较小，刚好能卡过
CF1972E
题意
给定长度为 $n(n\le 2\cdot 10^5)$ 的数组 $b$ 和正整数 $k(k\le 10^9)$，求一个数组 $a$，使得 $b=f^k(a)\text{ mod }998244353$，其中 $f(a)$ 表示对 $a$ 建的树状数组，$f^k(a)$ 表示嵌套 $k$ 层操作。
做法
- 在建立树状数组的过程中，在对应的树上，每个结点都会贡献给它的全体祖先
- $k$ 次操作后，每个结点对其父结点的贡献次数为 $k$，对其 $2$ 阶祖先的贡献次数为 $\sum_{i=1}^{k}i$，对其 $3$ 阶祖先的贡献次数为 $\sum_{i=1}^{k}\sum_{j=1}^{i}i$。据此类推，对其 $b$ 阶祖先的贡献次数为一个长度为 $k$ 的数组求 $b$ 次前缀和后的末元素大小。这个问题相当于一个 $k\times (b+1)$ 的格路问题模型，结果为 $C(k+(b+1)-2,k-1)=C(k+b-1,b)$
- 按照 lowbit 从小到大的顺序使每个位置删去贡献即得 $a$
CF1916E
题意
给定一棵大小为 $n(n\le 3\cdot 10^5)$ 的有根树以及每个结点的颜色 $a(a_i\in[1,n])$，求一对结点 $(u,v)$ 使得 $diff(u,lca(u,v))\cdot diff(v,lca(u,v))$ 最大。其中 $diff$ 代表两个结点间路径上的颜色种数，$u,v$ 可以相同。
做法
- 枚举 lca，当 $x$ 作 lca 时找到 $x$ 所有子结点子树中最优的链，选择其中最优的两条链相乘来更新答案。剩下的关键问题是如何快速求出以某结点为根的最优链
- 考虑在 DFS 回溯的过程中维护当前结点子树中所有结点到当前结点的链的答案，其实只需要在回溯过程中不断将重复颜色的贡献删去即可。当回溯到结点 $x$ 时，需要加上 $x$ 的贡献，其作用于 $x$ 的子树；同时需要删去 $x$ 下方距其最近的同色结点 ${y}$ 的贡献，这些贡献作用于 $y_i$ 的子树。为了方便对子树信息进行修改，可以使用欧拉序将树映射到序列，再用线段树维护序列上每个结点到当前结点的链答案。
GYM105139K
题意
给定数轴上的 $n(n\le 10^6)$ 个一维坐标 $a(0\le a_i<998244353)$，每次随机选择两个相邻的坐标，将它们用它们的平均值替换，直到只剩一个值。求最终值的数学期望。
做法
- 分别计算每个数的贡献系数，假设某个数当前左边有 $x$ 个数，右边有 $y$ 个数，其贡献系数记为 $f_{i,j}$。根据是否选中该数以及选中该数的左边还是右边分四类情况讨论，得 $f_{i,j}=\frac{i-1}{i+j}f_{i-1,j}+\frac{1}{i+j}\frac{1}{2}f_{i-1,j}+\frac{j-1}{i+j}f_{i,j-1}+\frac{1}{i+j}\frac{1}{2}f_{i,j-1}=\frac{1}{i+j}((i-\frac{1}{2})f_{i-1,j}+(j-\frac{1}{2})f_{i,j-1})$
- 令 $g_{i,j}=(i+j)!f_{i,j}$，则 $g_{i,j}=(i-\frac{1}{2})g_{i-1,j}+(j-\frac{1}{2})g_{i,j-1}$ 恰好是一个网格图路径计数问题的答案，可以用组合数计算
- 最终答案为 $\sum_{i=0}^{i=n-1}f_{i,n-1-i}$
GYM105158D
题意
给定 $n(n\le 2\times 10^5)$ 个二维点坐标，求所有点对中曼哈顿距离比欧几里得距离 $\frac{\lVert P_iP_j\rVert _1}{\lVert P_iP_j\rVert _2}$ 的最大值
做法
- 分析式子得：所求即为连线角度最接近 $45^\circ$ 或 $135^\circ$ 的点对
- 关键结论：分别按照 $x+y$ 和 $x-y$ 排序，最优点对一定在其中一个排序下是相邻的。证明可以考虑任意三个点连成的三角形，其中最上方和最下方的点的连线一定不会是三角形中最接近水平的。
GYM105143D
题意
给定长度为 $n(n\le 5000)$ 的数组 $a$，求 $F_{i,j}(1\le i\le n,1\le j\le 2n)$，其中 $F_{i,j}$ 表示从位置 $i$ 出发走 $j$ 步的所有路径中经过的所有位置元素和最大的路径对应的元素和。
做法
- 思考答案的计算方法，有 $F_{i,j}=\max{g_{i,j},g_{i-1,j-1},g_{i-2,j-2},\cdots,g_{i+1,j-1},g_{i+2,j-2},\cdots}$，其中 $g_{i,j}$ 表示从 $i$ 出发往一个方向走 $j$ 步的最大结果
- 先预处理出 $g$ 的所有元素值，然后分别沿着两条对角线求前缀最大值即可 $O(1)$ 计算出 $F$ 的一个元素值
- 但是会 MLE，因此还需要在第二维上滚动数组优化一下
2024.5 刷题笔记