题解 | #小红的兽#

题目链接

小红的兽

题目描述

在一个“人”与“兽”的游戏中，有 $n$ 个单位，每个单位有自己的身份和战斗力。游戏进行 $m$ 个回合，每个回合有两个单位遭遇。

遭遇时的规则如下：

单位可以选择向对方公开 ('Y') 或隐藏 ('N') 自己的身份。
战斗触发条件（至少一方决定攻击）：
- 一个兽，如果得知对方是人，会立即攻击。
- 一个人，如果得知对方是兽，且自己战斗力严格大于对方，会发起攻击。
- 如果双方得知对方与自己身份相同，则无事发生。
战斗结果：
- 战斗力高的一方获胜，另一方死亡。
- 战斗力相等，则同归于尽。
已死亡的单位无法参与后续的遭遇。

你需要模拟整个过程，并输出最终所有单位的存活情况。

解题思路

这是一个纯粹的模拟问题，核心在于根据题目给出的复杂规则，精确地更新每个单位的状态。

1. 数据结构

首先，我们需要一种方式来存储每个单位的信息。一个包含单位身份、战斗力和存活状态的类或结构体是理想的选择。然后，我们可以创建一个这些对象的数组来代表所有单位。

identity: "human" 或 "monster"
power: 整数
is_alive:布尔值，初始为 true

2. 模拟主循环

整个程序的核心是一个循环，从第 1 轮到第 $m$ 轮，模拟每一次遭遇。

3. 单次遭遇的逻辑

对于 u 和 v 之间的一场遭遇，我们按以下步骤判断：

存活检查：在任何逻辑开始之前，必须先检查 u 和 v 是否都还活着。如果任何一方已经死亡，则本轮遭遇不发生任何事情，直接进入下一轮。
决策判断：我们需要判断是否至少有一方会发起攻击。

我们定义一个布尔变量 fight_happens = false。
- 判断 u 是否攻击 v：
  - 条件1: v 向 u 公开了身份 (reveal_v == 'Y').
  - 条件2: u 和 v 身份不同。
  - 条件3:
    - 如果 u 是 monster，则满足上述条件即可攻击。
    - 如果 u 是 human，还需满足 power[u] > power[v]。
  - 如果以上所有条件满足，则 fight_happens = true。
- 判断 v 是否攻击 u：
  - 逻辑与 u 攻击 v 完全对称。如果满足条件，同样设置 fight_happens = true。
战斗结算：
- 如果 fight_happens 经过判断后为 true，则进行战斗结算。
- 比较 power[u] 和 power[v] 的大小：
  - power[u] > power[v] -> v.is_alive = false
  - power[v] > power[u] -> u.is_alive = false
  - power[u] == power[v] -> u.is_alive = false, v.is_alive = false

4. 输出结果

