Year of the Cow

题意

给定若干条牛之间出生年份的关系，例如某头牛出生在另一头牛之前或之后最近的某个生肖年。

Bessie 出生在 Ox 年。要求推导 Elsie 与 Bessie 的出生年份相差多少年。

思路

暴力想法

把 Bessie 的出生年份设为 0。处理一条关系时，从参照牛的年份开始，按 previous 或 next 一年一年移动，直到遇到目标生肖：

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

string animal_name[12] = {
    "Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse",
    "Goat", "Monkey", "Rooster", "Dog", "Pig", "Rat"
};

map<string, int> born_year;

string get_animal(int year) {
    int x = year % 12;
    if (x < 0) {
        x += 12;
    }
    return animal_name[x];
}

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

    born_year["Bessie"] = 0;

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        string cow_a, born, in_word, relation, animal, year_word, from, cow_b;
        cin >> cow_a >> born >> in_word >> relation >> animal >> year_word >> from >> cow_b;

        int y = born_year[cow_b];

        // 暴力逐年移动，直到遇到严格之前/之后的目标生肖年。
        do {
            if (relation == "next") {
                y++;
            } else {
                y--;
            }
        } while (get_animal(y) != animal);

        born_year[cow_a] = y;
    }

    cout << abs(born_year["Elsie"]) << '\n';

    return 0;
}

这个做法很直观，因为每次最多走 12 年。

用模 12 直接跳转

12 个生肖循环出现，把它们编号：

text

1Ox=0, Tiger=1, ..., Rat=11

如果某头牛的相对年份是 year，那么它的生肖就是 year mod 12。

处理一条 next 关系时，设参照牛生肖编号为 base_animal，目标生肖编号为 target_animal：

text

1
2
3diff = (target_animal - base_animal + 12) % 12
如果 diff == 0，则 diff = 12
新牛年份 = base_year + diff

previous 同理，只是向前走：

text

1
2
3diff = (base_animal - target_animal + 12) % 12
如果 diff == 0，则 diff = 12
新牛年份 = base_year - diff

这里 $diff == 0$ 必须改成 12，因为题目要求严格之前或严格之后，不能停在同一年。

代码

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

string animal_name[12] = {
    "Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse",
    "Goat", "Monkey", "Rooster", "Dog", "Pig", "Rat"
};

map<string, int> animal_id;
map<string, int> born_year; // 相对 Bessie 的出生年份，Bessie 为 0。

int get_animal_id(int year) {
    int x = year % 12;
    if (x < 0) {
        x += 12;
    }
    return x;
}

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

    for (int i = 0; i < 12; i++) {
        animal_id[animal_name[i]] = i;
    }

    born_year["Bessie"] = 0;

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        string cow_a, born, in_word, relation, animal, year_word, from, cow_b;
        cin >> cow_a >> born >> in_word >> relation >> animal >> year_word >> from >> cow_b;

        int base_year = born_year[cow_b];
        int base_animal = get_animal_id(base_year);
        int target_animal = animal_id[animal];
        int diff;

        if (relation == "next") {
            diff = (target_animal - base_animal + 12) % 12;
            if (diff == 0) {
                diff = 12;
            }
            born_year[cow_a] = base_year + diff;
        } else {
            diff = (base_animal - target_animal + 12) % 12;
            if (diff == 0) {
                diff = 12;
            }
            born_year[cow_a] = base_year - diff;
        }
    }

    cout << abs(born_year["Elsie"]) << '\n';

    return 0;
}

复杂度

每条关系处理一次，使用 map 查询和插入，时间复杂度为 $O(N \log N)$ 。

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

总结

这题的关键是用相对年份简化问题：不需要知道真实年份，只要知道每头牛相对 Bessie 是第几年。

生肖由年份对 12 的余数决定，所以每条关系都可以用一次模运算推出新牛的年份。

目录

题意

思路

暴力想法

用模 12 直接跳转

代码

复杂度

总结