大厂真题

小红书通用岗 2026-09-10

本场考试概述

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

考点分析：

• 第一题：可达性 DP （bitset 优化）（难度中等）
• 第二题：二分答案 + 贪心（难度中等）

建议策略：

• 第一题先把”两个值拆进两组”转成”给 配正负号”，再按差值值域记录每格的可达集合，只保留最小差值会得到错误答案
• 第二题看到”最小化最大值”就想二分答案，判定时贪心从左往右摆，注意两篇笔记可以紧挨着放，不需要留空位

第 1 题：平衡路径

题目描述

小红书的数据分析师正在处理一份 行 列的实验数据表。每个单元格包含两个特征值，分别记为 和 。

分析师需要从左上角的单元格 开始，依次处理到右下角的单元格 。每次只能移动到正下方 或正右方 的相邻单元格，不能跳出表格。

对于每一个经过的单元格（包括起点和终点），分析师需要将它的两个特征值分别归入两个不同的数据组：将其中一个特征值归入”第一组”，另一个归入”第二组”。

也就是说，每个单元格的两个特征值会被拆开，一个进入第一组总和，一个进入第二组总和。

定义”组间差值”为：第一组总和与第二组总和之差的绝对值。

分析师希望通过选择合适的处理路径以及每个单元格的分配方式，使得最终的组间差值尽可能小。请你帮他计算出这个最小值。

输入描述

输入包含 行。

第一行包含两个整数 ，表示表格的行数和列数。

接下来的 行，每行包含 个整数，其中第 行第 个数为 。

再接下来的 行，每行包含 个整数，其中第 行第 个数为 。

输出描述

输出一行一个整数，表示可能的最小组间差值。

样例1

输入

2 2
1 2
3 4
2 8
2 1

输出

1

题解：可达性 DP

思路分析

每个格子的两个值必须拆进两组，等价于给 配一个正号或负号；要在所有从左上到右下的路径中，让路径上这些带号 之和的绝对值最小。

这是一道把”求最小值”改写成”求可达集合”的网格 DP：只记每格的最小差值是错的，前半段差值为 的方案后面遇到 只能得到 ，而前半段差值为 的方案反而能抵消成 ，所以必须保留每格能凑出的全部差值。

算法实现

先看集合有多大。路径恰好经过 个格子，每个 ，差值一定落在 内。枚举路径有 条，指数级不可行；按差值值域做状态，每格只需一个长度 的布尔数组 。

状态方程定义：

状态方程初始化：

起点之前差值为 ，所以 。

状态方程转移：

走到 只能从上方或左方来，先把两个来源的集合取并，再给当前格的 配正负号。 时两个分支相同，集合原样传下去，不用特判。

集合用 bitset 存，第 位为 表示差值 可达。于是整体加 就是左移 位、整体减 就是右移 位，一次移位处理全部差值。每行只依赖上一行，按列滚动成一维数组 ， 被覆盖前存的正是上一行同列。

答案是 中绝对值最小的元素。集合关于 对称（路径上所有格子同时换号仍合法），所以从第 位往高位找第一个 即可。

复杂度分析

时间复杂度：O(HW⌈D/b⌉)，D=25441，b 为大整数内部字位数；提取最低可达位另需 O(⌈D/b⌉)。

空间复杂度：O(HW+W⌈D/b⌉) 个机器字，包含两个输入矩阵。

题解代码

import sys
input = sys.stdin.readline

OFF = 159 * 80

def min_balance(h, w, a, b):
    f = [0] * w
    for i in range(h):
        for j in range(w):
            d = abs(a[i][j] - b[i][j])
            if i == 0 and j == 0:
                src = 1 << OFF  # 起点之前差值为 0
            else:
                src = 0
                if i > 0:
                    src |= f[j]  # f[j] 还没被本行覆盖，存的是上一行同列
                if j > 0:
                    src |= f[j - 1]  # 本行左边一格已算好
            f[j] = (src << d) | (src >> d)
    nonnegative = f[w - 1] >> OFF
    return (nonnegative & -nonnegative).bit_length() - 1

h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))
b = []
for _ in range(h):
    b.append(list(map(int, input().split())))

print(min_balance(h, w, a, b), end='')

正确性说明

到当前格的路径只能来自上方或左方，因此合并二者可达集合不重不漏。每个格子的分配只有正负差值两种，移位恰好生成这两个后继。由起点归纳到终点后，集合包含全部合法差值，取最小绝对值即为答案。

易错点与边界

不能只保存每格当前最小差值；起点和终点均参与分配，偏移必须覆盖整个路径差值。

第 2 题：最优笔记排布

题目描述

