The 'Winning' Gene

GitHub 跳转原题关系图返回列表

固定候选起点和长度，用 LCP 与单调指针求最大可行 K，再用差分统计每个 pair 的 winner 数。

OJ: usaco

题目 ID: 1424

难度:普及+/提高

标签:字符串LCP差分usaco

日期: 2026-07-11 20:58

题意

给定字符串 $S$ ，长度为 $N$ 。

对每一对 $(K,L)$ ，其中 $1\leqslant L\leqslant K\leqslant N$ ：

枚举所有长度为 $K$ 的子串；
在每个长度为 $K$ 的子串中，找字典序最小的长度为 $L$ 的子串；
如果有多个最小值，取最左边的那个；
把这些 winner 在原串里的起点加入集合 $P$ 。

要求对每个 $v=1..N$ ，统计有多少对 $(K,L)$ 满足 $|P|=v$ 。

思路

先看一个直接模拟题意的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:58
 * update_at: 2026-07-11 21:00
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
string s;
long long answer_cnt[MAXN];
bool marked[MAXN];

int compare_sub(int i, int j, int len) {
    for (int k = 0; k < len; k++) {
        if (s[i + k] < s[j + k]) return -1;
        if (s[i + k] > s[j + k]) return 1;
    }
    return 0;
}

int calc_pair(int big_len, int small_len) {
    for (int i = 0; i < n; i++) {
        marked[i] = false;
    }

    for (int start = 0; start + big_len <= n; start++) {
        int best_pos = start;
        for (int p = start + 1; p + small_len <= start + big_len; p++) {
            if (compare_sub(p, best_pos, small_len) < 0) {
                best_pos = p;
            }
        }
        marked[best_pos] = true;
    }

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (marked[i]) cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;

    for (int big_len = 1; big_len <= n; big_len++) {
        for (int small_len = 1; small_len <= big_len; small_len++) {
            int cnt = calc_pair(big_len, small_len);
            answer_cnt[cnt]++;
        }
    }

    for (int v = 1; v <= n; v++) {
        cout << answer_cnt[v] << '\n';
    }

    return 0;
}

暴力枚举每个 $(K,L)$ ，再枚举每个 K-mer 内的所有长度 $L$ 子串。它很适合确认题意，但复杂度过高。

换一个方向：不直接问某个 $(K,L)$ 有多少 winner，而是固定一个位置 $p$ 和长度 $L$ ，问它能在哪些窗口长度 $K$ 下成为 winner。

设当前候选串为：

text

1T = S[p..p+L-1]

如果某个窗口要让 $p$ 成为 winner，它不能包含下面这些阻挡位置：

位置	阻挡条件	原因
左侧 $a<p$	$S[a..a+L-1]\leqslant T$	更小会赢；相等时最左边会赢
右侧 $b>p$	$S[b..b+L-1]<T$	只有严格更小时才会抢走 winner

只需要看最近的两个阻挡位置：

a：左侧最大的阻挡位置；
b：右侧最小的阻挡位置。

为了避开左阻挡，可以把窗口起点放在 a+1。这个窗口中最后一个长度 $L$ 子串的起点是：

text

1a + 1 + K - L

它必须在 b 左边：

text

1a + 1 + K - L < b

整理得到：

text

1K <= b + L - a - 2

所以固定 $p,L$ 后，它会对所有窗口长度：

text

1L <= K <= maxK

贡献一个 winner。

接下来要快速求左右阻挡位置。先预处理 LCP：

text

1lcp[i][j] = S[i..] 和 S[j..] 的最长公共前缀长度

倒序转移：

text

1S[i] == S[j] 时，lcp[i][j] = lcp[i+1][j+1] + 1

有了 LCP，两个长度为 $L$ 的子串比较可以做到 $O(1)$ 。

对固定 p，随着 L 变化，左右阻挡位置可以用单调指针维护。于是所有 p,L 的贡献可以在 $O(N^2)$ 内处理。

最后用 delta_cnt[L][maxK]++ 记录区间 [L,maxK] 的贡献。对每个 L 从大到小扫 K：

text

1
2winners += delta_cnt[L][K]
answer_cnt[winners]++

此时 winners 就是当前 pair (K,L) 的 $|P|$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:58
 * update_at: 2026-07-11 21:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;

int n;
string s;

int lcp[MAXN][MAXN];   // lcp[i][j] 表示 s[i..] 和 s[j..] 的最长公共前缀长度。
int delta_cnt[MAXN][MAXN];
int left_limit[MAXN], right_limit[MAXN];
long long answer_cnt[MAXN];

