石头剪刀布

题意

两人按各自周期出石头、剪刀、布，比赛 $N$ 轮后比较谁获胜轮数更多。

思路

第 $i$ 轮的出拳下标分别为 i % a_length 和 i % b_length。字典 wins_against 记录每种拳能战胜的拳，比较映射结果即可计数。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15round_count, a_length, b_length = map(int, input().split())
a_pattern = list(map(int, input().split()))
b_pattern = list(map(int, input().split()))

# 每种拳能战胜的拳：石头 0 胜剪刀 2，剪刀 2 胜布 5，布 5 胜石头 0。
wins_against = {0: 2, 2: 5, 5: 0}
a_wins = sum(wins_against[a_pattern[i % a_length]] == b_pattern[i % b_length] for i in range(round_count))
b_wins = sum(wins_against[b_pattern[i % b_length]] == a_pattern[i % a_length] for i in range(round_count))

if a_wins > b_wins:
    print("A")
elif a_wins < b_wins:
    print("B")
else:
    print("draw")

C++代码

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#include <cstdio>

int n,na,nb;
int a[105],b[105];

int main(){
    scanf("%d%d%d",&n,&na,&nb);
    int i,j;
    for (i=1;i<=na;i++){
        scanf("%d",&a[i]);
    }

    int idx = 1;
    for(i=na+1;i<=n;i++){
        a[i] = a[idx];
        idx++;
    }
    for (i=1;i<=nb;i++){
        scanf("%d",&b[i]);
    }

    idx = 1;
    for(i=nb+1;i<=n;i++){
        b[i] = b[idx];
        idx++;
    }
    int win_a = 0,win_b =0;
    for(i=1;i<=n;i++){
        if( (a[i] == 0 && b[i] == 2) || (a[i] == 2 && b[i] == 5) || (a[i] == 5 && b[i] == 0 ))
            win_a++;
        else if( (b[i] == 0 && a[i] == 2) || (b[i] == 2 && a[i] == 5) || (b[i] == 5 && a[i] == 0 ))
            win_b++;
    }
    if( win_a == win_b)
        printf("draw");
    else if( win_a > win_b)
        printf("A");
    else 
        printf("B");
    return 0;
}

复杂度

时间复杂度为 $O(N)$ ，除两个周期外额外空间复杂度为 $O(1)$ 。

总结

周期性序列访问的核心是下标对周期长度取模。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结