The 'Winning' Gene

题目描述

注意：本题的内存限制为 512MB，是默认值的两倍。 在多年举办比赛并一次又一次看到 Bessie 获得第一名之后，Farmer John 意识到这不可能是偶然。相反，他认为 Bessie 的 DNA 中一定编码了“获胜”基因，于是他开始寻找这个“获胜”基因。

他设计了一套流程来识别这个“获胜”基因的可能候选。他取出 Bessie 的基因组，它是一个长度为 $N$ 的字符串 $S$，其中 $1 \leq N \leq 3000$。他选择一对 $(K,L)$，满足 $1 \leq L \leq K \leq N$，表示“获胜”基因候选的长度为 $L$，并且它将出现在一个更长的长度为 $K$ 的子串中。为了识别该基因，他取出 $S$ 中所有长度为 $K$ 的子串，我们称其为一个 $k$-mer。对于某个给定的 $k$-mer，他取出其中所有长度为 $L$ 的子串，找出按字典序最小的那个子串作为“获胜”基因候选（如果有并列，则选择最靠左的那个子串），然后将该子串在 $S$ 中的起始位置（$0$ 下标）记为 $p_i$，并加入集合 $P$。

由于他尚未确定 $K$ 和 $L$，他想知道对于每一对 $(K,L)$ 会有多少个候选。

对于每个 $v$（$1\dots N$），请帮助他确定满足 $|P|=v$ 的 $(K,L)$ 对的数量。

输入格式

输入为： $N$ 表示字符串长度。$S$ 表示给定的字符串。 保证所有字符均为大写字母，且 $s_i \in A-Z$，因为牛的遗传学比我们先进得多。

输出格式

对于每个 $v$（$1\dots N$），输出满足 $|P|=v$ 的 $(K,L)$ 对的数量，每个数占一行。

8
AGTCAACG

11
10
5
4
2
2
1
1

提示

在该测试用例中，输出的第三行是 5，因为恰好有 5 对 $K$ 和 $L$ 会产生三个“获胜”基因候选。这些候选如下（其中 $p_i$ 为 $0$ 下标）： (4,2) -> P = [0,3,4] (5,3) -> P = [0,3,4] (6,4) -> P = [0,3,4] (6,5) -> P = [0,1,3] (6,6) -> P = [0,1,2] 要看 (4,2) 如何得到这些结果，我们取出所有 $4$-mer： AGTC GTCA TCAA CAAC AACG 对每个 $4$-mer，我们找出按字典序最小的长度为 2 的子串： AGTC -> AG GTCA -> CA TCAA -> AA CAAC -> AA AACG -> AA 我们取出所有这些子串在原字符串中的位置并加入集合 $P$，得到 $P = [0,3,4]$。 另一方面，如果关注 $(4,1)$，我们会发现这只会产生总共 $2$ 个“获胜”基因候选。如果我们取出所有 $4$-mer 并找出按字典序最小的长度为 $1$ 的子串（用 A、A'、A* 来区分不同的 A），则得到： AGTC -> A GTCA' -> A' TCA'A* -> A' CA'AC -> A' A'ACG -> A' 尽管在最后 3 个情况中 A' 和 A* 都是按字典序最小的，但最靠左的子串优先，因此这些情况下都只将 A' 计为唯一候选。这意味着 $P = [0,4]$。 SCORING: Inputs 2-4: $N \leq 100$ Inputs 5-7: $N \leq 500$ Inputs 8-16: No additional constraints. Problem credits: Suhas Nagar

标签: USACO|2024|Silver

来源

USACO|2024|Silver