大厂真题 / 小红书

小红书通用岗 2026-09-20

内容边界：本场笔试共披露 2 道编程题，没有选择题。本文只收录这 2 道题，不补写原文未披露的题目、样例与约束。

本场考试概述

考试时间：2026年9月20日 考试岗位：通用岗 难度评级：中等偏难

考点分析：

• 第一题 最短安全标签：贪心（难度中等）
• 第二题 笔记领域优化：排序 + 前缀和 + 贪心（难度困难）

建议策略：

• 第一题的代码只有一趟扫描，难点全在”为什么可以按集齐 $26$ 个字母切段”这个结论上，想清楚再动手，写起来很快。

• 第二题先把”能不能做到”翻译成两条不等式（总量够分、次数够用），再枚举达标领域的个数，不要一上来就想构造具体的搬运方案。

• 两道题都要注意数据范围：第一题的字符串长度到 $10^{5}$，第二题的调整次数到 $10^{14}$，答案会超过 $32$ 位整数。

第 1 题：最短安全标签

题目描述

运营团队要为新的内容板块设计一个独一无二的安全标签。这个标签不能以子序列的形式出现在任何已有笔记标题里，否则会和既有内容混淆。

把所有已知笔记标题按发布顺序拼接成一个长字符串 $S$，则 $S$ 的每一个子序列都被视为”已经出现过”的标签。现在要找出最短的、不是 $S$ 的子序列的字符串，只需要输出它的长度。

子序列的定义是：原字符串删除任意个（可以删除 $0$ 个）字符后得到的字符串，包括原串本身和空串。

输入描述

输入一行，一个只由小写字母组成的字符串 $S$（$1 \le \lvert S\rvert \le 10^{5}$）。

输出描述

输出一行一个正整数，表示最短安全标签的长度。

样例1

输入

abcdefghijklmnopqrstuvwxyz

输出

2

样例解释

$S$ 包含了全部 $26$ 个小写字母，所以任何长度为 $1$ 的标签都是 $S$ 的子序列。长度为 $2$ 的标签中，$\mathtt{aa}$ 无法从 $S$ 中删字符得到（$S$ 里只有一个 $\mathtt{a}$），它就是一个安全标签，因此答案为 $2$。

题解：贪心

思路分析

第一步：把”求最短”反过来问

朴素做法是按长度枚举候选标签：长度为 $L$ 的小写串共有 $26^{L}$ 个，$L=4$ 时已经接近 $46$ 万，每个候选还要 $O(\lvert S\rvert)$ 判一次子序列，搜索空间随 $L$ 指数增长，走不通。

把问题反过来问：长度 $L$ 的串是不是全都是 $S$ 的子序列？只要找到最小的、答案恰好为”否”的 $L$，问题就解决了。

第二步：子序列匹配取最早位置

判断一个串是否是 $S$ 的子序列，标准做法是贪心匹配：从左往右扫描 $S$，每一位都在 $S$ 里取最早能匹配上的位置。取最早最优，因为位置越靠左、留给后面字符的空间越大，能匹配成功的情形是取更靠后位置时的超集。

第三步：切段判据

把上面这条贪心反过来看，就得到了切段判据：从左扫 $S$，当前段一旦集齐 $26$ 个字母就切一刀、重新计数。设切出 $k$ 个完整段，末尾还剩一段残缺的尾巴，则答案就是 $k+1$。

第四步：两侧各证一遍

先看长度 $k$ 的串为什么全都是子序列。任取一个长度 $k$ 的串，它的第 $i$ 位必定在第 $i$ 段里出现过（每一段都包含完整的 $26$ 个字母），逐段往下接就能把整个串匹配完。

