✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

得物-2026.03.21

这套三题的梯度很清楚：先做基础模拟，再做“并查集 + 二分答案”的建模题，最后收在前缀和计数。整体不算特别刁钻，但第二题如果没有先抓住单调性，很容易卡在暴力分组上。

第 1 题：双入口停车场

这题是直接模拟。事件 L 找最左空位，事件 R 找最右空位，数字事件把对应车位释放。
数据范围只有 ，每次线性扫描就足够，总复杂度是 。

第 2 题：同组约束的最大上限

当给定上限 后，满足 的两人必须同组。
把这些约束连成边以后，分组数就是连通块个数。随着 增大，连通块数量只会减少或不变，因此可以二分答案，每次用并查集判断当前上限是否可行。

第 3 题：连续糖罐的差值方案数

把每个糖罐转成差值 ，原题就变成统计和为 的连续子数组个数。
用前缀和加哈希表计数，扫到当前前缀和 时，把之前出现过的 的次数累加进答案即可，总复杂度是 。

01. 双入口停车场

双入口停车场

问题描述

小柯在维护一条只有一排车位的停车场，车位从左到右编号为 。停车场有左右两个入口，车辆进场时遵循固定策略：

• 事件 L：有车从左侧进入，停到当前最靠左的空车位。
• 事件 R：有车从右侧进入，停到当前最靠右的空车位。
• 事件是数字 ：表示车位 上的车离开。

如果某辆车入场时已经没有空位，那么它会直接离开，停车场状态保持不变。

现在按顺序给出 条事件。初始时所有车位都为空。
请你输出所有最终仍为空的车位编号，并按升序排列。

输入格式

• 第一行两个整数 ，表示车位数和事件数。
• 接下来 行，每行是一个事件：L、R 或一个整数。

输出格式

输出一行，按从小到大输出所有空车位编号，空格分隔。

样例输入

6 5
R
L
L
1
R

样例输出

1 3 4

数据范围

• 
• 
• 数字事件满足
• 保证最终至少存在一个空车位

题解

按题意逐条模拟即可。

维护一个长度为 的布尔数组 ：

• 表示车位 已占用
• 表示车位 为空

处理事件：

• L：从左到右找到第一个空位并占用。
• R：从右到左找到第一个空位并占用。
• 数字 ：将 设为空。

最后再从左到右收集所有空位输出。

因为 很小，每次事件线性扫描就足够。

• 时间复杂度：
• 空间复杂度：

参考代码

• Python

import sys

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


def solve() -> None:
    n, m = map(int, input().split())
    occ = [0] * (n + 1)

    for _ in range(m):
        op = input()
        if op == "L":
            for i in range(1, n + 1):
                if occ[i] == 0:
                    occ[i] = 1
                    break
        elif op == "R":
            for i in range(n, 0, -1):
                if occ[i] == 0:
                    occ[i] = 1
                    break
        else:
            occ[int(op)] = 0

    ans = [str(i) for i in range(1, n + 1) if occ[i] == 0]
    print(" ".join(ans))


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<int> occ(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        string op;
        cin >> op;
        if (op == "L") {
            for (int p = 1; p <= n; ++p) {
                if (!occ[p]) {
                    occ[p] = 1;
                    break;
                }
            }
        } else if (op == "R") {
            for (int p = n; p >= 1; --p) {
                if (!occ[p]) {
                    occ[p] = 1;
                    break;
                }
            }
        } else {
            int p = stoi(op);
            occ[p] = 0;
        }
    }

    bool first = true;
    for (int i = 1; i <= n; ++i) {
        if (!occ[i]) {
            if (!first) cout << ' ';
            cout << i;
            first = false;
        }
    }
    cout << '\n';
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            int c;
            while ((c = read()) <= ' ') {
                if (c == -1) return null;
            }
            StringBuilder sb = new StringBuilder();
            while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = Integer.parseInt(fs.next());
        int m = Integer.parseInt(fs.next());

        int[] occ = new int[n + 1];
        for (int i = 0; i < m; i++) {
            String op = fs.next();
            if ("L".equals(op)) {
                for (int p = 1; p <= n; p++) {
                    if (occ[p] == 0) {
                        occ[p] = 1;
                        break;
                    }
                }
            } else if ("R".equals(op)) {
                for (int p = n; p >= 1; p--) {
                    if (occ[p] == 0) {
                        occ[p] = 1;
                        break;
                    }
                }
            } else {
                int p = Integer.parseInt(op);
                occ[p] = 0;
            }
        }

        StringBuilder out = new StringBuilder();
        boolean first = true;
        for (int i = 1; i <= n; i++) {
            if (occ[i] == 0) {
                if (!first) out.append(' ');
                out.append(i);
                first = false;
            }
        }
        System.out.println(out);
    }
}

02. 同组约束的最大上限

同组约束的最大上限

问题描述

小柯要把一批成员分成若干组。第 个人有两个属性：能力值 和性格值 。
两个人之间的差别值定义为：

给定一个差别上限 。若某两个人的差别值不超过 ，那么这两个人必须被放进同一组。
请你求出：在最终分组数不少于 的前提下， 最大可以取多少。

输入格式

• 第一行两个正整数 。
• 第二行 个整数：。
• 第三行 个整数：。

输出格式

输出一个整数，表示满足“组数至少为 ”时的最大差别上限。

样例输入

3 2
1 9 3
2 7 8

样例输出

7

数据范围

• 
• 
• 任意两个人至少在一项属性上不同

题解

1. 固定上限 后如何判断

把每个人看成图上的一个点。
若两人满足：

就连一条边。因为“必须同组”有传递性，最终的分组数就是这个图的连通块个数。

所以对固定的 ，我们只要用并查集合并所有满足条件的点对，最后统计连通块个数 即可。

2. 单调性

当 变大时，满足条件的边只会更多，连通块数量只会不变或减少。
因此 关于 单调不增。

题目要求“分组数至少为 ”，即：

这对 是一个单调可判定条件，可以二分答案。

3. 算法

1. 设二分区间为 ，其中 是所有点对差别值最大值。
2. 二分中点 ，检查 是否成立。
3. 若成立，说明还能增大 ；否则缩小 。
4. 最终得到最大的可行 。

4. 复杂度

设人数为 。

• 单次检查：枚举所有点对并查集合并，
• 二分次数：，其中 是距离值范围
• 总时间复杂度：
• 空间复杂度：

参考代码

• Python

import sys

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


class DSU:
    def __init__(self, n: int):
        self.fa = list(range(n))
        self.sz = [1] * n
        self.comp = n

    def find(self, x: int) -> int:
        while self.fa[x] != x:
            self.fa[x] = self.fa[self.fa[x]]
            x = self.fa[x]
        return x

    def union(self, x: int, y: int) -> None:
        fx = self.find(x)
        fy = self.find(y)