// 比较 s[i..i+len-1] 和 s[j..j+len-1]。
// 返回 -1/0/1，分别表示前者更小、相等、前者更大。
int compare_sub(int i, int j, int len) {
    int same = lcp[i][j];
    if (same >= len) return 0;
    if (i + same == n) return -1;
    if (j + same == n) return 1;
    if (s[i + same] < s[j + same]) return -1;
    return 1;
}

void build_lcp() {
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (s[i] == s[j]) {
                lcp[i][j] = lcp[i + 1][j + 1] + 1;
            }
        }
    }
}

void solve() {
    build_lcp();

    for (int p = 0; p < n; p++) {
        int b_cand = p + 1;
        for (int len = n; len >= 1; len--) {
            // 右侧第一个严格小于当前位置子串的位置，会抢走 winner。
            while (b_cand < n && compare_sub(p, b_cand, len) <= 0) {
                b_cand++;
            }
            right_limit[len] = min(b_cand + len, n + 1);
        }

        int a_cand = p - 1;
        for (int len = 1; len <= n; len++) {
            // 左侧小于或等于当前位置子串的位置，会因为字典序或最左规则抢走 winner。
            while (a_cand >= 0 && compare_sub(p, a_cand, len) < 0) {
                a_cand--;
            }
            left_limit[len] = a_cand + 1;
        }

        for (int len = 1; len <= n; len++) {
            if (p + len > n) continue;

            int max_k = right_limit[len] - left_limit[len] - 1;
            if (max_k > n) max_k = n;
            if (max_k >= len) {
                delta_cnt[len][max_k]++;
            }
        }
    }

    for (int len = 1; len <= n; len++) {
        int winners = 0;
        for (int k = n; k >= len; k--) {
            winners += delta_cnt[len][k];
            answer_cnt[winners]++;
        }
    }

    for (int v = 1; v <= n; v++) {
        cout << answer_cnt[v] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;
    solve();

    return 0;
}

复杂度

预处理 LCP 为 $O(N^2)$ 。

枚举每个位置并用单调指针统计贡献，总复杂度为 $O(N^2)$ 。

最后汇总 delta_cnt 也是 $O(N^2)$ 。

空间复杂度为 $O(N^2)$ 。

总结

本题的关键转化是：从“一个 $(K,L)$ 有哪些 winner”，改成“一个位置 $p$ 能为哪些 $(K,L)$ 贡献 winner”。

左侧相等会抢走 winner，右侧相等不会抢走 winner，这是最容易写错的地方。处理好左右阻挡后，每个位置的贡献就是一段连续的窗口长度区间，再用差分统计即可。

1424 The ‘Winning’ Gene

赛事信息

USACO 2024 US Open Contest, Silver

题目描述

注意：本题的内存限制为 512MB，通常限制的 2 倍。 在多年举办比赛并看着 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$ 中的起始位置 $p_i$ （从 $0$ 开始索引）写入一个集合 $P$ 。由于他还没有选定 $K$ 和 $L$ ，他想知道每对 $(K,L)$ 将有多少个候选。对于 $1\dots N$ 中的每一个 $v$ ，帮助他求出满足 $|P|=v$ 的 $(K,L)$ 对的数量。

输入格式

输入的第一行包含 $N$ ，为字符串的长度。第二行包含 $S$ ，为给定的字符串。输入保证所有字符均为大写字符，其中 $s_i \in A-Z$ ，因为奶牛遗传学远比我们的高级。

输出格式

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

输入输出样例 #1

输入 #1

text

1
28
AGTCAACG

输出 #1

text

样例说明

在这个测试用例中，输出的第三行为 5 是因为我们发现恰好有 5 对 $K$ 和 $L$ 存在三个「胜利」基因候选。这些候选为（其中 $p_i$ 从 $0$ 开始索引）：

text

1
2
3
4
5
6
(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

text

1
2
3
4
5
6
AGTC
GTCA
TCAA
CAAC
AACG

对于每一个 $4$ -mer，我们识别出字典序最小的长度为 2 的子串

text

1
2
3
4
5
6
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），我们得到

text

1
2
3
4
5
6
AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'

尽管 A’ 和 A* 在最后 3 种情况下字典序均为最小，但最左边的子串优先，因此仅有 A’ 在所有这些情况中被视为候选。这意味着 $P = [0,4]$ 。

测试点性质

测试点 2-4： $N \leq 100$ 。
测试点 5-7： $N \leq 500$ 。
测试点 8-16：没有额外限制。

The 'Winning' Gene

目录

题意

思路

代码

复杂度

总结