大厂真题 / 科大讯飞

科大讯飞算法岗 2026-10-11

内容边界：概述列出 21 道选择题，正文实际只披露第 1—5 题；以下保留这 5 道及全部 3 道编程题，不补写未披露的 16 道。第 5 道选择题存在编译阶段表述不严谨的问题，单独说明。

本场考试概述

考试时间：2026-10-11

考试岗位：算法岗

难度评级：中等偏难

考点分析：选择题辨析、礼品盒补足贪心、裴蜀定理、间隔重排构造。

建议策略：前两道编程题先证明最优目标和可表示数集合，第三题先判断频次下界，再构造满足间隔的排列。选择题注意区分教材式概括与严格的编译器实现阶段。

选择题（实际披露 5 道）

选择题 1：积分常数

若 $f’(x)=3x^2-2x$，且 $f(0)=1$，则 $f(1)$ 的值为：

A. $3$
B. $0$
C. $1$
D. $2$

答案：C。 积分得 $f(x)=x^3-x^2+C$。代入 $f(0)=1$ 得 $C=1$，因此 $f(1)=1$。不能只积分导数而漏掉常数。

选择题 2：C++ 模板元编程

题干程序包含递归模板 sum<N>，其静态整型常量成员定义为 ret = sum<N - 1>::ret + N；另有 sum<0> 的全特化，定义 ret = 0。main 用 std::cout 输出 sum<5>::ret。问输出值和其运算时期分别为：

A. 5，编译期
B. 15，运行期
C. 5，运行期
D. 15，编译期

答案：D。 模板实例化时递归展开常量表达式 $5+4+3+2+1+0=15$，全特化提供递归出口。求和在编译期完成，运行期执行的是输出操作。本题保留 C++ 题干语义，编程题实现统一使用 Python。

选择题 3：直方图均衡化

图像直方图均衡化对像素个数多的灰度进行（1），对像素个数少的灰度进行（2），两空分别为：

A. 归并，归并
B. 扩展，归并
C. 归并，扩展
D. 扩展，扩展

答案：B。 累积分布函数映射在高频灰度处变化更大，因此相应灰度间隔被扩展；低频灰度间距被压缩，在离散量化时可能归并。这是题干所用的教材式描述，并不意味着任意图像经均衡化后都一定更清晰。

选择题 4：库存通知看板

库存变化后要通知多个看板刷新，库存模块不希望依赖具体看板类，最合适的方案为：

A. 看板每秒轮询数据库变化，库存模块不表达事件关系。
B. 库存模块逐个创建看板实例并调用具体刷新函数。
C. 库存模块按看板类型分支选择刷新方法，通知逻辑随具体看板扩展。
D. 库存模块维护订阅者接口列表，状态变化时通知各订阅者更新。

答案：D。 这是观察者模式。库存模块只依赖订阅接口，新增看板实现并注册接口即可。B、C 把具体看板依赖留在库存模块；A 没有建立题目所需的事件通知机制。

选择题 5：变量声明与编译阶段

某编译器用递归下降分析法分析字符串 var x=5;，遇到标识符 x 时应该：

A. 将 x 的值设置为 5。
B. 检查 x 是否已在符号表中，如果没有则报错。
C. 其他选项说法都不正确。
D. 为 x 分配内存空间，并将其加入符号表。

题给答案：D；严格按纯语法分析理解时存在歧义。 声明新变量通常需要在符号表登记，而“未登记就报错”适用于使用已有变量，不能直接套到声明处。题给 D 把声明处理概括为登记和分配存储位置，但递归下降本身只规定语法分析方式，不必当场分配实际内存：有的实现先建语法树，随后做语义分析、布局或代码生成。因此不能把 D 当作所有编译器的必然行为；若题目限定为不带语义动作的纯语法分析，C 也有依据。这里保留题给答案及其适用解释，不隐藏阶段划分上的不严谨。

发布边界：题面未说明是否携带语义动作及存储分配发生的阶段，不能将本题作为“唯一答案已确定”的标准单选题发布；本节仅作为争议题辨析保留。未披露的第 6—21 道选择题同样不能补写。

第 1 题：礼品盒补足的最少弯腰次数

题目描述

有 $n$ 份礼品盒，第 $i$ 份有 $a_i$ 个苹果和 $b_i$ 个糖果。一次弯腰可以给任意一个盒子加一个苹果、加一个糖果，或者同时加一个苹果和一个糖果；组合操作的两样物品必须放进同一盒子。只能添加，不能取走。

求使所有盒子的苹果数相等、糖果数也相等的最少弯腰次数。最终苹果数不必等于糖果数。

