Cow Gymnastics

题意

有 K 次训练课，每次都会给 N 头奶牛排一个名次。

如果奶牛 a 在每一次训练课中都排在奶牛 b 前面，就称 (a,b) 是一对一致关系。

求一致关系的数量。

思路

朴素判断

可以枚举两头奶牛 a、b，然后在每场排名里扫描它们的位置：

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/**
 * 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 14:34
 * update_at: 2026-07-11 14:36
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 15;
const int MAXN = 25;

int k, n;
int rank_list[MAXK][MAXN]; // 每场训练的排名顺序

int find_pos(int session, int cow) {
    for (int i = 1; i <= n; i++) {
        if (rank_list[session][i] == cow) {
            return i;
        }
    }
    return -1;
}

bool always_better(int a, int b) {
    for (int s = 1; s <= k; s++) {
        int pos_a = find_pos(s, a);
        int pos_b = find_pos(s, b);
        if (pos_a > pos_b) {
            return false;
        }
    }
    return true;
}

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

    cin >> k >> n;
    for (int s = 1; s <= k; s++) {
        for (int i = 1; i <= n; i++) {
            cin >> rank_list[s][i];
        }
    }

    int ans = 0;

    // 朴素做法：每次判断一对牛时，都去每场排名里扫描位置。
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            if (a == b) {
                continue;
            }
            if (always_better(a, b)) {
                ans++;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

这个做法很直观。由于数据范围小，它已经足够快。

位置表

为了让判断更清楚，读入时可以预处理位置表：

text

1pos[s][cow] = cow 在第 s 场训练中的排名位置

位置越小，说明排名越靠前。

对于一对有方向的奶牛 (a,b)，如果每一场都满足：

text

1pos[s][a] < pos[s][b]

那么 a 就始终比 b 表现好，答案加一。

注意这里要枚举有序对 (a,b)，而不是只枚举 a < b。

代码

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/**
 * 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 14:34
 * update_at: 2026-07-11 14:36
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 15;
const int MAXN = 25;

int k, n;
int rank_list[MAXK][MAXN]; // 每场训练的排名顺序
int pos[MAXK][MAXN];       // pos[s][cow] 表示 cow 在第 s 场中的名次位置

bool always_better(int a, int b) {
    for (int s = 1; s <= k; s++) {
        if (pos[s][a] > pos[s][b]) {
            return false;
        }
    }
    return true;
}

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

    cin >> k >> n;
    for (int s = 1; s <= k; s++) {
        for (int i = 1; i <= n; i++) {
            cin >> rank_list[s][i];
            pos[s][rank_list[s][i]] = i;
        }
    }

    int ans = 0;

    // 枚举有方向的二元关系：a 是否每次都排在 b 前面。
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            if (a == b) {
                continue;
            }
            if (always_better(a, b)) {
                ans++;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

枚举有序对是 $O(N^2)$ ，每对检查 K 场训练，时间复杂度为 $O(KN^2)$ 。

使用排名数组和位置数组，空间复杂度为 $O(KN)$ 。

总结

这题本质是在统计稳定的二元先后关系。

先把每场排名转成 pos 位置表，再枚举有序对判断“是否每次都靠前”，代码会很直接。

目录

题意

思路

朴素判断

位置表

代码

复杂度

总结