2020-2021:teams:i_dont_know_png:multi2020-nowcoder-1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-1 [2020/07/15 17:28] qxforever 创建 |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-1 [2020/07/18 21:05] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| [[https://ac.nowcoder.com/acm/contest/5666|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5666|比赛链接]] | ||
| + | |||
| + | ===== A - B-Suffix Array ===== | ||
| + | |||
| + | Upsolved by qxforever. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 对于一个字符串 $s$，定义 $b_i=\min_{1\le j<i,s_j=s_i}i-j$ ，若不存在这样的 $j$ ，则 $b_i=0$ 。 | ||
| + | |||
| + | 给一个长度为 $n$ 的字符串 $s$ ，求所有后缀的 $b$ 数组的字典序。$\sum n\le10^6$ ，字符集 $\{a,b\}$ 。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 对于一个后缀 $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)$ 。 | ||
| + | |||
| + | 于是我们可以 $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.1594805331.txt.gz · 最后更改: 2020/07/15 17:28 由 qxforever