在 $m$ 轮模拟全部结束后，遍历单位数组，根据每个单位的 is_alive 状态，构建并输出最终的 'Y'/'N' 字符串。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Unit {
    string identity;
    int power;
    bool is_alive;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<Unit> units(n);
    for (int i = 0; i < n; ++i) {
        cin >> units[i].identity >> units[i].power;
        units[i].is_alive = true;
    }

    for (int k = 0; k < m; ++k) {
        int u_idx, v_idx;
        char reveal_u, reveal_v;
        cin >> u_idx >> v_idx >> reveal_u >> reveal_v;
        u_idx--; 
        v_idx--; 

        if (!units[u_idx].is_alive || !units[v_idx].is_alive) {
            continue;
        }

        bool fight_happens = false;

        // Check if u attacks v
        if (reveal_v == 'Y' && units[u_idx].identity != units[v_idx].identity) {
            if (units[u_idx].identity == "monster" || 
               (units[u_idx].identity == "human" && units[u_idx].power > units[v_idx].power)) {
                fight_happens = true;
            }
        }

        // Check if v attacks u
        if (reveal_u == 'Y' && units[u_idx].identity != units[v_idx].identity) {
            if (units[v_idx].identity == "monster" || 
               (units[v_idx].identity == "human" && units[v_idx].power > units[u_idx].power)) {
                fight_happens = true;
            }
        }
        
        if (fight_happens) {
            if (units[u_idx].power > units[v_idx].power) {
                units[v_idx].is_alive = false;
            } else if (units[v_idx].power > units[u_idx].power) {
                units[u_idx].is_alive = false;
            } else { // Equal power
                units[u_idx].is_alive = false;
                units[v_idx].is_alive = false;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << (units[i].is_alive ? 'Y' : 'N');
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;

class Unit {
    String identity;
    int power;
    boolean isAlive;

    public Unit(String identity, int power) {
        this.identity = identity;
        this.power = power;
        this.isAlive = true;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Unit[] units = new Unit[n];
        for (int i = 0; i < n; i++) {
            units[i] = new Unit(sc.next(), sc.nextInt());
        }

        for (int k = 0; k < m; k++) {
            int uIdx = sc.nextInt() - 1;
            int vIdx = sc.nextInt() - 1;
            char revealU = sc.next().charAt(0);
            char revealV = sc.next().charAt(0);

            if (!units[uIdx].isAlive || !units[vIdx].isAlive) {
                continue;
            }

            boolean fightHappens = false;

            // Check if u attacks v
            if (revealV == 'Y' && !units[uIdx].identity.equals(units[vIdx].identity)) {
                if (units[uIdx].identity.equals("monster") ||
                   (units[u_idx].identity.equals("human") && units[uIdx].power > units[vIdx].power)) {
                    fightHappens = true;
                }
            }

            // Check if v attacks u
            if (revealU == 'Y' && !units[uIdx].identity.equals(units[vIdx].identity)) {
                if (units[vIdx].identity.equals("monster") ||
                   (units[vIdx].identity.equals("human") && units[vIdx].power > units[uIdx].power)) {
                    fightHappens = true;
                }
            }
            
            if (fightHappens) {
                if (units[uIdx].power > units[vIdx].power) {
                    units[vIdx].isAlive = false;
                } else if (units[vIdx].power > units[uIdx].power) {
                    units[uIdx].isAlive = false;
                } else { // Equal power
                    units[uIdx].isAlive = false;
                    units[vIdx].isAlive = false;
                }
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            result.append(units[i].isAlive ? 'Y' : 'N');
        }
        System.out.println(result.toString());
    }
}

import sys

def solve():
    try:
        n, m = map(int, sys.stdin.readline().split())
        units = []
        for _ in range(n):
            identity, power_str = sys.stdin.readline().split()
            # [identity, power, is_alive]
            units.append([identity, int(power_str), True])

        for _ in range(m):
            u_idx, v_idx, reveal_u, reveal_v = sys.stdin.readline().split()
            u_idx, v_idx = int(u_idx) - 1, int(v_idx) - 1

            if not units[u_idx][2] or not units[v_idx][2]:
                continue

            fight_happens = False

            # Check if u attacks v
            if reveal_v == 'Y' and units[u_idx][0] != units[v_idx][0]:
                if units[u_idx][0] == "monster" or \
                   (units[u_idx][0] == "human" and units[u_idx][1] > units[v_idx][1]):
                    fight_happens = True
            
            # Check if v attacks u
            if reveal_u == 'Y' and units[u_idx][0] != units[v_idx][0]:
                if units[v_idx][0] == "monster" or \
                   (units[v_idx][0] == "human" and units[v_idx][1] > units[u_idx][1]):
                    fight_happens = True

            if fight_happens:
                if units[u_idx][1] > units[v_idx][1]:
                    units[v_idx][2] = False
                elif units[v_idx][1] > units[u_idx][1]:
                    units[u_idx][2] = False
                else: # Equal power
                    units[u_idx][2] = False
                    units[v_idx][2] = False

    except (IOError, ValueError):
        return
    
    result = "".join(['Y' if unit[2] else 'N' for unit in units])
    print(result)

solve()

算法及复杂度

算法：模拟
时间复杂度： $O(N + M)$ 。
- 读取 $N$ 个单位的初始信息需要 $O(N)$ 的时间。
- 模拟 $M$ 轮遭遇，每一轮的操作（几次比较和赋值）都是常数时间 $O(1)$ 的，所以总模拟时间为 $O(M)$ 。
空间复杂度： $O(N)$ 。
- 需要 $O(N)$ 的空间来存储 $N$ 个单位的身份、战斗力和存活状态信息。