✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

🤖 内容包含AI辅助生成，题解和代码均经过多轮验证，有问题欢迎评论

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

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

字节-2026.04.19

字节-2026.04.19

题目一：小兰的走廊按钮

这一题的关键在于先固定按钮持续时间，再去问“最少需要按几次”。固定后可以直接从左往右贪心覆盖第一个还没处理的关闭门，再利用可行性的单调性二分答案。

难度：Mid

题目二：小兰的印章网格

判断过程要围绕“一个合法图形一定能拆成若干个彼此不接触的 红块”展开。先找完整红块，再判相邻冲突，最后做一遍覆盖核验，三个步骤缺一不可。

难度：Mid

题目三：小兰的尾零字典序

操作虽然作用在整个数组上，但变化的是因子 的位置分布。字典序比较优先看前缀，所以应该从左到右尽量把前面的因子 拿走，并把代价统一丢到最后一个位置。

难度：Mid

题目四：小兰的第二大池化

题意就是标准模拟，没有隐藏状态。按层处理所有 小块，每块留下第二大值，直到矩阵缩成一个数即可。

难度：Low

1. 小兰的走廊按钮

问题描述

小兰需要沿着一条长度为 的走廊从左走到右，途中会依次经过编号为 到 的门。

第 扇门的状态用 表示：

• ，表示这扇门原本就是开着的。
• ，表示这扇门原本是关着的。

她手里有一个按钮，最多可以按下 次。

如果在准备通过某一扇门时按下按钮，并把持续时间设为 ，那么从当前门开始，接下来连续 扇门都会临时视为打开状态。由于每通过一扇门恰好花费 秒，所以这个持续时间恰好对应连续 扇门。

小兰想把持续时间设得尽量短。请你求出，为了顺利通过全部门，最小的非负整数 是多少。

输入格式

第一行输入一个整数 ，表示测试数据组数。

对于每组数据：

• 第一行输入两个整数 ，分别表示门的数量和按钮最多使用次数。
• 第二行输入 个整数 ，表示每扇门的初始状态。

输出格式

对于每组数据，输出一行一个整数，表示最小的可行持续时间 。

样例输入

3
5 1
0 1 1 0 1
7 2
1 0 1 1 0 1 0
4 2
0 0 0 0

样例输出

4
3
0

样例输入 2

1
6 2
1 1 0 0 1 1

样例输出 2

2

数据范围

• 
• 
• 
• 
• 保证所有测试数据中

样例说明

样例	解释说明
样例 1	第 组数据里，若 ，从第 扇门按下按钮后只能覆盖到第 扇门，第 扇门仍然无法通过，所以最小值是 。第 组数据中所有门本来就打开，按钮一次都不用按，答案为 。
样例 2	可以在第 扇门和第 扇门前各按一次按钮，持续时间取 就能覆盖全部关闭门。

题解

先把持续时间 看成已经确定，问题会变成：

“至少要按几次按钮，才能让所有关闭门都被覆盖？”

1. 固定 后，最优策略是什么

从左到右扫描所有门。

如果当前门本来就是开的，或者已经被前一次按钮覆盖到了，那么直接继续往后走。

如果扫到的是当前最靠左、还没有被覆盖的关闭门，那么这一次按钮必须在这里按下。

原因很简单：

• 按得更晚，当前这扇门已经过不去。
• 按得更早，也不会让左边变得更好，因为左边已经处理完了。

所以固定 时，可以直接贪心：

• 遇到第一个未覆盖的关闭门，就按一次按钮。
• 这一按会覆盖当前位置开始的连续 扇门。
• 然后把指针跳到覆盖区间之后，继续扫描。

这样扫完整条走廊，得到的就是固定 时所需的最少按键次数。

2. 为什么可以二分答案

如果某个持续时间 已经可行，那么任何更大的持续时间也一定可行。

因为每次按钮能覆盖的门只会更多，不会更少。

这说明“是否能在不超过 次内通过全部门”对 具有单调性，可以直接二分最小可行值。

