大厂真题 / 科大讯飞

科大讯飞 2026-8-23 笔试真题 - 算法岗

本场考试概述

考试时间：2026 年 8 月 23 日

考试岗位：算法岗

难度评级：中等

考点分析：

第 1 题：计数、独立事件、几何分布期望（中等）
第 2 题：哈希计数、互补数配对（中等）
第 3 题：堆优化 Dijkstra、按行程模拟（中等偏难）

第 1 题：骰子好运的期望轮数

题目描述

有一个 $n$ 面骰子，每个面写有一个数字，且各个面朝上的概率相同。

每轮独立抛两次骰子。只有第一次朝上的数字为 $a$，并且第二次朝上的数字为 $b$，这一轮才算得到好运。不断进行游戏，直到第一次得到好运时停止，求所需轮数的期望。

输入描述

第一行输入三个整数 $n,a,b$，分别表示骰子面数和两个目标数字。

第二行输入 $n$ 个非负整数 $x_1,x_2,\ldots,x_n$，表示各个面上的数字。

题目保证 $a\ne b$，并且 $a,b$ 都至少出现一次。

输出描述

输出期望轮数，保留一位小数。

样例 1

输入

3 8 5
8 5 5

输出

4.5

解释

数字 $8$ 出现在 $1$ 个面，数字 $5$ 出现在 $2$ 个面。一轮成功的概率为

\[\frac{1}{3}\times\frac{2}{3}=\frac{2}{9},\]

因此期望轮数为 $9/2=4.5$。

样例 2

输入

4 0 1
0 0 1 1

输出

4.0

思路分析

设数字 $a$ 和 $b$ 分别出现在 $c_a$、$c_b$ 个面上。两次抛掷相互独立，所以一轮成功的概率为

\[p=\frac{c_a}{n}\cdot\frac{c_b}{n} =\frac{c_ac_b}{n^2}.\]

各轮也独立同分布，首次成功的轮数服从参数为 $p$ 的几何分布。

若其期望为 $E$，考察第一轮：成功时游戏立即结束；失败时已经用掉一轮，之后面对的状态与游戏开始时完全相同。因此也可以写成

\[E=1+(1-p)E.\]

移项可得

\[E=\frac{1}{p}=\frac{n^2}{c_ac_b}.\]

只需扫描骰子各面，统计两个目标数字的出现次数，再代入公式。

正确性证明

引理 1：算法计算的一轮成功概率为真实概率。

证明：第一次抛出 $a$ 的概率为 $c_a/n$，第二次抛出 $b$ 的概率为 $c_b/n$。两次抛掷独立，所以二者同时发生的概率是两者乘积，即 $c_ac_b/n^2$。

引理 2：若每轮成功概率为 $p$，首次成功所需轮数的期望为 $1/p$。

证明：无论第一轮结果如何都先消耗一轮；若第一轮失败，概率为 $1-p$，之后仍需期望 $E$ 轮。故 $E=1+(1-p)E$，解得 $E=1/p$。

定理：算法输出首次得到好运所需轮数的正确期望。

证明：由引理 1，算法得到正确的单轮成功概率；由引理 2，其倒数就是所求期望。代码输出 $n^2/(c_ac_b)$，因此答案正确。

ACM Python 代码

import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, a, b = data[:3]
    faces = data[3:3 + n]

    count_a = sum(value == a for value in faces)
    count_b = sum(value == b for value in faces)

    expectation = n * n / (count_a * count_b)
    print(f"{expectation:.1f}")


if __name__ == "__main__":
    solve()

复杂度分析

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

空间复杂度：$O(n)$（按当前代码一次读入全部输入）；若逐个读取并计数，可降为 $O(1)$ 额外空间。

易错点

成功概率必须按目标数字出现的面数计算，不能把两个目标数字直接视为等概率。
结果要求保留一位小数，按期望公式直接计算，避免用随机模拟造成误差。

第 2 题：拆除炸弹的最少按钮次数

题目描述

炸弹控制器上有 $n$ 个按钮，每个按钮写有一个自然数。每个按钮有触发和非触发两种状态，按一次按钮会切换其状态。初始时所有按钮都处于触发状态。

倒计时结束时，如果存在两个不同的、仍处于触发状态的按钮，并且它们的数字之和恰好为 $k$，炸弹就会爆炸。

求至少需要按多少次按钮，才能保证炸弹不爆炸。

输入描述

第一行输入两个正整数 $n,k$。

第二行输入 $n$ 个自然数 $a_1,a_2,\ldots,a_n$，表示各按钮上的数字。

输出描述

输出防止炸弹爆炸所需的最少按键次数。

样例 1

输入

1 8
6

输出

样例 2

输入

6 12
4 8 5 7 4 1

输出

解释

数值 $4$ 与 $8$ 互补，关闭唯一的 $8$ 代价为 $1$；数值 $5$ 与 $7$ 互补，再关闭其中任意一个代价为 $1$。共按 $2$ 次。

样例 3

输入