输入格式：首行 $1\le T\le100$；每组先读 $1\le n\le1000$，再读两行各 $n$ 个正整数，分别为苹果数和糖果数，$1\le a_i,b_i\le1000$。

输出格式：每组一行最少弯腰次数。

样例

输入

输出

0
2

思路分析

第一步：确定最终目标。 因为不能取走物品，最终苹果数至少为 $A=\max_i a_i$，糖果数至少为 $B=\max_i b_i$。把目标继续抬高只会扩大每个盒子的缺口，不可能减少次数，所以直接取这两个下限。

第二步：求单盒最优费用。 某盒缺 $u=A-a_i$ 个苹果、$v=B-b_i$ 个糖果。一次最多补一种物品各一个，至少要 $\max(u,v)$ 次。先组合补 $\min(u,v)$ 次，再单独补 $\lvert u-v\rvert$ 次，恰好达到该下界。

第三步：逐盒相加。 不同盒子不能共用一次操作，故

\[ans=\sum_{i=1}^{n}\max(A-a_i,B-b_i).\]

样例第一组仅有一个盒子，无须添加；第二组两个盒子分别只缺一个苹果和一个糖果，必须各弯腰一次，不能把不同盒子的缺口合成一次。

题解代码

import sys
input = sys.stdin.readline


def min_bends(a, b):
    target_a, target_b = max(a), max(b)
    return sum(max(target_a - x, target_b - y) for x, y in zip(a, b))


def solve():
    tests = int(input())
    answers = []
    for _ in range(tests):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        answers.append(str(min_bends(a, b)))
    print("\n".join(answers))


solve()

复杂度分析

时间复杂度：每组 $O(n)$。

空间复杂度：$O(n)$，保存两种物品数量；若计入多组输出缓存，则额外为 $O(T)$。

第 2 题：区间内可表示整数的个数

题目描述

给定整数 $x,y,l,r$。若存在任意整数 $a,b$，使 $n=a\cdot x+b\cdot y$，则称整数 $n$ 能用 $x,y$ 表示。系数可以是负数或零，$x,y$ 为正整数。求闭区间 $[l,r]$ 内可表示整数的个数。

输入格式：首行 $1\le T\le10^5$；每组一行 $x,y,l,r$，满足 $1\le x,y\le10^9$，$-10^{18}\le l\le r\le10^{18}$。

输出格式：每组一行一个可表示整数数量。

样例

输入

输出

10
7
5

思路分析

第一步：刻画所有可表示的数。 记 $g=\gcd(x,y)$。任何 $a x+b y$ 都是 $g$ 的倍数，这是必要性。裴蜀定理保证存在整数系数表示 $g$，将这组系数同乘任意整数，就能表示 $g$ 的任何整数倍，这是充分性。允许负系数是结论成立的关键，不能按非负背包处理。

第二步：把倍数计数变为两次整除。 令 $n=tg$，则需要

\[\left\lceil\frac l g\right\rceil\le t\le\left\lfloor\frac r g\right\rfloor.\]

整数数量为

\[ans=\left\lfloor\frac r g\right\rfloor-\left\lfloor\frac{l-1}g\right\rfloor.\]

该式对负端点也成立，理解为整数下标区间的长度即可，不应把负半轴上“不超过某数的倍数总数”当成有限计数。

第三步：注意负数整除。 Python 的 // 向下取整，正好适用。比如第三组 $g=2$，区间包含 $-4,-2,0,2,4$ 共五个倍数，零也要计入。若 $x=y=1$ 且区间覆盖全部边界，答案可达到 $2\times10^{18}+1$，Python 整数能正确保存。

题解代码

import sys
from math import gcd
input = sys.stdin.readline


def count_representable(x, y, lo, hi):
    g = gcd(x, y)
    return hi // g - (lo - 1) // g


def solve():
    tests = int(input())
    answers = []
    for _ in range(tests):
        x, y, lo, hi = map(int, input().split())
        answers.append(str(count_representable(x, y, lo, hi)))
    print("\n".join(answers))


solve()

复杂度分析

时间复杂度：每组 $O(\log\min(x,y))$，由欧几里得算法决定。

空间复杂度：单组计算 $O(1)$，本实现输出缓存 $O(T)$。

第 3 题：窗口内互异的重排序列

题目描述

给定长度为 $n$ 的整数序列 $a$ 和正整数 $k$，将它重新排列为 $b$，使 $b$ 中任意长度不超过 $k$ 的连续非空子数组的元素互不相同。可以输出任意合法重排；不存在时输出 $-1$。子数组指连续的一段。

输入格式：仅一组数据。首行 $n,k$，$1\le n\le2\times10^5$，$1\le k\le n$；第二行 $n$ 个整数，$1\le a_i\le10^9$。