3. 边界怎么处理

如果整条走廊里没有一扇关闭门，那么不需要按按钮，答案就是 。

否则答案一定在 之间，直接在这个区间上二分即可。

4. 复杂度分析

二分会做 次检查。

每次检查只需要线性扫一遍门，复杂度是 。

所以单组数据总复杂度为 ，可以通过题目范围。

• Python

import sys

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

def chk(arr, x):
    n = len(arr)
    cnt = 0
    i = 0
    while i < n:
        # 原本就打开的门可以直接通过。
        if arr[i] == 0:
            i += 1
            continue

        # 这是最靠左、还没被覆盖的关闭门，
        # 这一按必须从这里开始。
        cnt += 1
        i += x
    return cnt

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n, k = map(int, input().split())
        arr = list(map(int, input().split()))

        # 全是开门时，持续时间取 0 就够了。
        if sum(arr) == 0:
            out.append("0")
            continue

        l, r = 1, n
        ans = n
        while l <= r:
            mid = (l + r) // 2
            if chk(arr, mid) <= k:
                ans = mid
                r = mid - 1
            else:
                l = mid + 1

        out.append(str(ans))

    print("\n".join(out))

if __name__ == "__main__":
    solve()

• Cpp

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

int need(const vector<int>& arr, int x) {
    int n = (int)arr.size();
    int cnt = 0;

    for (int i = 0; i < n; ) {
        // 开门可以直接通过。
        if (arr[i] == 0) {
            ++i;
            continue;
        }

        // 这是最靠左的未覆盖关闭门，
        // 按钮必须从这里开始生效。
        ++cnt;
        i += x;
    }

    return cnt;
}

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

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> arr(n);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
            sum += arr[i];
        }

        // 没有关闭门时，答案就是 0。
        if (sum == 0) {
            cout << 0 << "\n";
            continue;
        }

        int l = 1, r = n, ans = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (need(arr, mid) <= k) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        cout << ans << "\n";
    }
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    static int need(int[] arr, int x) {
        int n = arr.length;
        int cnt = 0;

        for (int i = 0; i < n; ) {
            // 开门不需要额外处理。
            if (arr[i] == 0) {
                i++;
                continue;
            }

            // 当前最靠左的未覆盖关闭门，
            // 只能从这里开始按按钮。
            cnt++;
            i += x;
        }

        return cnt;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder out = new StringBuilder();

        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int[] arr = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                sum += arr[i];
            }

            // 全部已经打开时，最优持续时间就是 0。
            if (sum == 0) {
                out.append(0).append('\n');
                continue;
            }

            int l = 1, r = n, ans = n;
            while (l <= r) {
                int mid = (l + r) >>> 1;
                if (need(arr, mid) <= k) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            out.append(ans).append('\n');
        }

        System.out.print(out);
    }
}

2. 小兰的印章网格

问题描述

小兰有一枚固定大小为 的印章。每按一次印章，对应的 子矩阵都会被全部染成红色。

她在一张 的网格上按下了若干次印章，并且整个过程始终满足两条规则：

• 每个格子至多被染色一次。
• 任意两个红色 块都不能相邻。这里的相邻指两块红色区域只要共用一条边，或者只共用一个角，都算相邻。

现在只知道最终得到的矩阵：

• * 表示这个格子是红色。
• . 表示这个格子没有被染色。

请你判断，这个最终矩阵是否可能由上述过程得到。

共有 组询问。

输入格式

第一行输入一个整数 ，表示询问组数。

对于每组数据：

• 第一行输入两个整数 ，表示网格的行数和列数。
• 接下来输入 行，每行是一个长度为 的字符串，只包含 * 和 .。

输出格式

对于每组数据输出一行。

• 如果这个矩阵合法，输出 Yes。
• 否则输出 No。

样例输入

3
6 7
**...**
**...**
.......
.......
**...**
**...**
4 6
**....
**....
..**..
..**..
3 4
.**.
.**.
....

样例输出

Yes
No
Yes

