题解 | #纸牌游戏#

题目链接

BGN15 纸牌游戏

题目描述

Alex 与 Bob 进行纸牌游戏。Alex 拥有牌 $c_1, c_2$ ，Bob 拥有牌 $c_3, c_4$ 。游戏共两回合，每回合双方各随机翻开一张未翻开的牌并比较大小。

牌面数字更大者赢得该回合。
若相等则该回合无人获胜。

两回合结束后，赢得回合数更多者获胜。若回合数相同则为平局。已知四张牌的具体数字，请计算 Alex 最终获胜的不同翻牌顺序数量。

输入描述

第一行输入整数 $T$ ，表示测试用例数量。每个测试用例一行输入四个整数 $c_1, c_2, c_3, c_4$ 。

输出描述

对每个测试用例输出一行一个整数，表示 Alex 获胜的翻牌顺序数量。

样例

输入

输出

解题思路

本题要求计算 Alex 获胜的“不同翻牌顺序”的数量。一个完整的“翻牌顺序”由两回合的牌面对决构成，而这完全取决于双方在第一回合各自选择出哪张牌。

Alex 在第一回合有两种选择：出 $c_1$ 或 $c_2$ 。
Bob 在第一回合也有两种选择：出 $c_3$ 或 $c_4$ 。

因此，第一回合的对局情况共有 $2 \cdot 2 = 4$ 种。一旦第一回合的牌确定，第二回合的对局（双方剩下的牌）也随之确定。所以，总共只有4种独一无二的“翻牌顺序”。

我们可以通过暴力枚举的方式，模拟这4种场景，判断每种场景下 Alex 是否获胜。

设 Alex 的牌为 $\{c_1, c_2\}$ ，Bob 的牌为 $\{c_3, c_4\}$ 。

4种翻牌顺序如下：

第一回合： $c_1$ vs $c_3$ ，第二回合： $c_2$ vs $c_4$
第一回合： $c_1$ vs $c_4$ ，第二回合： $c_2$ vs $c_3$
第一回合： $c_2$ vs $c_3$ ，第二回合： $c_1$ vs $c_4$
第一回合： $c_2$ vs $c_4$ ，第二回合： $c_1$ vs $c_3$

算法步骤：

对于每组测试数据，读入 $c_1, c_2, c_3, c_4$ 。
初始化 Alex 的获胜场景计数器 $win\_count = 0$ 。
对上述4种场景，逐一进行模拟：
- 在每个场景中，分别计算 Alex 和 Bob 在两回合中赢得的回合数。
- 例如，在场景1中，比较 $c_1$ 和 $c_3$ ，再比较 $c_2$ 和 $c_4$ 。
- 如果 Alex 赢得的回合总数大于 Bob，则将 $win\_count$ 加1。
模拟完4种场景后，输出 $win\_count$ 的值。

这种方法直接明了，且因为场景数恒定为4，所以效率非常高。

代码

c++
java
python

#include <iostream>

using namespace std;

// 模拟一局游戏，返回Alex是否获胜
bool doesAlexWin(int a1, int b1, int a2, int b2) {
    int alex_wins = 0;
    int bob_wins = 0;
    if (a1 > b1) alex_wins++;
    if (b1 > a1) bob_wins++;
    if (a2 > b2) alex_wins++;
    if (b2 > a2) bob_wins++;
    return alex_wins > bob_wins;
}

void solve() {
    int c1, c2, c3, c4;
    cin >> c1 >> c2 >> c3 >> c4;

    int win_count = 0;

    // 场景1: c1 vs c3, c2 vs c4
    if (doesAlexWin(c1, c3, c2, c4)) {
        win_count++;
    }
    // 场景2: c1 vs c4, c2 vs c3
    if (doesAlexWin(c1, c4, c2, c3)) {
        win_count++;
    }
    // 场景3: c2 vs c3, c1 vs c4
    if (doesAlexWin(c2, c3, c1, c4)) {
        win_count++;
    }
    // 场景4: c2 vs c4, c1 vs c3
    if (doesAlexWin(c2, c4, c1, c3)) {
        win_count++;
    }

    cout << win_count << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 模拟一局游戏，返回Alex是否获胜
    private static boolean doesAlexWin(int a1, int b1, int a2, int b2) {
        int alex_wins = 0;
        int bob_wins = 0;
        if (a1 > b1) alex_wins++;
        if (b1 > a1) bob_wins++;
        if (a2 > b2) alex_wins++;
        if (b2 > a2) bob_wins++;
        return alex_wins > bob_wins;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int c1 = sc.nextInt();
            int c2 = sc.nextInt();
            int c3 = sc.nextInt();
            int c4 = sc.nextInt();

            int win_count = 0;

            // 场景1: c1 vs c3, c2 vs c4
            if (doesAlexWin(c1, c3, c2, c4)) {
                win_count++;
            }
            // 场景2: c1 vs c4, c2 vs c3
            if (doesAlexWin(c1, c4, c2, c3)) {
                win_count++;
            }
            // 场景3: c2 vs c3, c1 vs c4
            if (doesAlexWin(c2, c3, c1, c4)) {
                win_count++;
            }
            // 场景4: c2 vs c4, c1 vs c3
            if (doesAlexWin(c2, c4, c1, c3)) {
                win_count++;
            }
            System.out.println(win_count);
        }
    }
}

# -*- coding: utf-8 -*-

def does_alex_win(a1, b1, a2, b2):
    # 模拟一局游戏，返回Alex是否获胜
    alex_wins = 0
    bob_wins = 0
    if a1 > b1:
        alex_wins += 1
    elif b1 > a1:
        bob_wins += 1
    
    if a2 > b2:
        alex_wins += 1
    elif b2 > a2:
        bob_wins += 1
        
    return alex_wins > bob_wins

def solve():
    c1, c2, c3, c4 = map(int, input().split())
    
    win_count = 0
    
    # 场景1: c1 vs c3, c2 vs c4
    if does_alex_win(c1, c3, c2, c4):
        win_count += 1
    # 场景2: c1 vs c4, c2 vs c3
    if does_alex_win(c1, c4, c2, c3):
        win_count += 1
    # 场景3: c2 vs c3, c1 vs c4
    if does_alex_win(c2, c3, c1, c4):
        win_count += 1
    # 场景4: c2 vs c4, c1 vs c3
    if does_alex_win(c2, c4, c1, c3):
        win_count += 1
        
    print(win_count)

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：模拟、暴力枚举
时间复杂度：对于每组测试数据，我们固定模拟4种场景，每个场景进行常数次比较。因此，单次查询的时间复杂度为 $O(1)$ 。如果总共有 $T$ 组数据，则总时间复杂度为 $O(T)$ 。
空间复杂度：我们只使用了少数变量来存储牌面和计数值，因此空间复杂度为 $O(1)$ 。