2020-2021:teams:i_dont_know_png:multi2020-nowcoder-1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-1 [2020/07/15 18:03] qxforever |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-1 [2020/07/18 21:05] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| 对于一个后缀 $t$ ，首先考虑 $t$ 中 a，b 同时出现的最短前缀，其长度记为 $f(t)$ 。其 $b$ 数组的开头为 $1,1,1,1....0$ 。于是若 $f(s)<f(t)$ ，则 $b(s)<b(t)$ 。 | 对于一个后缀 $t$ ，首先考虑 $t$ 中 a，b 同时出现的最短前缀，其长度记为 $f(t)$ 。其 $b$ 数组的开头为 $1,1,1,1....0$ 。于是若 $f(s)<f(t)$ ，则 $b(s)<b(t)$ 。 | ||
| - | 当 $f(s)=f(t)$ 时，需要比较两个串的第 $\mathrm{lcp}(s,t)+1$ 位。若 $s_{\mathrm{lcp}+1}=s_{\mathrm{lcp}}$ ，则 $b(s)<b(t)$ 。 | + | 当 $f(s)=f(t)$ 时，需要比较两个串的第 $\mathrm{LCP}(s,t)+1$ 位。若 $s_{\mathrm{LCP}+1}=s_{\mathrm{LCP}}$ ，则 $b(s)<b(t)$ 。 |
| 于是我们可以 $O(1)$ 比较两个后缀 $b$ 数组的大小关系。复杂度为 $O(n\log n)$ 。 | 于是我们可以 $O(1)$ 比较两个后缀 $b$ 数组的大小关系。复杂度为 $O(n\log n)$ 。 | ||
| + | |||
| + | ===== F - Infinite String Comparision ===== | ||
| + | |||
| + | Solved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给两个串，问分别无限拼起来两串哪个大。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 暴力比较前 $2\times \max(l_a,l_b)$ 位即可。 | ||
| + | |||
| + | ===== J - Easy Integration ===== | ||
| + | |||
| + | Solved by WolframAlpha. | ||
| + | |||
| + | nb 题，跳了 | ||
| + | |||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-1.1594807431.txt.gz · 最后更改: 2020/07/15 18:03 由 qxforever
