魔法微灵的协作法则（K0043）- 华为可信认证科目一方向 · 可信 / BFS题解 | AlgoMooc

K0043. 魔法微灵的协作法则

困难

通过率 71% · 提交 31 · 通过 22

可信BFS系统设计哈希表

本题改编自华为可信认证科目一方向 · 考点：可信 / BFS · 难度：困难

在艾瑞利亚大陆上，存在着一种古老的魔法装置，称为。这些微灵可被唤醒并驻留于浮空魔塔（服务器）中，形成一套庞大的魔法协作网络。每一个魔法微灵都能释放某种魔力，但有些微灵的魔力释放于其它微灵的存在。魔法系统的运行规则如下： 1. 部署规则：每个魔法微灵只能在一座浮空魔塔中存在一个活跃的，但可以被唤醒于多座魔塔中。 2. 魔力提供规则： - 若一个魔法微灵没有依赖，只要任意一个分身被唤醒，则其魔力便可释放； - 若有依赖，只有当： - 它自身至少有一个分身处于运行状态； - 所有它依赖的微灵都已能成功释放魔力；才能释放魔力。举例说明：某时刻，微灵 A 依赖微灵 B，B 又依赖 C，而 C 没有依赖。 - 若 C 至少有一个运行中的分身，则 C 可释放魔力； - 若 B 至少有一个运行分身，则 B 可释放魔力； - 若 A 至少有一个运行分身，则 A 也可释放魔力；然而，如果 B 的所有分身都被熄灭（即），则 A 和 B 都无法释放魔力，但 C 仍可。你的任务是模拟这个魔法系统的运行过程。方法说明 - `ServiceWgSys()` 初始化魔法系统。假设所有魔塔已预加载所有魔法微灵的咒文。 - `bool startService(int serverId, const string& serviceName)` 在浮空魔塔 `serverId` 上唤醒微灵 `serviceName`。 - 若该微灵已在此塔运行，返回 `false`； - 否则将其唤醒并返回 `true`。 - `bool addDependency(const string& fromService, const string& toService)` 设定微灵 `fromService` 依赖 `toService`。 - 若该依赖已存在，返回 `false`； - 否则建立依赖关系，返回 `true`。 - `bool isServiceAvailable(const string& serviceName)` 查询微灵 `serviceName` 当前是否能释放魔力。 - 若能，返回 `true`；否则返回 `false`。 - `void rebootServers(const vector& serverIds)` 重启指定的浮空魔塔列表 `serverIds`。这些魔塔中的微灵将全部熄灭，需手动重新唤醒。

这类题属于华为可信认证科目一方向中「可信 / BFS」方向的高频题型，通常考察对「可信 / BFS」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

提示：带虚线的词点一下有通俗解释。

输入描述

第一行为一个整数 Q，表示命令的总条数。

接下来 Q 行，每行表示一次操作命令，格式如下：

初始化命令（只能出现一次，且必须为第 1 行）：
```
ServiceWgSys
```
启动微服务：
```
startService
```
添加微服务依赖：
```
addDependency
```
查询某个微服务是否可提供服务：
```
isServiceAvailable
```

批量重启服务器：

rebootServers
               // 表示接下来有 n 个 serverId
  ...   // 一行输入 n 个服务器编号，用空格分隔

参数约束

1 <= Q <= 1000
0 <= serverId <= 1000
所有服务器编号在 rebootServers 命令中互不相同
所有服务名由英文字母或数字组成，0 < len(serviceName) < 15

输出描述

第一行输出固定为：

null

之后的每一行对应每条命令的返回结果：

对于 ServiceWgSys() 和 rebootServers(...) 命令，输出：
```
null
```
对于 startService(...)、addDependency(...)、isServiceAvailable(...) 命令，输出：
```
True
```
或：
```
False
```

示例

示例 1

输入示例

13
ServiceWgSys
startService
1
serviceA
startService
2
serviceA
startService
2
serviceA
addDependency
serviceB
serviceA
rebootServers
1
2
isServiceAvailable
serviceA
startService
2
serviceB
isServiceAvailable
serviceB
rebootServers
2
2 1
isServiceAvailable
serviceA
startService
1
serviceA
isServiceAvailable
serviceA

