[COCI 2007/2008 #4] VAUVAU

题意

两条狗都会无限重复自己的行为周期：

第一条狗先暴躁 a 分钟，再安静 b 分钟
第二条狗先暴躁 c 分钟，再安静 d 分钟

给出三个人到达的时刻 p,m,g，要求分别输出那一刻有几条狗处于暴躁状态：

both：两条都在叫
one：只有一条在叫
none：都不在叫

思路

先看一个最直观的朴素解：

对某个到达时刻 t，从第 1 分钟开始一分一分模拟狗的状态：

先连续 angry 分钟算作暴躁
再连续 calm 分钟算作安静
循环往复，直到走到第 t 分钟

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

int a, b, c, d;
int p, m, g;

// 直接按分钟模拟到第 t 分钟，看这一分钟狗是否在叫。
int is_angry(int angry, int calm, int t) {
    int len = angry + calm;
    int now = 1;

    while (now <= t) {
        for (int i = 1; i <= angry && now <= t; i++, now++) {
            if (now == t) {
                return 1;
            }
        }
        for (int i = 1; i <= calm && now <= t; i++, now++) {
            if (now == t) {
                return 0;
            }
        }
    }

    return 0;
}

void print_state(int t) {
    int cnt = 0;
    cnt += is_angry(a, b, t);
    cnt += is_angry(c, d, t);

    if (cnt == 2) {
        cout << "both\n";
    }
    else if (cnt == 1) {
        cout << "one\n";
    }
    else {
        cout << "none\n";
    }
}

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

    cin >> a >> b >> c >> d;
    cin >> p >> m >> g;

    print_state(p);
    print_state(m);
    print_state(g);

    return 0;
}

这个办法能帮助理解题意，但其实没必要一分一分往前走。

关键在于：每条狗的状态是一个固定周期。

例如第一条狗的周期长度就是 a + b。
对于任意时刻 t，只要看它在当前周期里的位置即可：

pos = t % (a + b)
如果 pos != 0 且 pos <= a，说明落在暴躁时间段
否则就落在安静时间段

第二条狗完全同理。

分别判断两条狗在该时刻是否暴躁，再把结果加起来，就能输出 both、one 或 none。

代码

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#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;
int p, m, g;

// 判断某条狗在第 t 分钟时是否处于暴躁状态。
int is_angry(int angry, int calm, int t) {
    int len = angry + calm;
    int pos = t % len;
    if (pos != 0 && pos <= angry) {
        return 1;
    }
    return 0;
}

void print_state(int t) {
    int cnt = 0;
    cnt += is_angry(a, b, t);
    cnt += is_angry(c, d, t);

    if (cnt == 2) {
        cout << "both\n";
    }
    else if (cnt == 1) {
        cout << "one\n";
    }
    else {
        cout << "none\n";
    }
}

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

    cin >> a >> b >> c >> d;
    cin >> p >> m >> g;

    print_state(p);
    print_state(m);
    print_state(g);

    return 0;
}

复杂度

每个到达时刻只做常数次运算，总时间复杂度是 $O(1)$ ，空间复杂度也是 $O(1)$ 。

总结

这题本质上是周期模拟题。

读懂“第几分钟落在一个周期的哪一段”之后，直接用取模定位位置，比逐分钟模拟更直接。

[COCI 2007/2008 #4] VAUVAU

目录

题意

思路

代码

复杂度

总结