✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

小米-2026.03.14

这套题整体不偏，都是典型的“题面平和，但切入点必须找准”的中等题。第一题考的是连通块预处理和四方向去重，第二题则是标准的邻项交换贪心，能不能把排序准则推出来就是分水岭。

题目一：蓄水区扩建方案

表面上像是对每个位置都做一次改造模拟，实际上真正该做的是先把所有已有蓄水块统一编号。难点不在 BFS 本身，而在于枚举四个方向时要记得去重，否则同一连通块会被重复累加。

难度：中等

题目二：单窗业务排程

这题最关键的是别被“总时间最小”吓住，核心只是一条邻项交换结论。把两个人的相对顺序比较清楚以后，排序规则自然就出来了；后面的递推式只是顺着题意把总耗时滚动更新。

难度：中等

01. 蓄水区扩建方案

问题描述

小基 正在整理一块实验用地的蓄水布局。整块区域被划分成一个 的网格，每个格子只有两种状态：

• x 表示硬化地面，当前不能蓄水。
• o 表示蓄水单元，水可以在相邻蓄水单元之间流动。

如果两个蓄水单元可以通过上下左右移动互相到达，就认为它们属于同一个连通蓄水区。

现在允许进行一次改造。对于每个格子：

• 如果该格子原本就是 o，输出 0。
• 如果该格子原本是 x，假设把它改造成 o，需要输出改造后包含该格子的连通蓄水区大小。

请按网格形式输出每个位置对应的结果。

输入格式

第一行输入两个正整数 和 ，表示网格的行数和列数。

接下来输入 行，每行是一个长度为 的字符串，只包含 x 和 o，表示初始布局。

输出格式

输出 行，每行输出 个整数。

• 对于原本是 o 的格子，输出 0。
• 对于原本是 x 的格子，输出把它改造成 o 后，包含该格子的连通蓄水区大小。

相邻数字之间用一个空格分隔。

样例输入 1

3 3
xoo
oxo
xox

样例输出 1

5 0 0
0 6 0
3 0 5

样例说明 1

左上角位置原本是 x。如果把它改造成 o，它会和右边、下边已经连通的蓄水单元连在一起，形成大小为 的连通蓄水区。

中间位置也是 x。如果把它改造成 o，周围四个方向的蓄水单元都会被连起来，因此答案是 。

样例输入 2

6 5
ooooo
oxxoo
xxxox
oxxoo
xooxx
ooooo

样例输出 2

0 0 0 0 0
0 12 12 0 0
13 1 12 0 12
0 9 19 0 0
9 0 0 19 19
0 0 0 0 0

样例说明 2

例如第 行第 列原本是 x。如果把它改造成 o，就能把周围几个不同的蓄水区拼接成一个更大的整体，因此对应输出是 。

数据范围

题解

直接暴力做会很慢。

如果对每一个 x 都重新跑一遍 BFS 或 DFS，去看把它改成 o 以后能连出多大的连通块，那么一次遍历是 ，总复杂度会膨胀到 ，肯定过不去。

这题的关键不是“每个位置单独模拟”，而是先把原图里已经存在的连通块一次性处理完。

第一步：给所有 o 连通块编号

先遍历整张图。

每遇到一个还没有编号的 o，就从这里出发做一次 BFS，把整个连通块染成同一个编号，并顺手统计这个连通块的大小。

处理结束后，会得到两类信息：

• id[i][j]：位置 属于哪个连通块。
• siz[k]：编号为 的连通块大小。

这样一来，任何一个 o 属于哪个连通块、这个连通块有多大，都可以 查出来。

第二步：枚举每个 x

对于一个待改造的 x，它变成 o 之后，只可能和上下左右四个方向的连通块连起来。

所以答案就是：

• 先把自己算进去，初始值为 。
• 看四个方向有哪些 o。
• 如果相邻的 o 来自不同编号的连通块，就把这些连通块大小累加进来。

这里要注意去重。

因为同一个连通块可能从两个方向同时挨着当前格子，如果不去重，就会重复加两次。

由于只有四个方向，直接用一个很小的数组或集合去重就够了，代价非常小。

为什么这样做是对的

改造一个 x 以后，新的连通块只会由这几部分组成：

• 当前这个位置自己。
• 与它四联通相邻的那些原有 o 连通块。

除此之外，不可能再多出别的部分。

因为连通只能通过上下左右传播，而所有能通过当前格子接上的区域，入口都只能来自四个相邻位置。

所以只要把四个方向涉及到的不同连通块大小全部加起来，得到的就是唯一正确答案。

复杂度分析

设网格大小为 。

• 第一次 BFS 染色，每个格子最多进队一次，复杂度是 。
• 第二次枚举每个格子时，每个位置只检查四个方向，复杂度也是 。

总时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import sys
from collections import deque

input = lambda: sys.stdin.readline().strip()


def solve() -> None:
    n, m = map(int, input().split())
    g = [list(input()) for _ in range(n)]

    # comp[i][j] 记录当前位置属于哪个蓄水连通块，-1 表示尚未编号。
    comp = [[-1] * m for _ in range(n)]
    siz = []
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def bfs(sr: int, sc: int, idx: int) -> int:
        q = deque([(sr, sc)])
        comp[sr][sc] = idx
        cnt = 0
        while q:
            x, y = q.popleft()
            cnt += 1
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if not (0 <= nx < n and 0 <= ny < m):
                    continue
                if g[nx][ny] != 'o' or comp[nx][ny] != -1:
                    continue
                comp[nx][ny] = idx
                q.append((nx, ny))
        return cnt

    # 先给所有原有的蓄水区编号，并统计每个连通块大小。
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'o' and comp[i][j] == -1:
                idx = len(siz)
                siz.append(bfs(i, j, idx))

    ans = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'o':
                continue

            cur = 1
            used = set()
            # 当前格子变成 o 之后，只会连接四个方向的不同连通块。
            for dx, dy in dirs:
                ni, nj = i + dx, j + dy
                if not (0 <= ni < n and 0 <= nj < m):
                    continue
                if g[ni][nj] != 'o':
                    continue
                idx = comp[ni][nj]
                if idx in used:
                    continue
                used.add(idx)
                cur += siz[idx]
            ans[i][j] = cur

    for row in ans:
        print(*row)


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) {
        cin >> g[i];
    }

    vector<vector<int>> comp(n, vector<int>(m, -1));
    vector<int> siz;
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};

    auto bfs = [&](int sx, int sy, int id) {
        queue<pair<int, int>> q;
        q.push({sx, sy});
        comp[sx][sy] = id;
        int cnt = 0;

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            ++cnt;

            for (int k = 0; k < 4; ++k) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }
                if (g[nx][ny] != 'o' || comp[nx][ny] != -1) {
                    continue;
                }
                comp[nx][ny] = id;
                q.push({nx, ny});
            }
        }
        return cnt;
    };

    // 先把所有已有的蓄水区染色。
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'o' && comp[i][j] == -1) {
                int id = (int)siz.size();
                siz.push_back(bfs(i, j, id));
            }
        }
    }

    vector<vector<int>> ans(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'o') {
                continue;
            }

            int cur = 1;
            int used[4];
            int top = 0;

            // 只统计四个方向出现的不同连通块。
            for (int k = 0; k < 4; ++k) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m) {
                    continue;
                }
                if (g[ni][nj] != 'o') {
                    continue;
                }

                int id = comp[ni][nj];
                bool ok = true;
                for (int t = 0; t < top; ++t) {
                    if (used[t] == id) {
                        ok = false;
                        break;
                    }
                }
                if (!ok) {
                    continue;
                }
                used[top++] = id;
                cur += siz[id];