题解 | #纸牌游戏#

题目链接

题目描述

Alex 与 Bob 进行纸牌游戏。Alex 有两张牌 $a_1, a_2$ ，Bob 有两张牌 $b_1, b_2$ 。游戏分两回合，每回合双方随机翻开一张未翻开的牌比大小。牌面大者赢下该回合，相等则平局。两回合后，赢得回合数更多的一方获胜。若双方赢得回合数相同，则游戏平局。

已知四张牌的具体数字，求 Alex 最终获胜的不同翻牌顺序有多少种。

解题思路

本题要求我们计算在所有可能的翻牌顺序中，Alex 获胜的次数。

首先，我们分析“翻牌顺序”的构成。

设 Alex 的牌为 $\{A_1, A_2\}$ ，Bob 的牌为 $\{B_1, B_2\}$ 。
第一回合，Alex 可以出 $A_1$ 或 $A_2$ （2种选择），Bob 可以出 $B_1$ 或 $B_2$ （2种选择）。
第一回合的牌一旦确定，第二回合的牌也就随之确定了。
因此，总共有 $2 \times 2 = 4$ 种不同的翻牌顺序。

这 4 种顺序可以归结为两种基本的牌局配对：

配对一：Alex 的 $A_1$ 对阵 Bob 的 $B_1$ ，同时 $A_2$ 对阵 $B_2$ 。
- 这对应了两种翻牌顺序：
  - 第一回合 $A_1$ vs $B_1$ ，第二回合 $A_2$ vs $B_2$ 。
  - 第一回合 $A_2$ vs $B_2$ ，第二回合 $A_1$ vs $B_1$ 。
- 这两种顺序的回合胜负情况完全相同，因此游戏最终结果也相同。
配对二：Alex 的 $A_1$ 对阵 Bob 的 $B_2$ ，同时 $A_2$ 对阵 $B_1$ 。
- 这同样对应了两种翻牌顺序。
- 这两种顺序的游戏最终结果也相同。

因此，我们的解题策略可以简化为：

分别计算上述两种配对下的游戏结果。
如果一种配对能让 Alex 获胜（即 Alex 在该配对的两场比赛中赢得的回合数多于 Bob），那么就给最终的获胜顺序计数器加上 2。
将两种配对的结果相加，就是最终答案。

为了方便处理，我们可以先将 Alex 和 Bob 的手牌进行排序，例如 Alex 的牌为 $\{A_{min}, A_{max}\}$ ，Bob 的牌为 $\{B_{min}, B_{max}\}$ 。然后分析以下两种配对：

配对一：( $A_{min}$ vs $B_{min}$ ) 和 ( $A_{max}$ vs $B_{max}$ )
配对二：( $A_{min}$ vs $B_{max}$ ) 和 ( $A_{max}$ vs $B_{min}$ )

对每个配对，计算 Alex 的胜场数是否大于 Bob 的胜场数即可。

代码

cpp
java
python

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int get_alex_wins(int a1, int a2, int b1, int b2) {
    int alex_score = 0;
    int bob_score = 0;
    if (a1 > b1) alex_score++;
    if (b1 > a1) bob_score++;
    if (a2 > b2) alex_score++;
    if (b2 > a2) bob_score++;
    return alex_score > bob_score ? 2 : 0;
}

void solve() {
    int a1, a2, b1, b2;
    cin >> a1 >> a2 >> b1 >> b2;
    
    int total_wins = 0;
    
    // 配对一: a1 vs b1, a2 vs b2
    total_wins += get_alex_wins(a1, a2, b1, b2);
    
    // 配对二: a1 vs b2, a2 vs b1
    total_wins += get_alex_wins(a1, a2, b2, b1);

    cout << total_wins << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {

    private static int getAlexWins(int a1, int a2, int b1, int b2) {
        int alexScore = 0;
        int bobScore = 0;
        if (a1 > b1) alexScore++;
        if (b1 > a1) bobScore++;
        if (a2 > b2) alexScore++;
        if (b2 > a2) bobScore++;
        
        return alexScore > bobScore ? 2 : 0;
    }

    public static void solve(Scanner sc) {
        int a1 = sc.nextInt();
        int a2 = sc.nextInt();
        int b1 = sc.nextInt();
        int b2 = sc.nextInt();

        int totalWins = 0;

        // 配对一: a1 vs b1, a2 vs b2
        totalWins += getAlexWins(a1, a2, b1, b2);
        
        // 配对二: a1 vs b2, a2 vs b1
        totalWins += getAlexWins(a1, a2, b2, b1);
        
        System.out.println(totalWins);
    }

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

def get_alex_wins(a1, a2, b1, b2):
    alex_score = 0
    bob_score = 0
    if a1 > b1:
        alex_score += 1
    elif b1 > a1:
        bob_score += 1
    
    if a2 > b2:
        alex_score += 1
    elif b2 > a2:
        bob_score += 1
        
    return 2 if alex_score > bob_score else 0

def solve():
    a1, a2, b1, b2 = map(int, input().split())
    
    total_wins = 0
    
    # 配对一: a1 vs b1, a2 vs b2
    total_wins += get_alex_wins(a1, a2, b1, b2)
    
    # 配对二: a1 vs b2, a2 vs b1
    total_wins += get_alex_wins(a1, a2, b2, b1)
    
    print(total_wins)

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

算法及复杂度

算法：模拟 / 枚举
时间复杂度：对于每个测试用例，我们只进行常数次比较。因此，时间复杂度是 $\mathcal{O}(1)$ 。
空间复杂度： $\mathcal{O}(1)$ ，只需要存储几个变量。