样例输入 2

2
1 5
.*.*.
2 3
***
***

样例输出 2

No
No

数据范围

样例说明

样例	解释说明
样例 1	第 组数据里有四个彼此完全分开的 红块，所以合法。第 组数据中两块红色区域会在角上接触，不满足题意。第 组数据恰好是一枚单独的印章。
样例 2	第 组数据连一枚完整的 印章都放不下。第 组数据会产生两个互相重叠的候选印章位置，也不合法。

题解

这一题只需要判断最终图形能否拆成若干块互不接触的 红块。

1. 合法印章留下来的样子

一次印章会把一个完整的 区域染红。

所以只要某个图形是合法答案，那么其中每一个红色格子都必须属于某个完整的 红块。

这给出了第一步做法：

• 枚举所有左上角位置。
• 找出所有四个格子全为 * 的 红块。

2. 怎么判断这些红块会不会互相接触

设两个候选红块的左上角分别是 和 。

由于每个红块固定都是 ，只要同时满足：

这两块就一定会出现下面某一种情况：

• 重叠；
• 共边；
• 只共角。

这些情况全都不允许。

反过来，只要行差或列差有一个超过 ，两块之间就至少隔开了一整行或一整列，不会互相接触。

因此可以把每个候选红块的左上角记下来，再检查周围 的左上角范围里有没有别的候选块。

3. 为什么最后还要做一次覆盖检查

找到候选红块并且确认它们彼此不接触后，事情还没结束。

因为原矩阵里可能还会残留某些 *，它们并不属于任何完整的 红块。

这类格子不可能通过合法印章得到。

所以还需要把所有候选红块覆盖到一张辅助表上，再扫描原矩阵：

• 如果某个 * 没有被覆盖到，答案就是 No。
• 只有所有 * 都恰好属于某个合法红块时，答案才是 Yes。

4. 特殊情况

如果 或 ，连一枚印章都放不下。

这时只有“整个矩阵全是 .”才合法，只要出现一个 * 就一定不合法。

5. 复杂度分析

枚举所有 子矩阵是 。

每个候选块只检查常数个相邻位置，最后覆盖检查也是 。

所以单组数据总复杂度为 。

• Python

import sys

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

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n, m = map(int, input().split())
        g = [input() for _ in range(n)]

        # 行或列不足 2 时，根本放不下印章。
        if n < 2 or m < 2:
            ok = True
            for i in range(n):
                for j in range(m):
                    if g[i][j] == '*':
                        ok = False
            out.append("Yes" if ok else "No")
            continue

        pos = []
        has = [[False] * m for _ in range(n)]

        # 先找出所有完整的 2x2 红块。
        for i in range(n - 1):
            for j in range(m - 1):
                if g[i][j] == '*' and g[i + 1][j] == '*' and \
                   g[i][j + 1] == '*' and g[i + 1][j + 1] == '*':
                    pos.append((i, j))
                    has[i][j] = True

        ok = True

        # 两个左上角只要同时落在 5x5 邻域内，
        # 两块红色区域就一定会接触。
        for x, y in pos:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    if dx == 0 and dy == 0:
                        continue
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < n and 0 <= ny < m and has[nx][ny]:
                        ok = False
                        break
                if not ok:
                    break
            if not ok:
                break

        if not ok:
            out.append("No")
            continue

        cov = [[False] * m for _ in range(n)]
        for x, y in pos:
            for dx in range(2):
                for dy in range(2):
                    cov[x + dx][y + dy] = True

        # 每个红格都必须被某个合法印章覆盖到。
        for i in range(n):
            for j in range(m):
                if g[i][j] == '*' and not cov[i][j]:
                    ok = False
                    break
            if not ok:
                break

        out.append("Yes" if ok else "No")

    print("\n".join(out))

if __name__ == "__main__":
    solve()

• Cpp

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

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

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

        // 尺寸太小时，合法情况只能是全白矩阵。
        if (n < 2 || m < 2) {
            bool ok = true;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {