🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 华为秋招笔试，来啦！！！

🍥 华为这次笔试的难度对于没打过竞赛的选手来说偏大，其中第三题是HDU的一道原题

1️⃣ python选手狂喜，其他语言的选手需要自己写判断的逻辑

2️⃣ 二分+BFS，属于比较经典的题了，建议大家好好掌握

3️⃣ 01分组背包的变种，加了一个每组至少选一个的限制，也非常经典

🛜 01.K小姐的网络监控 评测链接🔗

问题描述

在一个网络监控系统中，K小姐负责定期检查网络的健康状态。每当重要节日来临，K小姐需要对网络中的各个设备进行数据采集，并根据预设的判断条件来判断网络是否健康。判断条件以布尔表达式的形式给出，包含不同的字段名和对应的数据值。若采集到的数据符合条件，则认为网络健康；否则，网络处于不健康状态。

输入格式

第一行包含两个整数 和 ，分别表示判断条件的数量和数据采集的数量。
接下来的 行字符串表示布尔表达式，即判断条件。
接下来的 行，每行包含两个字符串，分别是字段名 和对应的数据值 。

输出格式

对于每个判断条件，输出一个整数： 表示网络健康， 表示网络不健康。

样例输入

2 2
error = '0' AND (name = 'NE40' OR name = 'NE20')
error = '1' AND (name = 'NE40' OR name = 'NE20')
name NE40
error 0

样例输出

0
1

样例解释

1. 对于第一个条件 error = '0' AND (name = 'NE40' OR name = 'NE20')：

   • 当 name 的值为 NE40，而 error 的值为 0 时，该表达式计算结果为 true。
   • 因此输出 0，表示网络健康。

2. 对于第二个条件 error = '1' AND (name = 'NE40' OR name = 'NE20')：

   • 当 name 的值为 NE40，而 error 的值为 0 时，该表达式计算结果为 false。
   • 因此输出 1，表示网络不健康。

样例输入

3 2
error = '1' AND (name = 'NE40' OR name = 'NE20')
error = '2' AND (name = 'NE40' OR name = 'NE20')
error = '3' AND (name = 'NE40' OR name = 'NE20')
name NE40
error 3

样例输出

1
1
0

样例解释

1. 对于第一个条件 error = '1' AND (name = 'NE40' OR name ='NE20')：

   • 当 name 的值为 NE40，而 error 的值为 3 时，该表达式计算结果为 false。
   • 因此输出 1，表示网络不健康。

2. 对于第二个条件 error = '2' AND (name = 'NE40' OR name ='NE20')：

   • 当 name 的值为 NE40，而 error 的值为 3 时，该表达式计算结果为 false。
   • 因此输出 1，表示网络不健康。

3. 对于第三个条件 error = '3' AND (name='NE40' OR name='NE20')：

   • 当 name 的值为 NE40，而 error 的值为 3 时，该表达式计算结果为 true。
   • 因此输出 0，表示网络健康。

数据范围

题解

解法：Python

可以使用 Python 的 eval() 函数来动态地计算这些布尔表达式。在执行之前，需要对输入的表达式进行一些简单的替换，以确保能被 Python 正确解析。 将 AND 替换为 and，将 OR 替换为 or，并将 = 替换为 ==。

参考代码

• Python

# 导入必要模块
import sys

# 读取输入数据
n, m = map(int, input().split())

# 存储判断条件
conditions = []
for _ in range(n):
    conditions.append(input().strip())

# 存储采集到的数据
data_dict = {}
for _ in range(m):
    key, value = input().split()
    data_dict[key] = value

# 检查每个条件并输出结果
for condition in conditions:
    # 替换为 Python 可识别的格式
    condition = condition.replace('AND', 'and').replace('OR', 'or').replace('=', '==')
    
    # 使用 eval() 计算布尔表达式
    if eval(condition, {}, data_dict):
        print(0)  # 健康状态
    else:
        print(1)  # 不健康状态

🧩 02.迷宫中的配送员 评测链接🔗

问题描述