再构造一个长度 $k+1$ 的反例。令 $c_i$ 为第 $i$ 个完整段的最后一个字符。因为每段都在首次集齐字母时结束，$c_i$ 在该段此前没有出现。对字符串 $c_1c_2\cdots c_k$ 做最早位置匹配时，第 $i$ 位恰好匹配到第 $i$ 段末尾，而不是任意位置。因此，在它后面追加一个尾巴中缺失的字母，就一定无法继续匹配。

边界落在 $k=0$：$S$ 本身没集齐 $26$ 个字母时答案为 $1$，对应那个从未在 $S$ 里出现过的单字母。

算法实现

一趟扫描 $S$，用集合 seen 记录当前段出现过哪些字母。集合大小达到 $26$ 就切出一段，并清空集合。扫描结束后输出完整段数加一。

复杂度分析

时间复杂度：$O(\lvert S\rvert)$。瓶颈就是这一趟扫描，每个字符只处理一次；是否集齐靠一个计数器判定，不需要重扫字母表，所以既省不掉也快不了。

空间复杂度：额外空间为 $O(1)$，集合至多存储 $26$ 个字母；若计入读入字符串的存储，则为 $O(\lvert S\rvert)$。

题解代码

import sys

input = sys.stdin.readline


def solve():
    s = input().strip()
    seen = set()          # 当前这一段里出现过的字母
    blocks = 0            # 已经切出的完整段数
    for ch in s:
        seen.add(ch)
        # 本段集齐 26 个字母就切一刀、重新计数；切出 k 段则答案为 k + 1
        if len(seen) == 26:
            blocks += 1
            seen.clear()
    print(blocks + 1)


solve()

正确性说明

任意长度 $k$ 的小写串都可以逐段匹配，因此长度不超过 $k$ 的字符串都不是安全标签。另一方面，依次取各完整段的末字符，再追加尾巴缺失的字母，最早匹配必定逐段停在段末，最后一位无法匹配。这给出了长度 $k+1$ 的安全标签，故答案恰为 $k+1$。

易错点与边界

• 切段的条件是”当前段集齐 $26$ 个字母”，不是”集齐 $S$ 里出现过的字母”，否则样例里的 $S$ 不会切出完整段。
• 尾巴不计入 $k$，例如 $S$ 是两个完整字母表加一段 “abc” 时，$k$ 仍为 $2$、答案为 $3$。
• 用集合记录已见字母时可以直接用长度判集齐，不需要额外的哈希计数。

第 2 题：笔记领域优化

题目描述

平台共有 $n$ 个内容领域（例如美妆、穿搭、美食、旅行）。第一阶段结束时，第 $i$ 个领域发布了 $a_i$ 篇笔记。

第二阶段可以在不同领域之间调整笔记归属：把第 $i$ 个领域的一篇笔记转移到第 $j$ 个领域，操作完成后 $a_i$ 减一、$a_j$ 加一，任何时刻都必须保证每个领域的笔记数非负，且这样的调整操作不超过 $k$ 次。

第三阶段平台评估综合影响力。具体规则是：令 $x$ 表示笔记数量不少于 $b$ 篇的领域个数，$y$ 表示所有领域中笔记数量的最小值，即 $y = \min(a_1, a_2, \dots, a_n)$，则综合影响力定义为 $x \times c_1 + \min(y, b) \times c_2$，并且保证 $c_1 \ge c_2$。

可以任意选择调整的领域对，求综合影响力的最大值。

输入描述

输入第一行有五个正整数 $n, k, b, c_1, c_2$（$1 \le n \le 10^{5}$，$1 \le k \le 10^{14}$，$1 \le b \le 10^{9}$，$1 \le c_2 \le c_1 \le 10^{9}$）。

第二行有 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^{9}$），含义如题。

输出描述

输出一个整数，表示理想情况下综合影响力的最大值。

样例1

输入

4 4 5 6 3
1 1 7 7

输出

21

样例解释