输出示例

null
True
True
False
True
null
True
True
True
null
False
True
True

说明：

行数	命令	说明	输出
1	`ServiceWgSys`	初始化微服务系统	`null`
2	`startService 1 serviceA`	在服务器1启动 serviceA，成功启动	`True`
3	`startService 2 serviceA`	在服务器2也启动 serviceA，成功	`True`
4	`startService 2 serviceA`	再次尝试在服务器2启动同一个微服务，已存在，失败	`False`
5	`addDependency serviceB serviceA`	设置：serviceB 依赖 serviceA	`True`
6	`rebootServers [2]`	重启服务器2，停止其所有微服务实例	`null`
7	`isServiceAvailable serviceA`	serviceA 仍在服务器1运行，可提供服务	`True`
8	`startService 2 serviceB`	在服务器2启动 serviceB，成功	`True`
9	`isServiceAvailable serviceB`	serviceB 本身运行，且依赖的 serviceA 也可提供服务	`True`
10	`rebootServers [2, 1]`	重启服务器1和2，所有微服务实例停止	`null`
11	`isServiceAvailable serviceA`	所有 serviceA 实例停止，无法提供服务	`False`
12	`startService 1 serviceA`	在服务器1重新启动 serviceA，成功	`True`
13	`isServiceAvailable serviceA`	serviceA 再次运行，有实例，因此可用	`True`

时间限制 1000 ms · 内存限制 128 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List

# 定义魔法系统主类（模板）
class ServiceWgSys:
    def __init__(self):
        pass

    def startService(self, serverId: int, serviceName: str) -> bool:
        return False

    def addDependency(self, fromService: str, toService: str) -> bool:
        return False

    def isServiceAvailable(self, serviceName: str) -> bool:
        return False

    def rebootServers(self, serverIds: List[int]):
        pass


# 主函数入口
system = None  # 初始化魔法系统实例
Q = int(input())  # 输入命令总数
for i in range(Q):
    cmd = input().strip()  # 读取当前命令

    if i == 0 and cmd == "ServiceWgSys":
        system = ServiceWgSys()
        print("null")
    elif cmd == "startService":
        serverId = int(input())
        serviceName = input().strip()
        print(system.startService(serverId, serviceName))
    elif cmd == "addDependency":
        fromService = input().strip()
        toService = input().strip()
        print(system.addDependency(fromService, toService))
    elif cmd == "isServiceAvailable":
        serviceName = input().strip()
        print(system.isServiceAvailable(serviceName))
    elif cmd == "rebootServers":
        n = int(input())
        serverIds = list(map(int, input().split()))
        system.rebootServers(serverIds)
        print("null")
    else:
        raise ValueError(f"Unknown command: {cmd}")

from typing import List

# 定义魔法系统主类（模板）
class ServiceWgSys:
    def __init__(self):
        pass

def startService(self, serverId: int, serviceName: str) -> bool:
        return False

def addDependency(self, fromService: str, toService: str) -> bool:
        return False

def isServiceAvailable(self, serviceName: str) -> bool:
        return False

def rebootServers(self, serverIds: List[int]):
        pass

# 主函数入口
system = None  # 初始化魔法系统实例
Q = int(input())  # 输入命令总数
for i in range(Q):
    cmd = input().strip()  # 读取当前命令

if i == 0 and cmd == "ServiceWgSys":
        system = ServiceWgSys()
        print("null")
    elif cmd == "startService":
        serverId = int(input())
        serviceName = input().strip()
        print(system.startService(serverId, serviceName))
    elif cmd == "addDependency":
        fromService = input().strip()
        toService = input().strip()
        print(system.addDependency(fromService, toService))
    elif cmd == "isServiceAvailable":
        serviceName = input().strip()
        print(system.isServiceAvailable(serviceName))
    elif cmd == "rebootServers":
        n = int(input())
        serverIds = list(map(int, input().split()))
        system.rebootServers(serverIds)
        print("null")
    else:
        raise ValueError(f"Unknown command: {cmd}")

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交