4 14
7 7 7 3

输出

解释

任意两个数值为 $7$ 的按钮都会凑出 $14$，因此最多保留一个，必须关闭两个。

思路分析

按按钮上的数值分组，记 cnt[x] 为数值 $x$ 的按钮个数。数值 $x$ 只会与 $k-x$ 产生冲突，不同互补数对之间互不影响。

对于一个无序互补组，有两种情况：

$x\ne k-x$：如果两组中都保留按钮，就一定能选出一对使数字和为 $k$。所以必须关闭其中完整的一组，最小代价为
\[\min(\operatorname{cnt}[x],\operatorname{cnt}[k-x]).\]
$x=k-x$：即 $2x=k$。同组中只要留下至少两个按钮就会爆炸，所以最多保留一个，最小代价为
\[\operatorname{cnt}[x]-1.\]

若补数 $k-x$ 没有出现，则该组没有冲突，不需要操作。

遍历哈希表时，只在 $x<k-x$ 时处理普通互补对，防止同一个无序对被计算两次；自配对组单独处理。

同一个按钮按两次会回到触发状态，因此最优方案不会对任何按钮按超过一次，问题等价于最少关闭多少个按钮。

正确性证明

引理 1：对于 $x\ne k-x$ 的互补组，最少需要关闭 $\min(\operatorname{cnt}[x],\operatorname{cnt}[k-x])$ 个按钮。

证明：若两侧各留下至少一个按钮，二者之和就是 $k$，仍会爆炸，所以任意可行方案必须关空一侧。关空两侧的代价分别是两侧出现次数，选择较小者可行且最优。

引理 2：对于 $2x=k$ 的自配对组，最少需要关闭 $\operatorname{cnt}[x]-1$ 个按钮。

证明：留下两个或更多数值为 $x$ 的按钮时，可选出两个不同按钮且和为 $k$，所以至多留一个；关闭其余按钮即可消除全部冲突，代价恰为 $\operatorname{cnt}[x]-1$。

引理 3：不同无序互补组可以独立求解。

证明：一个数值 $x$ 的冲突对象唯一是 $k-x$，不会与其他数值组产生冲突。因此对某组按钮的选择不影响其他组的可行性。

定理：算法得到防止炸弹爆炸的最少按键次数。

证明：由引理 1 和引理 2，算法对每个互补组取到最小代价；由引理 3，各组最优代价可以直接相加。遍历条件保证每组恰好计算一次，所以总和即全局最优答案。

ACM Python 代码

import sys
from collections import Counter


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, target = data[:2]
    values = data[2:2 + n]
    count = Counter(values)

    answer = 0
    for value, frequency in count.items():
        other = target - value
        if other not in count:
            continue

        if value == other:
            answer += frequency - 1
        elif value < other:
            answer += min(frequency, count[other])

    print(answer)


if __name__ == "__main__":
    solve()

复杂度分析

设不同数字的数量为 $d$。

时间复杂度：期望 $O(n+d)$，即期望 $O(n)$。

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

易错点

当某个数字与自身互补时，只需将该数的炸弹全部关闭一次，不能重复计数。
对不同的互补数对只处理一次，否则会把同一对的代价计算两遍。

第 3 题：快递配送的总耗时

题目描述

有 $n$ 个乡村，编号为 $1$ 到 $n$。快递站位于乡村 $s$。乡村之间有 $m$ 条单向道路和 $k$ 条双向道路，每条道路都有非负耗时。任意两个乡村均可相互到达，且可能有重边和自环。

快递员从快递站出发，按照给定顺序配送 $q$ 件快递，每一段都走耗时最短的路径。

到达第 $i$ 件快递的目的地后，先把本次行驶耗时计入总耗时：

如果此时累计耗时为奇数，则通知收货人当面取件，额外耗时 $a$；
如果此时累计耗时为偶数，则将快递放入快递柜，额外耗时 $b$。

注意，本件快递的投递耗时不参与本件投递方式的奇偶判断，但会影响之后的累计耗时。

全部配送完成后，还要从最后一个目的地按最短路径返回快递站。求最终总耗时。

输入描述

第一行输入四个整数 $n,m,k,s$，分别表示乡村数、单向道路数、双向道路数和快递站编号。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条从 $u$ 到 $v$、耗时为 $w$ 的单向道路。

再接下来 $k$ 行，每行三个整数 $u,v,w$，表示一条连接 $u,v$、两个方向耗时均为 $w$ 的双向道路。

下一行输入三个整数 $a,b,q$，分别表示当面取件耗时、放入快递柜耗时和快递数量。

最后一行输入 $q$ 个整数 $d_1,d_2,\ldots,d_q$，表示各件快递的目的地顺序。

输出描述

输出配送全部快递并返回快递站后的总耗时。

样例 1

输入

输出

解释