把第 $3$ 个领域和第 $4$ 个领域各转出 $2$ 篇笔记给第 $2$ 个领域，共 $4$ 次调整，各领域笔记数变为 $(1,5,5,5)$。此时笔记数不少于 $b=5$ 的领域有 $3$ 个，最小值 $y=1$，综合影响力为 $3 \times 6 + \min(1,5) \times 3 = 21$。

样例2

输入

4 3 5 10 2
2 6 4 3

输出

30

样例解释

把第 $1$ 个领域的 $2$ 篇笔记分别转给第 $3$ 个领域和第 $4$ 个领域，再把第 $2$ 个领域的 $1$ 篇笔记转给第 $4$ 个领域，共 $3$ 次调整，各领域笔记数变为 $(0,5,5,5)$。此时 $x=3$，$y=0$，综合影响力为 $3 \times 10 + 0 \times 2 = 30$。

题解：排序 + 前缀和 + 贪心

思路分析

第一步：直接搜终态不可行

记总笔记数为 $S = a_1 + a_2 + \cdots + a_n$。朴素做法是枚举终态，但把 $S$ 篇笔记分给 $n$ 个领域的方案数是组合级的，$n$ 到 $10^{5}$ 时根本排不开。

第二步：把”能不能做到”翻译成两条不等式

突破口是终态不必完整确定：评分只认 $x$ 和 $y$。于是把目标写成一组下界——让 $x$ 个领域达到 $b$、其余 $n-x$ 个领域达到 $y$。给定一组 $(x,y)$，可行的充要条件是

• 总量够分：$S \ge x \times b + (n-x) \times y$；
• 次数够用：$\sum \max(0, t_i - a_i) \le k$，其中 $t_i$ 是第 $i$ 个领域的目标下界，在达标组中取 $b$，其余取 $y$，且 $0\le y\le b$。

第一条来自总量守恒。记缺口总量为 $D=\sum\max(0,t_i-a_i)$，可供转出的富余为 $E=\sum\max(0,a_i-t_i)$。由 $S\ge\sum t_i$ 得 $E\ge D$，所以可从富余领域逐篇转给缺口领域，恰好用 $D$ 次补齐下界，未用的富余留在原处即可。这样不会把任何供给方降到其目标下界以下。

第三步：达标名额该给谁

一个领域进达标组要补 $\max(0,b-a)$，留在低位组只需补 $\max(0,y-a)$。对于任意固定的 $0\le y\le b$，两者的差值关于 $a$ 单调不增：当 $a<y$ 时为 $b-y$，当 $y\le a<b$ 时为 $b-a$，当 $a\ge b$ 时为 $0$。差值本身依赖 $y$，但按 $a$ 从大到小选择的顺序不依赖 $y$。因此排序后把达标名额分给最大的 $x$ 个，对所有 $y$ 都最优。

第四步：固定 $x$，求最大的 $y$

把 $a$ 升序排序，记低位组规模 $m = n-x$，$pre$ 为前缀和。把低位组里最小的 $cnt$ 个抬到同一高度的代价是 $y \times cnt - pre[cnt]$，令它不超过剩余次数 $rem$ 就能反解出 $y$，再与总量给出的上限 $\lfloor (S - x \times b) / m \rfloor$ 以及 $b$ 取较小者。

这里不需要对 $y$ 二分：$m$ 增大时达标组缩小、剩余次数只增不减，而分界判据 $a_j \times j - pre[j]$（下标从 $1$ 开始）与 $m$ 无关，所以分界点只会一路右移，用单指针扫到底即可。

第五步：处理 $x = n$ 的边界

$x = n$ 时所有领域都达到了 $b$、最小值也不低于 $b$，$\min(y,b)$ 直接取满 $b$，综合影响力就是 $n \times c_1 + b \times c_2$，需要单独判断，此时低位组规模 $m = 0$ 不能参与上面的计算。

算法实现