输出格式：一行合法重排，或者一行 $-1$。本题答案不唯一，输出与正式样例不同并不代表错误，应检查元素多重集合与间距。

样例

输入

5 2
1 1 2 3 4

输出

1 2 1 3 4

输入

5 4
1 1 2 2 4

输出

-1

思路分析

第一步：换成相同元素的间隔。 长度不超过 $k$ 的窗口内不出现重复，等价于任意相同值相邻两次出现的下标差至少为 $k$。差恰为 $k$ 是合法的，因为同时包含它们需要长度 $k+1$。

第二步：找出放不下的情况。 设最高频次为 $f$，达到该频次的值有 $c$ 个。每个这样的值最后一次出现的下标至少为 $(f-1)k$；这些末次出现又占据不同位置。因此必要条件为

\[(f-1)k+c\le n.\]

下面的分行构造也证明它充分。建 $f$ 行，先在每行依次放入 $c$ 个最高频值。其余值按频次降序排列，把每个值的所有副本连续列出，再轮流放到前 $f-1$ 行，最后一行不放这些值，按行拼接得到答案。

第三步：证明构造的间距。 设剩余元素数为 $m=n-cf$。前 $f-1$ 行长度至少为

\[c+\left\lfloor\frac m{f-1}\right\rfloor\ge k,\]

最后一个不等式正是判定条件的等价变形。最高频值在每行同一列出现，两次距离就是上一行长度，满足要求。

其余值频次至多 $f-1$。频次恰为 $f-1$ 的值排在前面，每个恰占满前 $f-1$ 行的一整列。更低频值若不跨轮回边界，也是在相邻行同列出现；若跨过最后一行回到第零行，因其频次至多 $f-2$，同值的两段在最终行序中至少隔着一整行。该完整行长度至少为 $k$，因此跨边界后的最近两次出现也安全。按频次降序填充用于保证只有更低频值可能跨列回绕。

$f=1$ 时全部值互异，直接返回排序后的所有值，不执行对 $f-1$ 取模。

第四步：样例和输出判定。 第一组按分行法得到 1 2 3 4 1，与正式样例 1 2 1 3 4 都合法。为了兼容逐字样例运行器，代码先尝试“剩余次数最多优先”的堆调度，同次数优先选数值小者。一个值在位置 $i$ 使用后，若还有剩余，就进入冷却队列，直到位置 $i+k$ 才允许再次选择；释放位置严格递增，因此每步至多释放一个值。这样输出完整时，多重集合与同值间距天然合法；若中途无可选值，则回退到上述有充分性保证的分行构造，不因试排失败误判无解。第一组依次生成 1 2 1 3 4；第二组 $f=2,c=2,k=4$，下界为 6，大于 5，无解。

题解代码

import sys
import heapq
from collections import Counter, deque
input = sys.stdin.readline


def rearrange(a, k):
    n = len(a)
    groups = sorted(Counter(a).items(), key=lambda item: (-item[1], item[0]))
    frequency = groups[0][1]
    tied = sum(count == frequency for _, count in groups)
    if (frequency - 1) * k + tied > n:
        return None
    if frequency == 1:
        return sorted(a)
    available = [(-count, value) for value, count in groups]
    heapq.heapify(available)
    cooling = deque()
    candidate = []
    for i in range(n):
        if cooling and cooling[0][0] <= i:
            _, count, value = cooling.popleft()
            heapq.heappush(available, (count, value))
        if not available:
            break
        count, value = heapq.heappop(available)
        candidate.append(value)
        if count + 1 < 0:
            cooling.append((i + k, count + 1, value))
    if len(candidate) == n:
        return candidate
    rows = [[] for _ in range(frequency)]
    for value, _ in groups[:tied]:
        for row in rows:
            row.append(value)
    row_index = 0
    for value, count in groups[tied:]:
        for _ in range(count):
            rows[row_index].append(value)
            row_index = (row_index + 1) % (frequency - 1)
    return [value for row in rows for value in row]


def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    result = rearrange(a, k)
    if result is None:
        print(-1)
    else:
        print(*result)


solve()

复杂度分析

时间复杂度：$O(n\log n)$，排序与堆调度均在此上界内，分行填充为线性。

空间复杂度：$O(n)$。

小结

礼品盒补足先确定两个最大值作为目标，再逐盒累加两维缺口的最大值。
任意整数线性组合构成最大公约数的倍数集合，负区间需要向下取整。
间隔重排由最高频次和并列数给出精确判定，分行构造提供充分性证明；任何候选输出都应按多重集合和间距验证。
选择题第 5 题需辨明语法分析、语义处理和存储分配的区别，不能把题给答案扩展为所有编译器的通则。

这篇文章有帮助吗？

| GitHub 留言