2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2 [2020/07/17 18:40] qxforever |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2 [2020/08/15 18:05] (当前版本) nikkukun add J |
||
|---|---|---|---|
| 行 18: | 行 18: | ||
| 注意自然溢出 hash 的底数不要用偶数。 | 注意自然溢出 hash 的底数不要用偶数。 | ||
| + | |||
| + | ==== 解题思路 2 ==== | ||
| + | |||
| + | 串的所有 border 是其 AC 自动机上的所有 fail 链，因此对每个串的前缀，只需要统计从根节点到该节点上，所有串最近的 fail 链做的贡献之和，这个可以在遍历过程中用一个栈维护。或者可以先处理每条 fail 链上长度平方的增量，这样进出一个节点时就只用加减该节点上贡献的增量即可。 | ||
| + | |||
| + | |||
| ===== B - Boundary ===== | ===== B - Boundary ===== | ||
| 行 43: | 行 49: | ||
| 设叶子个数为 $x$ ，所有叶子都至少被选中 $1$ 次，那么答案的下界为 $\lceil x/2 \rceil$ 。 | 设叶子个数为 $x$ ，所有叶子都至少被选中 $1$ 次，那么答案的下界为 $\lceil x/2 \rceil$ 。 | ||
| - | 这里我的做法是将一个非叶节点设为根节点，每次从根节点不同的两个子树中各选一个叶子，直到所有叶子都在同一棵子树中。 | + | 这里的做法是将一个非叶节点设为根节点，每次从根节点不同的两个子树中各选一个叶子，直到所有叶子都在同一棵子树中。 |
| 与树的重心类似，这里提出了一个树的叶子的重心的概念，即子树的叶子数量的最大值最小的节点。对于这样的节点，子树叶子数量的最大值 $\le \lceil x/2 \rceil$。选这样的节点为根，可以保证当所有叶子都在同一颗子树中时，子树中剩余的叶子最多为 $1$ 。于是我们就构造出了一种答案为 $\lceil x/2 \rceil$ 的方案。 | 与树的重心类似，这里提出了一个树的叶子的重心的概念，即子树的叶子数量的最大值最小的节点。对于这样的节点，子树叶子数量的最大值 $\le \lceil x/2 \rceil$。选这样的节点为根，可以保证当所有叶子都在同一颗子树中时，子树中剩余的叶子最多为 $1$ 。于是我们就构造出了一种答案为 $\lceil x/2 \rceil$ 的方案。 | ||
| + | ===== D - Duration ===== | ||
| + | |||
| + | 签到题 | ||
| ===== E - Exclusive OR ===== | ===== E - Exclusive OR ===== | ||
| 行 111: | 行 120: | ||
| 用区间代表的二元组建成一个 $n \times n$ 的网格图，相当于禁掉一些边，使得 $(1, n)$ 不能走到 $y = x$ 的位置上。这个东西是平面图最小割，参考 [[https://www.luogu.com.cn/problem/P4001 | 狼抓兔子]] 跑最短路即可。 | 用区间代表的二元组建成一个 $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$ | ||
| + | |||
| + | 套两个辛普森积分，要调调参数。 | ||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-2.1594982427.txt.gz · 最后更改: 2020/07/17 18:40 由 qxforever