先把 $a$ 升序排序，预处理前缀和 $pre$ 与后缀代价 $top$：$pre[i]$ 表示最小的 $i$ 个领域笔记之和，$top[i]$ 表示把下标 $i$ 到 $n-1$ 这些领域全部补到 $b$ 需要多少次调整。然后枚举低位组规模 $m$，对应达标个数 $x = n-m$，用 $top[m]$ 判断次数是否够用，用剩余次数反解出最大的 $y$，与总量上限取较小者，再更新答案。分界点用单指针维护。

复杂度分析

时间复杂度：$O(n \log n)$。排序占主导，前缀和、后缀代价与单指针扫描均为 $O(n)$。

空间复杂度：$O(n)$。排序后的数组之外，还需要前缀和与后缀代价两个长度为 $n+1$ 的数组。

题解代码

import sys

input = sys.stdin.readline


def solve():
    n, k, b, c1, c2 = map(int, input().split())
    a = sorted(map(int, input().split()))
    total = sum(a)

    # pre[i]：升序后最小的 i 个领域笔记之和；top[i]：把下标 i..n-1 全部补到 b 的次数
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]
    top = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        top[i] = top[i + 1] + max(0, b - a[i])

    best = 0
    # x = n 时全部领域达标，min(y, b) 直接取满 b，需要单独算
    if total >= n * b and top[0] <= k:
        best = n * c1 + b * c2

    # 枚举低位组规模 m（达标个数 x = n - m）；j 是"能被统一抬高"的分界，只会右移
    j = 0
    for m in range(1, n + 1):
        x = n - m
        rem = k - top[m]
        if rem < 0:
            continue
        room = total - x * b
        if room < 0:
            continue
        cap = min(b, room // m)
        while j + 1 <= m - 1 and a[j + 1] * (j + 1) - pre[j + 1] <= rem:
            j += 1
        cnt = j + 1
        y = min(cap, (rem + pre[cnt]) // cnt)
        if x * c1 + y * c2 > best:
            best = x * c1 + y * c2
    print(best)


solve()

正确性说明

两条不等式对目标下界既必要也充分：总量不足则无法满足全部下界，缺口大于 $k$ 则无法补齐；反之，富余总量不少于缺口，可用恰好等于缺口的次数完成搬运。交换论证保证最大的 $x$ 个领域作为达标组具有最小缺口；固定该组后，单指针求出预算允许的最高水位，再与总量上限取较小者，得到最大的可行 $y$。

这里要求的是“至少 $x$ 个达标”，不是恰好 $x$ 个，所以候选分数不会高于相应可行终态的实际分数。另一方面，对最优终态取其真实达标数 $x$ 和截断后的最小值 $y$，该组合必在枚举范围内，算法求得的水位不会更低。因此枚举所得最大分数恰好等于全局最优值。

易错点与边界

• 答案上界是 $n \times c_1 + b \times c_2 \approx 10^{18}$，Java、C++ 等语言必须使用 $64$ 位整数。
• $x = n$ 必须单独处理，此时 $\min(y,b)$ 取满 $b$，且低位组规模为 $0$ 不能做除法。
• $y$ 的上限同时受”总量”和”剩余次数”两个约束，只取其中一个会把答案算大。
• 达标名额要取升序后最大的那几个，凭直觉取最小的会得到更差的方案。
• 调整次数可以恰好用完，也可以不用完，只要不超过 $k$ 次就行。

小结

• 第一题：求”最短的非子序列”时把问题反过来——判断长度 $L$ 是否全部是子序列，按集齐 $26$ 个字母切段，答案就是完整段数加一，时间 $O(\lvert S\rvert)$、空间 $O(1)$。
• 第二题：把终态可行性写成”总量够分、次数够用”两条不等式，达标名额取升序后最大的 $x$ 个，再枚举 $x$ 用前缀和反解最大的 $y$，时间 $O(n \log n)$、空间 $O(n)$。
• 两题都体现同一套思路：先把题目条件翻译成可判定的不等式或分段判据，再在可行的结构上贪心，而不是直接模拟构造。