====== 2020牛客暑期多校训练营（第二场） ====== [[https://ac.nowcoder.com/acm/contest/5667|比赛链接]] ===== A - All with Pairs ===== Upsolved by qxforever. ==== 题目描述 ==== 对两个字符串 $s,t$ 定义 $f(s,t)=\max(s[1..i]=t[\vert t\vert-i+1..\vert t\vert])$，即前缀等于后缀的最大长度。 给 $n$ 个字符串，求 $\sum_i\sum_j f(s_i,s_j)^2$ ，结果对 $998244353$ 取模。$\sum n\le10 ^5$，$\sum \vert s\vert\le 10^6$ ==== 解题思路 ==== 预处理出来所有前缀的 hash 值，存入 map 。计算答案时，对每个后缀的 hash ，在 map 中查询对应前缀的个数。但是这样会有重复，对每个串反转后求 next 数组即可。 注意自然溢出 hash 的底数不要用偶数。 ==== 解题思路 2 ==== 串的所有 border 是其 AC 自动机上的所有 fail 链，因此对每个串的前缀，只需要统计从根节点到该节点上，所有串最近的 fail 链做的贡献之和，这个可以在遍历过程中用一个栈维护。或者可以先处理每条 fail 链上长度平方的增量，这样进出一个节点时就只用加减该节点上贡献的增量即可。 ===== B - Boundary ===== Upsolved by qxforever. ==== 题目描述 ==== 给二维平面上 $n$ 个点，对于任意过点 $(0,0)$ 的圆，求圆边界上的点数量的最大值。$n\le 2000$ ==== 解题思路 ==== 对任意两个点以及 $(0,0)$ ，求出这三点确定的圆的圆心，并记录每个圆心的出现次数 $\text{cnt}$。设边界上的点数量为 $k$ ，则有 $\binom{k}{2}=\max\text{cnt}$ 。圆心坐标必定为有理数，用 map 维护一个分数类的 pair 即可。注意常数优化。 ===== C - Cover the Tree ===== Solved by qxforever. ==== 题目描述 ==== 给一颗 $n$ 个点的树，求链数最少的链覆盖，并输出方案。每条链至少被覆盖 $1$ 次。$n\le 2\times 10^5$ ==== 解题思路 ==== 设叶子个数为 $x$ ，所有叶子都至少被选中 $1$ 次，那么答案的下界为 $\lceil x/2 \rceil$ 。 这里的做法是将一个非叶节点设为根节点，每次从根节点不同的两个子树中各选一个叶子，直到所有叶子都在同一棵子树中。 与树的重心类似，这里提出了一个树的叶子的重心的概念，即子树的叶子数量的最大值最小的节点。对于这样的节点，子树叶子数量的最大值 $\le \lceil x/2 \rceil$。选这样的节点为根，可以保证当所有叶子都在同一颗子树中时，子树中剩余的叶子最多为 $1$ 。于是我们就构造出了一种答案为 $\lceil x/2 \rceil$ 的方案。 ===== D - Duration ===== 签到题 ===== E - Exclusive OR ===== Upsolved by nikkukun. ==== 题目描述 ==== 给定 $n \leq 2 \times 10^5$ 个 $[0, 2^{18})$ 内的数，求用恰好 $1, 2, \ldots, n$ 个数能异或出来的最大值。 ==== 解题思路 ==== 根据线性基的特性，只要用基底的个数个线性无关的基就能获得最大值，因此 $i$ 并非很小的时候只要在 $i-2$ 答案的基础上随便加上两个相同的数即可。 令 $f(i)$ 表示 $a_i$ 是否出现，则做 $i$ 次异或 FWT 就能得到 $i$ 个数能否表示出来的答案，这里选择处理前 20 次即可。 ===== F - Fake Maxpooling ===== Solved by nikkukun. ==== 题目描述 ==== 给定 $n \times m$ 的矩阵，第 $i$ 行 $j$ 列的数是 $\mathrm{lcm}(i, j)$，求所有 $k \times k$ 子矩阵最大值的和。 ==== 解题思路 ==== 降维，做两次单调队列。 ===== G - Greater and Greater ===== Solved by nikkukun. ==== 题目描述 ==== 给 $n \leq 1.5 \times 10^5$ 个数 $a_1, a_2, \ldots, a_n$ 和 $m \leq \min(n, 40000)$ 个数 $b_1, b_2, \ldots, b_m$，求 $a$ 中有多少长度为 $m$ 的子区间满足对应位置全都不小于 $b$ 的对应位置。 ==== 解题思路 ==== 类似 bitset 加速字符串匹配的类型，由大到小枚举 $b$ 中的元素，用一个 bitset 表示 $a$ 中不小于该元素的位置，这样 bitset 的变化量是 $O(n)$ 的，总时间复杂度 $O\left(\dfrac {nm}w \right)$。 ===== I - Interval ===== Upsolved by nikkukun. ==== 题目描述 ==== 区间 $[l, r]$ 可以任意变到 $[l+1, r]$ 或 $[l, r-1]$，同时提供了 $m$ 种已有的方案，每种方案仅属于以下一种： - 用一些花费禁掉 $[l_i, r_i]$ 与 $[l_i+1, r_i]$ 之间的双向转化 - 用一些花费禁掉 $[l_i, r_i]$ 与 $[l_i, r_i-1]$ 之间的双向转化 初始有区间 $[1, n]$（$n \leq 500$），你可以选择一些方案，使得任意转换过程中不出现 $l = r$ 的区间，并求最小花费。 ==== 解题思路 ==== 用区间代表的二元组建成一个 $n \times n$ 的网格图，相当于禁掉一些边，使得 $(1, n)$ 不能走到 $y = x$ 的位置上。这个东西是平面图最小割，参考 [[https://www.luogu.com.cn/problem/P4001 | 狼抓兔子]] 跑最短路即可。 ===== J - Just Shuffle ===== Solved by nikkukun & qxforever. ==== 题目描述 ==== 给一个长度 $n \leq 10^5$ 的置换 $A$ 和一个大质数 $k \in [10^8, 10^9]$，求是否存在另一个置换 $P$ 使得 $P^k = A$。 ==== 解题思路 ==== 考虑 $P$ 轮换乘积形式中的每个轮换，其 $k$ 次方相当于轮换移动了 $k$ 次。由于 $k$ 是个大质数，其必然与轮换长度互质，故轮换操作不会改变轮换长度（不互质的情况可能会让一个轮换变成很多小轮换），直接将 $A$ 中的每个轮换倒着移动 $k$ 次即可还原。 总时间复杂度 $O(n)$。 ===== K - Keyboard Free ===== Solved by qxforever & Potasium. ==== 题目描述 ==== 给三个同心圆的半径，每个圆上随机取一点，求所成三角形面积的期望。 ==== 解题思路 ==== 根据两个角度暴力计算推出二重积分式：$\frac{1}{(8{\pi}^2)}\int_{0}^{2\pi}\int_{0}^{2\pi} r_1(r_2sin(x)-r_3sin(y))+r_2r_3(cos(x)sin(y)-cos(y)sin(x)) \text{d}x\text{d}y$ 套两个辛普森积分，要调调参数。