✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

虾皮-2026.03.18

虾皮-2026.03.18

这套题的区分度还可以。第 1 题虽然是标准滑动窗口，但如果没意识到题意里的“子序列”其实对应连续子数组，很容易一开始就建错模型；第 2 题更偏实现，核心是把“只反转小写字母”这件事做得足够干净；第 3 题则是经典动态规划，重点在于状态里要同时容纳“继续剪”和“不再剪”两种选择。

题目一：巡逻编队的多样片段

这题本质是统计“恰好包含 种不同元素”的连续子数组个数。直接做不好维护，转成“至多 种”减去“至多 种”以后，双指针就很顺了。

难度：Mid

题目二：口号里的小写回放

这题没有复杂算法，关键是不要把整个单词反转，而是只把其中的小写字母抽出来逆序回填。大写字母、数字和空格的位置都必须原封不动。

难度：Low

题目三：封箱绳的最优分段

经典剪绳子模型。真正要想清楚的是，某一段在转移时到底应该继续拆，还是直接把长度本身拿来参与乘积；这个判断正是动态规划状态设计的关键。

难度：Mid

1. 巡逻编队的多样片段

问题描述

小基 在整理一支巡逻编队的训练记录。序列中的第 个数字 表示第 名队员所属的兵种编号。

她想从这份记录里截出若干段连续片段，要求每段里恰好出现 种不同的兵种。请你统计，满足条件的连续片段一共有多少个。

注意，这里统计的是连续片段，也就是连续子数组，而不是任意跳着选的子序列。

输入格式

第一行输入两个整数 ，表示训练记录的长度，以及希望片段中恰好包含的不同兵种数量。

第二行输入 个整数 ，表示整份训练记录。

输出格式

输出一个整数，表示恰好包含 种不同兵种的连续片段数量。

样例输入

5 2
1 2 1 2 3

样例输出

7

数据范围

样例	解释说明
样例1	满足条件的连续片段共有 个，分别是 [1,2]、[2,1]、[1,2]、[2,3]、[1,2,1]、[2,1,2]、[1,2,1,2]。
补充示例	若输入为 5 3，数组为 1 2 1 3 4，那么满足条件的连续片段是 [1,2,1,3]、[2,1,3]、[1,3,4]，答案为 3。

题解

这题如果直接去维护“恰好有 种不同数字”，窗口的增删会比较别扭。更自然的处理方式是先把问题拆成：

• 统计“至多有 种不同数字”的连续片段数量。
• 再减去“至多有 种不同数字”的连续片段数量。

为什么这样就能得到答案？

• “至多 种”里面，包含了“恰好 种”“恰好 种”……一直到“恰好 种”。
• “至多 种”里面，只包含“恰好 种”到“恰好 种”。
• 两者一减，剩下的正好就是“恰好 种”。

所以关键只剩一个子问题：怎么在线性时间内统计“至多 种”？

这里直接用滑动窗口。维护一个左右端点 ，再用哈希表记录窗口里每个数字的出现次数，以及当前窗口里一共有多少种不同数字。

当右端加入一个新数时：

• 如果这个数原来没出现过，不同数字种类数加一。
• 如果种类数超过了 ，就不断右移左端点，把多余的数字赶出去，直到窗口重新满足“至多 种”。

一旦窗口满足条件，以 结尾的合法连续片段数量就是：

因为左端可以取 ，这些片段都会落在当前合法窗口里。

整套过程每个元素最多进窗口一次、出窗口一次，所以总时间复杂度是 ，空间复杂度是 。在 的范围内完全可以通过。

参考代码

• Python

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


def calc(arr, lim):
    if lim < 0:
        return 0

    cnt = {}
    l = 0
    kind = 0
    ans = 0

    for r, x in enumerate(arr):
        pre = cnt.get(x, 0)
        cnt[x] = pre + 1
        if pre == 0:
            kind += 1

        # 让窗口重新满足“至多 lim 种不同数字”。
        while kind > lim:
            y = arr[l]
            cnt[y] -= 1
            if cnt[y] == 0:
                del cnt[y]
                kind -= 1
            l += 1

        # 以 r 结尾的所有合法区间都能一次性计入答案。
        ans += r - l + 1

    return ans


def solve():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    print(calc(arr, k) - calc(arr, k - 1))


if __name__ == "__main__":
    solve()

• Cpp

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

long long calc(const vector<int>& arr, int lim) {
    if (lim < 0) {
        return 0;
    }

    unordered_map<int, int> cnt;
    int l = 0;
    int kind = 0;
    long long ans = 0;

    for (int r = 0; r < (int)arr.size(); r++) {
        int x = arr[r];
        if (++cnt[x] == 1) {
            kind++;
        }

        // 不同数字过多时，持续缩小左端点。
        while (kind > lim) {
            int y = arr[l++];
            if (--cnt[y] == 0) {
                cnt.erase(y);
                kind--;
            }
        }

        // 以 r 结尾的合法区间个数。
        ans += r - l + 1;
    }

    return ans;
}

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

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

    cout << calc(arr, k) - calc(arr, k - 1) << '\n';
    return 0;
}

• Java

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

public class Main {
    static long calc(int[] arr, int lim) {
        if (lim < 0) {
            return 0L;
        }

        HashMap<Integer, Integer> cnt = new HashMap<>();
        int left = 0;
        int kind = 0;
        long ans = 0L;

        for (int right = 0; right < arr.length; right++) {
            int x = arr[right];
            int now = cnt.getOrDefault(x, 0) + 1;
            cnt.put(x, now);
            if (now == 1) {
                kind++;
            }

            // 如果种类数超标，就缩小窗口。
            while (kind > lim) {
                int y = arr[left++];
                int c = cnt.get(y) - 1;
                if (c == 0) {
                    cnt.remove(y);
                    kind--;
                } else {
                    cnt.put(y, c);
                }
            }

            // 当前窗口内，以 right 结尾的区间都合法。
            ans += right - left + 1L;
        }

        return ans;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int k = fs.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = fs.nextInt();
        }

        System.out.println(calc(arr, k) - calc(arr, k - 1));
    }

    static class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        FastScanner(Inp