在一个神秘的迷宫中，配送员K小姐需要从左上角的位置（0, 0）出发，前往右下角的位置（N-1, N-1）。这个迷宫是一个 的方格，每个格子都有一个辐射值，配送员必须穿着防护能力不低于该辐射值的防护服才能通过。配送员可以上下左右移动，每次移动耗时 单位。K小姐希望在最多 单位时间内到达目标位置，同时她的防护服需要满足起点和终点的辐射值要求。请问，K小姐的防护服最低需要达到多少防护能力，才能顺利完成任务？

输入格式

第一行包含两个正整数 和 。

接下来有 行，每行包含 个以空格分隔的整数，表示迷宫中每个位置的辐射值。

输出格式

输出一个整数，表示配送员穿着防护服的最低防护能力。

样例输入1

2 2
1 3
2 1

样例输出2

2

样例输入2

5 12
0 0 0 0 0
9 9 3 9 0
0 0 0 0 0
0 9 5 9 9
0 0 0 0 0

样例输出2

3

数据范围

，，以保证题目有解。所有辐射值都是非负整数，绝对值不超过 。

题解

二分+BFS

步骤

1. 二分查找：可以对可能的防护能力进行二分查找。防护能力的范围从起点和终点的辐射值的最大值开始，一直到最大可能的辐射值（）。

2. BFS：对于每一个假设的防护能力，用BFS来判断是否能够在不超过 单位时间内从起点到达终点。BFS能够有效地探索所有可能的路径，并记录每个位置到达时所需的时间。

3. 判断条件：如果在某个假设的防护能力下，K小姐能够在规定时间内到达终点，则说明可以尝试更小的防护能力；否则，就需要增加防护能力。

时间复杂度分析

• 二分查找的复杂度为 。
• 每次BFS遍历整个迷宫，其复杂度为 。
• 因此，总体复杂度为 ，对于最大输入规模是可接受的。

参考代码

• Python

from collections import deque

# 定义全局变量N和K，表示迷宫大小和最大时间限制
N, K = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(N)] # 输入迷宫数据

# BFS函数，用于判断能否在给定保护能力下到达终点
def bfs(protection):
    visited = [[False] * N for _ in range(N)] # 初始化访问标记数组
    q = deque([(0, 0)]) # 初始化队列，从起点开始搜索
    visited[0][0] = True # 标记起点为已访问
    
    dist = [[-1] * N for _ in range(N)] # 初始化距离数组，用于记录到达时间
    dist[0][0] = 0 # 起点时间为零
    
    while q:
        x, y = q.popleft() # 从队列中取出当前坐标
        
        if dist[x][y] > K: # 如果当前距离超过最大时间限制，返回False
            return False
        
        if x == N - 1 and y == N - 1: # 如果到达终点，返回True
            return True
        
        # 尝试向四个方向移动
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy # 新坐标
            
            # 检查新坐标是否有效并且未被访问且辐射值符合保护要求
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and maze[nx][ny] <= protection:
                visited[nx][ny] = True # 标记新坐标为已访问
                dist[nx][ny] = dist[x][y] + 1 # 更新新坐标的到达时间
                
                q.append((nx, ny)) # 将新坐标加入队列
                
    return False # 无法到达终点返回False

# 主解法函数，通过二分查找找到最小保护能力 
def solve():
    left = max(maze[0][0], maze[N - 1][N - 1]) # 从起始和结束位置的辐射值开始 
    right = 10000 # 最大可能辐射值
    
    while left < right: 
        mid = (left + right) // 2 # 中间值
        
        if bfs(mid): # 如果能到达终点，则尝试更小保护能力 
            right = mid 
        else: # 否则增加保护能力 
            left = mid + 1
            
    return left # 返回最小保护能力 

print(solve()) # 输出结果 

• Java

import java.util.*;

public class Main{
    
    static int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 定义四个方向移动
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt(); // 输入迷宫大小N 
        int K = sc.nextInt(); // 输入最大时间K
        
        int[][] maze = new int[N][N]; // 初始化迷宫矩阵
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                maze[i][j] = sc.nextInt(); // 输入每个格子的辐射值 
            }
        }
        
        System.out.println(solve(maze, K)); // 输出结果 
    }

    static boolean bfs(int[][] maze, int protection, int K) {
        boolean[][] visited = new boolean[maze.length][maze.length]; // 初始化访问数组 
        Queue<int[]> queue = new LinkedList<>(); 
        queue.offer(new int[]{0, 0}); // 从起点开始搜索 
        visited[0][0] = true;