小明是一位小红书博主，她准备在推荐流的连续 个位置上发布笔记。每个位置都有一个用户互动热度值 。她有 篇笔记需要按顺序依次放入推荐流中，第 篇笔记会占据连续的 个位置。我们定义 代表第 篇笔记的起始位置，则该笔记会占据区间 。

发布时需要满足以下条件：

1. 所有笔记占据的位置互不重叠，即对于任意 ，有 ；笔记与笔记之间可以留存任意数量的空位置。
2. 笔记必须按顺序发布，即 。
3. 所有笔记必须在推荐流范围内，即 且 。

我们定义，对每一篇笔记，取其覆盖区间内热度最大值；所有笔记的这些最大值中，最大的那个就是峰值热度。

即 。

低调的小明希望找到一个发布方案，使得峰值热度尽可能小。请你帮她求出这个最小值。

输入描述

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

对于每组测试数据：

第一行两个正整数 ，表示推荐流位置数和笔记篇数，所有测试数据的 之和不超过 。

第二行 个正整数 ，表示每个位置的热度值。

第三行 个正整数 ，表示每篇笔记占据的位置数。

输出描述

对于每组测试数据，输出一行一个整数，表示峰值热度的最小值。

样例1

输入

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

输出

3
1

样例解释

第一组：将第一篇笔记放在位置 （覆盖热度值 ，最大值为 ），第二篇笔记放在位置 （覆盖热度值 ，最大值为 ）。峰值热度为 。

第二组：将三篇笔记分别放在位置 、、（覆盖热度值均为 ），峰值热度为 。

题解：二分答案 + 贪心

思路分析

把 段长度固定的区间按顺序、互不重叠地摆进长度 的序列，让所有区间覆盖到的元素最大值尽可能小。

这是一道”最小化最大值”的二分答案题：固定上限 后问题只剩”能不能放下”的判定，而判定贪心扫一遍即可。

算法实现

二分答案：二分峰值热度上限 。 变大时可用位置只增不减，能放下的方案也只增不减，所以可行性关于 单调。峰值本身就是某个位置的热度，答案必等于某个 ，因此只在 去重排序后的数组 上二分。

check 函数：给定 ，热度大于 的位置一律不能被覆盖，从左到右扫描：

1. 维护当前连续可用的位置数 ，遇到 时 清零。
2. 恰好等于当前笔记长度 时立刻放下这一篇，令 、。
3. 篇全部放下返回可行，扫完仍没放完返回不可行。

贪心的依据：对任意合法方案归纳，设贪心第 篇结束于 、该方案结束于 ，且 。方案的第 篇占的 个位置都在 之后，自然也在 之后，所以贪心不晚于方案就能凑够这 个位置。于是贪心放不下，就说明任何方案都放不下。

放下后 直接清零、不留空位，因为条件 允许两篇紧挨。样例第二组取 时，第二、三篇必须紧挨着放在位置 ；误以为要隔一个空位会判不可行，输出 。

二分过程：

1. 若 check 可行，答案不超过 ，令 。
2. 否则 太小，令 。

输出： 时输出 。题目保证 ， 取最大值时所有位置可用、紧挨着放必能放下，二分右端一定可行。

复杂度分析

时间复杂度：。排序去重 ；二分约 轮，每轮 check 扫一遍 。逐个尝试 在 时达 次，二分降到约 次。

空间复杂度：，存 与去重后的 。

题解代码

import sys
input = sys.stdin.readline

def can_place(a, b, x):
    m = len(b)
    k = 0          # 下一篇要放的笔记编号
    need = b[0]    # 这一篇需要的连续位置数
    run = 0        # 当前连续热度 <= x 的位置数
    for v in a:
        if v > x:
            run = 0
            continue
        run += 1
        if run == need:
            k += 1
            if k == m:
                return True
            need = b[k]
            run = 0
    return False

def min_peak(a, b):
    vals = sorted(set(a))
    lo, hi = 0, len(vals) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if can_place(a, b, vals[mid]):
            hi = mid
        else:
            lo = mid + 1
    return vals[lo]

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(min_peak(a, b))

正确性说明

对笔记编号归纳，贪心每篇的结束位置都不晚于任意可行方案：上一篇更早结束不会减少下一篇可用位置。因此贪心失败当且仅当不存在可行方案。阈值变大只增加可用位置，二分得到最小可行阈值。

易错点与边界

两篇笔记可以相邻，不要求额外空位；越过不可用位置后连续可用长度清零。

小结

优先从题面约束提炼模型，再用样例检查边界。本文保留题面数学符号的原始 SVG，代码统一为 Python 3；未给出的评测限制或规则不补作事实。