#PU1424. USACO 2024 US Open Contest, Silver — Problem 3. The 'Winning' Gene

    ID: 1662 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:open24来源:usaco.orgscoring:equal_test_cases哈希字典树

USACO 2024 US Open Contest, Silver — Problem 3. The 'Winning' Gene

USACO 2024 US Open Contest, Silver — Problem 3. The 'Winning' Gene

题目描述

Note: The memory limit for this problem is 512MB, twice the default. After years of hosting games and watching Bessie get first place over and over, Farmer John has realized that this can't be accidental. Instead, he concludes that Bessie must have winning coded into her DNA so he sets out to find this "winning" gene. He devises a process to identify possible candidates for this "winning" gene. He takes Bessie's genome, which is a string SS of length NN where 1≤N≤30001 \leq N \leq 3000. He picks some pair (K,L)(K,L) where 1≤L≤K≤N1 \leq L \leq K \leq N representing that the "winning" gene candidates will have length LL and will be found within a larger KK length substring. To identify the gene, he takes all KK length substrings from SS which we will call a kk-mer. For a given kk-mer, he takes all length LL substrings, identifies the lexicographically minimal substring as a winning gene candidate (choosing the leftmost such substring if there is a tie), and then writes down the 00-indexed position pip_i where that substring starts in SS to a set PP. Since he hasn't picked KK and LL yet, he wants to know how many candidates there will be for every pair of (K,L)(K,L). For each vv in 1…N1\dots N, help him determine the number of (K,L)(K,L) pairs with ∣P∣=v|P|=v.

输入格式

NN representing the length of the string. SS representing the given string. All characters are guaranteed to be uppercase characters where si∈A−Zs_i \in A-Z since bovine genetics are far more advanced than ours.

输出格式

For each vv in 1…N1\dots N, output the number of (K,L)(K,L) pairs with ∣P∣=v|P|=v, with each number on a separate line.

数据范围

Inputs 2-4: N≤100N \leq 100 Inputs 5-7: N≤500N \leq 500 Inputs 8-16: No additional constraints. Problem credits: Suhas Nagar

样例

样例 1

8
AGTCAACG
11
10
5
4
2
2
1
1
In this test case, the third line of the output is 5 because we see that there are exactly 5 pairs of $K$ and $L$ that allow for
three "winning" gene candidates.  These candidates are (where $p_i$ is $0$-indexed):
(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]
To see how (4,2) leads to these results, we take all $4$-mers
AGTC
GTCA
TCAA
CAAC
AACG
For each $4$-mer, we identify the lexicographically minimal length 2 substring
AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA
We take the positions of all these substrings in the original string and add
them to a set $P$ to get $P = [0,3,4]$.
On the other hand, if we focus on the pair $(4,1)$, we see that this only leads
to $2$ total "winning" gene candidates. If we take all $4$-mers and identify the
lexicographically minimum length $1$ substring (using A and A' and A* to
distinguish the different As), we get
AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'
While both A' and A* are lexicographically minimal in the last 3 cases, the
leftmost substring takes precedence so A' is counted as the only candidate in
all of these cases. This means that $P = [0,4]$.