起点与第一件目的地都是 $1$，行驶耗时为 $0$，当前累计耗时为偶数，加快递柜耗时 $3$。随后 $1\to2$ 最短耗时为 $3$，累计为 $6$，再加 $3$；$2\to3$ 最短耗时为 $6$，累计为 $15$，再加当面取件耗时 $6$；最后 $3\to1$ 最短耗时为 $9$，总计 $30$。

样例 2

输入

输出

样例 3

输入

输出

思路分析

把每条双向道路拆成两条方向相反、权值相同的有向边，得到统一的有向图。

完整行程为

\[s\to d_1\to d_2\to\cdots\to d_q\to s.\]

只需要这些相邻站点之间的最短距离。每一段的起点一定属于集合

\[\{s,d_1,d_2,\ldots,d_q\}.\]

因此，对这个集合中的每个不同节点运行一次堆优化 Dijkstra，并保存其到所有节点的最短距离即可。配送点数量很少时，这比 Floyd 全源最短路更合适。

随后按顺序模拟：

从当前位置到本件目的地，加上最短行驶耗时；
检查此刻累计耗时的奇偶性，奇数加 $a$，偶数加 $b$；
更新当前位置。

所有快递送完后，再加当前位置返回 $s$ 的最短距离。

目的地与当前位置相同时，行驶距离为 $0$，但仍然要完成一次投递并进行奇偶判断。自环和重边不需要特殊处理，Dijkstra 的松弛操作会自然取到最短路径。

正确性证明

引理 1：每次 Dijkstra 得到指定源点到所有乡村的正确最短耗时。

证明：图中边权非负，满足 Dijkstra 算法的适用条件。堆优化只改变取出当前最小距离节点的实现方式，不改变标准 Dijkstra 的松弛过程，故结果正确。

引理 2：预处理的距离覆盖完整行程所需的每一段。

证明：每段行程起点只能是快递站 $s$ 或某个已配送目的地 $d_i$，这些节点全部在预处理源点集合中；终点是下一个目的地或最后的快递站。因此每一段所需距离都能从相应源点的距离数组中取得。

引理 3：模拟过程中每完成一件快递后，累计耗时与题意一致。

证明：算法先加入当前位置到目的地的最短耗时，此时恰为题目规定的奇偶判断时刻。之后根据该值，奇数加入 $a$、偶数加入 $b$，再更新位置，顺序与题意完全一致。按配送顺序归纳，每件完成后的累计值均正确。

定理：算法输出配送全部快递并返回快递站的正确总耗时。

证明：由引理 1 和引理 2，模拟使用的每段行驶耗时均为正确最短距离；由引理 3，全部配送与投递耗时被按正确顺序累计。最后加入返回快递站的最短耗时，故输出即题目要求的总耗时。

ACM Python 代码

import heapq
import sys


INF = float("inf")


def dijkstra(graph, source):
    distance = [INF] * len(graph)
    distance[source] = 0
    heap = [(0, source)]

    while heap:
        current_distance, node = heapq.heappop(heap)
        if current_distance != distance[node]:
            continue

        for next_node, weight in graph[node]:
            new_distance = current_distance + weight
            if new_distance < distance[next_node]:
                distance[next_node] = new_distance
                heapq.heappush(heap, (new_distance, next_node))

    return distance


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)

    n = next(iterator)
    directed_count = next(iterator)
    undirected_count = next(iterator)
    station = next(iterator)

    graph = [[] for _ in range(n + 1)]

    for _ in range(directed_count):
        u = next(iterator)
        v = next(iterator)
        weight = next(iterator)
        graph[u].append((v, weight))

    for _ in range(undirected_count):
        u = next(iterator)
        v = next(iterator)
        weight = next(iterator)
        graph[u].append((v, weight))
        graph[v].append((u, weight))

    hand_time = next(iterator)
    locker_time = next(iterator)
    delivery_count = next(iterator)
    destinations = [next(iterator) for _ in range(delivery_count)]

    useful_sources = set([station] + destinations)
    distances = {
        source: dijkstra(graph, source)
        for source in useful_sources
    }

    total_time = 0
    current = station

    for destination in destinations:
        total_time += distances[current][destination]
        if total_time % 2 == 1:
            total_time += hand_time
        else:
            total_time += locker_time
        current = destination

    total_time += distances[current][station]
    print(total_time)


if __name__ == "__main__":
    solve()

复杂度分析

设将双向边拆开后有向边总数为 $E=m+2k$，不同的有效源点数为

\[r=\left\lvert\{s,d_1,d_2,\ldots,d_q\}\right\rvert\le q+1.\]

时间复杂度：$O\bigl(r(n+E)\log n+q\bigr)$。

空间复杂度：$O(E+n+rn)$，分别用于邻接表、Dijkstra 工作数组和保存各有效源点的距离。

易错点

必须按配送顺序逐段累加时间，并在到达目的地后依据当前累计时间的奇偶性选择交付耗时。
最后一件快递交付后仍需返回快递站，不能漏掉返程最短路。
仅需从快递站和各目的地这些有效源点运行 Dijkstra，无须计算全源最短路。

这篇文章有帮助吗？

| GitHub 留言