开发者LT的博客
0%

洛谷P1328 - 生活大爆炸版石头剪刀布 - 题解

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟
暴力&枚举

洛谷P1328 - 生活大爆炸版石头剪刀布 - 题解

题目背景

NOIP2014 提高组 D1T1

题目描述

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

image-20260718145746278

现在，小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小 A 以 石头-布-石头-剪刀-蜥蜴人-斯波克 长度为 的周期出拳,那么他的出拳序列就是 石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-...，而如果小 B 以 剪刀-石头-布-斯波克-蜥蜴人 长度为 的周期出拳,那么他出拳的序列就是 剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-...。

已知小 A 和小 B 一共进行 次猜拳。每一次赢的人得 分，输的得 分；平局两人都得 分。现请你统计 次猜拳结束之后两人的得分。

输入格式

第一行包含三个整数：，分别表示共进行 次猜拳、小 A 出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含 个整数,表示小 A 出拳的规律,第三行包含 个整数，表示小 B 出拳的规律。其中， 表示 剪刀， 表示 石头， 表示 布， 表示 蜥蜴人， 表示 斯波克。数与数之间以一个空格分隔。

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小 A、小 B 的得分。

输入输出样例 #1

输入 #1

1
2
3
4
10 5 6
0 1 2 3 4
0 3 4 2 1 0

输出 #1

1
2
6 2

输入输出样例 #2

输入 #2

1
2
3
4
9 5 5
0 1 2 3 4
1 0 3 2 4

输出 #2

1
4 4

说明/提示

对于 ​ 的数据， ​ 。

解题思路

破解本题的关键是把提供的猜拳表格翻译成二维数组胜负表，通过取模运算在周期数组中定位每次的出拳，再利用胜负表快速判断结果

1. 存储出拳规律

题目输入的第二行和第三行分别给出了小A和小B的出拳规律，我们用两个数组来存储：

  • **数组 a[]**：存储小A的出拳周期，长度为 na
    • 例如：a[0] = 0 表示小A第一次出”剪刀”
    • a[1] = 1 表示小A第二次出”石头”
    • 以此类推，小A的出拳会按照这个数组循环
  • **数组 b[]**：存储小B的出拳周期，长度为 nb
    • 例如：b[0] = 0 表示小B第一次出”剪刀”
    • b[1] = 3 表示小B第二次出”蜥蜴人”
    • 以此类推，小B的出拳会按照这个数组循环

数组与周期序列的对应关系：

  • 小A第 i 次出拳：a[i % na]
    • 当 i = 0 时，0 % 6 = 0，出 a[0]
    • 当 i = 6 时，6 % 6 = 0，又出 a[0]，完成一个周期循环
  • 同理，小B第 i 次出拳：b[i % nb]

2. 胜负表的构建

题目给出了5种手势的胜负关系，我们用 5×5 的二维数组 来存储所有可能的结果：

  • score[甲][乙] = 1 表示甲赢
  • score[甲][乙] = 0 表示平局
  • score[甲][乙] = -1 表示甲输（乙赢）

数组下标对应关系：

  • 0 → 剪刀
  • 1 → 石头
  • 2 → 布
  • 3 → 蜥蜴人
  • 4 → 斯波克

胜负表解读（以第一行为例）：

text

1
2
3
4
5
6
{0, -1, 1, 1, -1}  // 甲出剪刀(0)时
// 乙出剪刀(0)：平局(0)
// 乙出石头(1)：甲输(-1)，因为石头胜剪刀
// 乙出布(2)：甲赢(1)，因为剪刀胜布
// 乙出蜥蜴人(3)：甲赢(1)，因为剪刀胜蜥蜴人（题目表格）
// 乙出斯波克(4)：甲输(-1)，因为斯波克胜剪刀（题目表格）

这样在判断胜负时，只需要查表即可，不需要写复杂的 if-else 判断（其实我第一次做想到的思路就是if-else，现在看确实有更好的做法）。

3. 得分统计

遍历 0 到 N-1 次猜拳：

  1. ia = i % na：计算小A本次出拳在数组 a[] 中的位置
  2. ib = i % nb：计算小B本次出拳在数组 b[] 中的位置
  3. a[ia] 和 b[ib] 就是双方本次的手势
  4. 查表 score[a[ia]][b[ib]] 得到结果
  5. 根据结果累加对应玩家的得分

代码实现

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
#include <iostream>
using namespace std;

int main() {
    int n, na, nb;
    cin >> n >> na >> nb;
    
    // a[]数组：存储小A的出拳规律
    // 例如：a = {0, 1, 2, 3, 4} 表示小A按 剪刀-石头-布-蜥蜴人-斯波克 循环
    int a[205], b[205];  // b[]数组：存储小B的出拳规律
    
    // 输入小A的出拳规律
    for (int i = 0; i < na; i++) cin >> a[i];
    
    // 输入小B的出拳规律
    for (int i = 0; i < nb; i++) cin >> b[i];
    
    // 胜负表：score[甲][乙]
    // 1表示甲赢，0表示平局，-1表示甲输
    int score[5][5] = {
        {0, -1, 1, 1, -1},  // 剪刀 vs 石头、布、蜥蜴人、斯波克
        {1, 0, -1, 1, -1},  // 石头 vs 剪刀、布、蜥蜴人、斯波克
        {-1, 1, 0, -1, 1},  // 布 vs 剪刀、石头、蜥蜴人、斯波克
        {-1, -1, 1, 0, 1},  // 蜥蜴人 vs 剪刀、石头、布、斯波克
        {1, 1, -1, -1, 0}   // 斯波克 vs 剪刀、石头、布、蜥蜴人
    };
    
    int sa = 0, sb = 0;  // 小A和小B的得分
    
    for (int i = 0; i < n; i++) {
        // ia和ib是本次出拳在各自周期数组中的索引
        int ia = i % na;  // 小A本次出拳：a[ia]
        int ib = i % nb;  // 小B本次出拳：b[ib]
        
        // 查表判断胜负：a[ia]表示小A的手势，b[ib]表示小B的手势
        int result = score[a[ia]][b[ib]];
        
        if (result == 1) {
            sa++;  // 小A赢
        } else if (result == -1) {
            sb++;  // 小B赢（因为甲是小A，乙是小B，-1表示甲输即乙赢）
        }
        // result == 0 时平局，双方都不得分
    }
    
    cout << sa << " " << sb << endl;
    return 0;
}

复杂度分析

  • 时间复杂度：O(N)，只需要遍历一次猜拳过程
  • 空间复杂度：O(NA + NB)，存储两个周期数组

注意事项

  1. 数组 a[] 和 b[] 存储的是出拳规律，不是出拳序列本身
  2. 通过 i % na 和 i % nb 的取模运算实现周期循环
  3. 胜负表中 score[a[ia]][b[ib]] 的查表方式，第一个下标是甲的出拳，第二个是乙的出拳
  4. 数组 score 初始化时每一行用 {} 括起来，避免负号引起的编译错误