BGN15 纸牌游戏

思路

拿到这题你先想一个问题：Alex 和 Bob 各有两张牌，每人每回合翻一张，总共两回合，翻牌顺序随机——那一共有多少种不同的翻牌方式？

Alex 选先翻哪张有 2 种选法，Bob 也有 2 种，所以总共 种翻牌顺序。

但你再仔细想想，这 4 种顺序的本质是什么？其实就是两张牌怎么"配对"的问题：

  • 配对方式 A：Alex 第一张 vs Bob 第一张，Alex 第二张 vs Bob 第二张
  • 配对方式 B：Alex 第一张 vs Bob 第二张，Alex 第二张 vs Bob 第一张

不管谁先翻谁后翻，最终的对战配对只有这两种。而每种配对方式对应 2 种翻牌顺序（先翻哪张的区别），所以每种配对如果 Alex 赢了，就贡献 2 次胜利。

每种配对怎么判胜负？

两回合分别比大小，赢的回合多的人获胜。也就是说：

  1. 数 Alex 赢了几个回合、Bob 赢了几个回合
  2. Alex 赢的回合数 > Bob 赢的回合数 → Alex 获胜

就这么简单，纯模拟枚举两种配对就行了。

代码

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int a1, a2, b1, b2;
        cin >> a1 >> a2 >> b1 >> b2;
        int ans = 0;
        // 配对1: a1 vs b1, a2 vs b2
        {
            int aw = 0, bw = 0;
            if (a1 > b1) aw++; else if (a1 < b1) bw++;
            if (a2 > b2) aw++; else if (a2 < b2) bw++;
            if (aw > bw) ans += 2; // 该配对对应2种翻牌顺序
        }
        // 配对2: a1 vs b2, a2 vs b1
        {
            int aw = 0, bw = 0;
            if (a1 > b2) aw++; else if (a1 < b2) bw++;
            if (a2 > b1) aw++; else if (a2 < b1) bw++;
            if (aw > bw) ans += 2;
        }
        cout << ans << "\n";
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int a1 = sc.nextInt(), a2 = sc.nextInt();
            int b1 = sc.nextInt(), b2 = sc.nextInt();
            int ans = 0;
            // 配对1: a1 vs b1, a2 vs b2
            {
                int aw = 0, bw = 0;
                if (a1 > b1) aw++; else if (a1 < b1) bw++;
                if (a2 > b2) aw++; else if (a2 < b2) bw++;
                if (aw > bw) ans += 2;
            }
            // 配对2: a1 vs b2, a2 vs b1
            {
                int aw = 0, bw = 0;
                if (a1 > b2) aw++; else if (a1 < b2) bw++;
                if (a2 > b1) aw++; else if (a2 < b1) bw++;
                if (aw > bw) ans += 2;
            }
            sb.append(ans).append("\n");
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
out = []
for _ in range(t):
    a1, a2, b1, b2 = map(int, input().split())
    ans = 0
    # 配对1: a1 vs b1, a2 vs b2
    aw = bw = 0
    if a1 > b1: aw += 1
    elif a1 < b1: bw += 1
    if a2 > b2: aw += 1
    elif a2 < b2: bw += 1
    if aw > bw: ans += 2
    # 配对2: a1 vs b2, a2 vs b1
    aw = bw = 0
    if a1 > b2: aw += 1
    elif a1 < b2: bw += 1
    if a2 > b1: aw += 1
    elif a2 < b1: bw += 1
    if aw > bw: ans += 2
    out.append(str(ans))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const res = [];
    for (let i = 0; i < t; i++) {
        const [a1, a2, b1, b2] = lines[idx++].split(/\s+/).map(Number);
        let ans = 0;
        // 配对1
        let aw = 0, bw = 0;
        if (a1 > b1) aw++; else if (a1 < b1) bw++;
        if (a2 > b2) aw++; else if (a2 < b2) bw++;
        if (aw > bw) ans += 2;
        // 配对2
        aw = 0; bw = 0;
        if (a1 > b2) aw++; else if (a1 < b2) bw++;
        if (a2 > b1) aw++; else if (a2 < b1) bw++;
        if (aw > bw) ans += 2;
        res.push(ans);
    }
    console.log(res.join('\n'));
});

复杂度

  • 时间复杂度：，每个测试用例只需常数次比较。
  • 空间复杂度：。

总结

这题看着像博弈论，其实就是个枚举题。关键在于想清楚 4 种翻牌顺序本质上只有 2 种配对方式，每种配对各对应 2 种顺序。把两种配对分别模拟一下比大小，Alex 赢了就加 2，完事儿。