差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2 [2020/07/17 11:26]
nikkukun
+++ 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2 [2020/08/15 18:05] (当前版本)
nikkukun add J
@@ 行 3: / 行 3: @@
 [[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 =====
@@ 行 44: / 行 97: @@
 类似 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$
+套两个辛普森积分，要调调参数。

CVBB ACM Team

用户工具

站点工具

差别

页面工具