大厂真题 / 阿里巴巴

阿里 5.23 笔试真题 - 算法岗

本场考试概述

考试时间：2026年5月23日 考试岗位：算法岗（暑期实习/春招） 难度评级：中等偏难

考点分析：

1. 第一题：贪心算法 + 排序（难度简单）
2. 第二题：哈希表 + 前缀计数（难度中等）
3. 第三题：二分答案 + 质因数分解 + 哈希 DP（难度困难）

建议策略：

1. 贪心题先想清楚”为什么这样排序”，写出第 $j$ 次成功的代价表达式即可一目了然
2. 多约束统计题先固定一个端点（$j$），把剩余约束转成前缀查询，再用哈希表加速
3. 最小化最大值类题目套二分答案模板，check 函数往往就是一个 $O(n)$ 或 $O(n \log n)$ 的可行性判断
4. $10^9$ 范围下试除分解过慢，Miller-Rabin + Pollard-Rho 是高频组合，建议背熟模板

第一题：荆棘林的最优砍断计划

题目描述

林中共有 $n$ 株荆棘，第 $i$ 株的坚硬度为 $a_i$，宝刀的初始锋利度为 $K$。可以选择任意数量的荆棘，每株至多尝试一次，并以任意顺序依次尝试砍断。每次尝试遵循以下规则：

• 若当前锋利度 $S$ 满足 $S \geq a_i$，则该荆棘被成功砍断
• 无论成功与否，每次尝试结束后锋利度 $S$ 都会永久减少 $1$

可以放弃任意荆棘（放弃不消耗锋利度）。请计算在最优策略下，最多能成功砍断多少株荆棘。

多组测试数据，第一行 $T$；每组第一行 $n, K$，第二行 $n$ 个整数 $a_i$。保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

样例

输入

3
5 5
2 1 4 10 3
2 1
10 10
3 3
3 3 3

输出

4
0
1

思路分析

第一步：识别最优策略的核心性质

失败的尝试只会让锋利度减少 $1$ 而无收益，因此最优策略不会主动尝试注定失败的荆棘。问题等价于：从 $n$ 株里选若干株并安排顺序，使每次砍断时锋利度都够。

第二步：推导代价表达式

假设最终成功砍断 $m$ 株，按尝试顺序排成 $b_1, b_2, \ldots, b_m$。由于只有成功的尝试才会真正发生（最优策略下不做失败尝试），第 $j$ 次成功时锋利度为 $K - (j-1)$。要求：

$j$ 越大，可承受的坚硬度越小。把序列按 $b_j$ 从大到小排列，约束最容易满足。

第三步：贪心策略

所有荆棘按坚硬度从大到小排序。维护已成功次数 $\text{cnt}$，逐个考察当前荆棘 $x$：

• 若 $K - \text{cnt} \geq x$，则砍断，$\text{cnt}$ 加 $1$
• 否则跳过（不消耗锋利度）

正确性分析：

• 跳过情况：当前最硬的荆棘砍不动，未来 $\text{cnt}$ 只增不减、锋利度只降不升，这株以后更砍不动。跳过没有损失。
• 砍断情况：当前能砍就立刻砍，不会比留到后面更差——两种顺序下成功次数都加 $1$，且剩下荆棘更软，对后续不构成负担。

样例演示：$K = 5$，排序后为 $[10, 4, 3, 2, 1]$。

• $x = 10$，锋利度 $5 < 10$，跳过
• $x = 4$，锋利度 $5 \geq 4$，砍，$\text{cnt} = 1$
• $x = 3$，锋利度 $4 \geq 3$，砍，$\text{cnt} = 2$
• $x = 2$，锋利度 $3 \geq 2$，砍，$\text{cnt} = 3$
• $x = 1$，锋利度 $2 \geq 1$，砍，$\text{cnt} = 4$

答案 $4$。

题解代码

import sys

data = sys.stdin.buffer.read().split()
idx = 0
T = int(data[idx]); idx += 1
out = []
for _ in range(T):
    n = int(data[idx]); K = int(data[idx + 1]); idx += 2
    a = [int(x) for x in data[idx:idx + n]]; idx += n
    # 从大到小排序：能砍则砍，从硬到软贪心保证成功次数最大
    a.sort(reverse=True)
    cnt = 0
    for x in a:
        # 当前锋利度 = K - 已成功次数；够则砍断
        if K - cnt >= x:
            cnt += 1
        # 不够直接跳过：失败的尝试只会白白消耗锋利度
    out.append(str(cnt))
sys.stdout.write("\n".join(out))

复杂度分析

时间复杂度：$O(n \log n)$，每组数据排序 $O(n \log n)$，线性扫描 $O(n)$。 空间复杂度：$O(n)$，存放当前组的坚硬度数组。

第二题：多约束条件下的元素匹配统计

题目描述

给定三个长度为 $n$ 的数组 $a$、$b$ 和 $c$。其中 $c_j$ 表示对数组 $b$ 的一个下标（1-based）。

请统计满足以下条件的有序对 $(i, j)$ 的数量：

• $i \leq j$
• $a_i = b_{c_j}$

多组测试数据，第一行 $T$；每组第一行 $n$，接下来三行分别是 $a$、$b$、$c$。保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$。

样例

输入

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

输出

5
6

思路分析

第一步：暴力分析瓶颈

直接枚举所有 $(i, j)$ 对需要 $O(n^2)$，$n$ 可达 $2 \times 10^5$，无法承受。

第二步：固定右端点转前缀查询

固定右端点 $j$ 后，条件简化为：在 $[1, j]$ 这段前缀里，$a_i$ 等于 $b_{c_j}$ 的元素有几个。前缀的频次用哈希表维护即可单次 $O(1)$ 查询。

第三步：算法流程

• 哈希表 $\text{cnt}$ 记录已遍历前缀里每个 $a$ 值的出现次数，初始为空，答案 $\text{ans} = 0$
• 从左到右枚举 $j$：先把 $a_j$ 计入前缀（此时哈希表恰好覆盖 $[1, j]$，包含 $j$ 自身，因为题目允许 $i = j$）
• 当前 $j$ 的目标值 $\text{target} = b_{c_j - 1}$（0-based），满足 $i \leq j$ 且 $a_i = \text{target}$ 的个数等于 $\text{cnt}[\text{target}]$，直接加入答案

样例演示（第一组）：$a = [1,2,1,2,1]$，$b = [2,1,3,1,2]$，$c = [2,1,5,4,3]$。

• $j=0$：$\text{cnt}[1]=1$，目标 $b[1]=1$，加 $1$
• $j=1$：$\text{cnt}[2]=1$，目标 $b[0]=2$，加 $1$
• $j=2$：$\text{cnt}[1]=2$，目标 $b[4]=2$，$\text{cnt}[2]=1$，加 $1$
• $j=3$：$\text{cnt}[2]=2$，目标 $b[3]=1$，$\text{cnt}[1]=2$，加 $2$
• $j=4$：$\text{cnt}[1]=3$，目标 $b[2]=3$，$\text{cnt}[3]=0$，加 $0$

总计 $5$。

题解代码

import sys
from collections import defaultdict

data = sys.stdin.buffer.read().split()
idx = 0
T = int(data[idx]); idx += 1
out = []
for _ in range(T):
    n = int(data[idx]); idx += 1
    a = [int(x) for x in data[idx:idx + n]]; idx += n
    b = [int(x) for x in data[idx:idx + n]]; idx += n
    c = [int(x) for x in data[idx:idx + n]]; idx += n
    cnt = defaultdict(int)
    ans = 0
    # 从左到右枚举 j，先把 a[j] 计入前缀，再查 b[c[j]-1] 出现了多少次
    for j in range(n):
        cnt[a[j]] += 1
        # c 是 1-based 下标，访问 b 前要减 1
        ans += cnt[b[c[j] - 1]]
    out.append(str(ans))
sys.stdout.write("\n".join(out))

复杂度分析

时间复杂度：$O(n)$，每组数据线性扫描，哈希插入和查询均摊 $O(1)$。 空间复杂度：$O(n)$，哈希表存放数组 $a$ 中的不同值。

第三题：寻找满足条件的最优子序列

题目描述

给定长度为 $n$ 的数组 $a$，想选出一个长度为 $k$ 的子序列。所选子序列需满足相邻两个元素的 $\gcd$ 不为 $1$。具体地，若选取下标序列 $i_1 < i_2 < \cdots < i_k$，则需要满足对所有 $1 \leq t < k$，$\gcd(a_{i_t}, a_{i_{t+1}}) > 1$。

在所有满足上述条件的子序列中，求最大元素的最小可能取值。如果不存在满足条件的子序列，则输出 $-1$。

第一行 $n, k$；第二行 $n$ 个整数 $a_i$（$2 \leq a_i \leq 10^9$）。

样例

输入

5 3
2 4 3 9 6

输出

6

样例解释：可选下标 $1, 2, 5$ 对应元素 $[2, 4, 6]$，此时 $\gcd(2,4)=2 > 1$，$\gcd(4,6)=2 > 1$，最大值为 $6$。可知没有更小的最大值，因此输出 $6$。

输入

5 2
5 7 11 13 17

输出

-1

样例解释：数组中任意两个元素的 $\gcd$ 均为 $1$，无法选出符合条件的子序列。

思路分析

第一步：二分答案框架

要求最大元素的最小可能取值，答案随取值上限单调可行（上限越大，能用的元素越多，越容易凑够长度 $k$），可以二分这个上限。

验证时只考虑值不超过上限的元素，问题变为：带 $\gcd > 1$ 邻接约束的最长子序列长度是否 $\geq k$。

第二步：GCD > 1 的等价刻画

两数 $\gcd > 1$ 当且仅当它们至少共享一个质因子。把每个 $a_i$ 拆成不同质因子集合后，相邻元素可连接的条件就变成两个质因子集合有交集。

第三步：哈希 DP 的 check 函数

设 $\text{best}[p]$ 表示在已处理元素中，含质因子 $p$ 且值不超过当前阈值的、以某个含 $p$ 的元素结尾的最长合法子序列长度。

从左到右遍历下标 $i$：

1. 若 $a_i > \text{limit}$ 则跳过
2. 否则当前元素至少自成长度 $1$，并尝试接到含共享质因子的最优前驱后面：$\text{cur} = 1 + \max_{p \in \text{primes}(a_i)} \text{best}[p]$
3. 若 $\text{cur} \geq k$，立即返回可行
4. 处理完后用 $\text{cur}$ 反向更新 $a_i$ 的所有质因子

第四步：质因数分解

$a_i$ 可达 $10^9$，试除法最坏需 $O(\sqrt{a_i}) \approx 31623$ 次除法。对于本题 $n \leq 10^5$，试除法总开销约 $3 \times 10^9$，在 Python 中可能超时。使用 Miller-Rabin 判素 + Pollard-Rho 分解，单次期望 $O(n^{1/4})$，实测更快。

第五步：二分过程

候选答案只能是数组中出现过的值（去重排序得到 $\text{vals}$）。先用最大值验证可行性，不行直接输出 $-1$。否则在 $\text{vals}$ 上做二分搜索找最小可行阈值。

特判：$k = 1$ 时单元素自然合法，直接返回数组最小值。

题解代码

import sys
import math
from random import seed as _seed, randint as _randint

_seed(20240523)

def is_prime(n):
    """Miller-Rabin 判素，1e9 范围内用小质数底即可确定性判定。"""
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        ok = False
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                ok = True
                break
        if not ok:
            return False
    return True

def pollard_rho(n):
    """Pollard-Rho：返回合数 n 的一个非平凡因子。"""
    if n % 2 == 0:
        return 2
    while True:
        x = _randint(2, n - 1)
        y = x
        c = _randint(1, n - 1)
        d = 1
        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n
            d = math.gcd(abs(x - y), n)
        if d != n:
            return d

def prime_factors(n):
    """返回 n 的不同质因子（去重升序）。"""
    if n == 1:
        return []
    result = set()
    stack = [n]
    while stack:
        cur = stack.pop()
        if cur == 1:
            continue
        if is_prime(cur):
            result.add(cur)
            continue
        d = pollard_rho(cur)
        stack.append(d)
        stack.append(cur // d)
    return sorted(result)

def check(limit, arr, fac_list, k):
    """给定阈值 limit，判断能否凑出长度 >= k 的合法子序列。"""
    best = {}
    for i, x in enumerate(arr):
        if x > limit:
            continue
        cur = 1
        primes = fac_list[i]
        for p in primes:
            v = best.get(p, 0)
            if v + 1 > cur:
                cur = v + 1
        if cur >= k:
            return True
        for p in primes:
            if cur > best.get(p, 0):
                best[p] = cur
    return False

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    arr = [int(x) for x in data[2:2 + n]]
    # 特判 k = 1：单元素自然合法，答案为数组最小值
    if k == 1:
        sys.stdout.write(str(min(arr)))
        return
    # 缓存同值分解结果，避免重复跑 Pollard-Rho
    memo = {}
    fac_list = []
    for x in arr:
        if x not in memo:
            memo[x] = prime_factors(x)
        fac_list.append(memo[x])
    # 候选答案只能是数组里出现过的值，去重升序
    vals = sorted(set(arr))
    # 最大值都不可行即全局无解
    if not check(vals[-1], arr, fac_list, k):
        sys.stdout.write("-1")
        return
    # 开区间二分：找使 check 成立的最小阈值
    lo, hi = 0, len(vals) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if check(vals[mid], arr, fac_list, k):
            hi = mid
        else:
            lo = mid + 1
    sys.stdout.write(str(vals[lo]))

if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：$n$ 个数的 Pollard-Rho 分解约 $O(n \cdot a^{1/4})$。每次 check 遍历数组并对每个元素遍历其质因子（不超过 $\log a$ 个），$O(n \log a)$。二分次数 $O(\log n)$。总计 $O(n \log n \cdot \log a + n \cdot a^{1/4})$。

空间复杂度：$O(n)$ 存放每个元素的质因子表，外加 $O(n)$ 大小的 $\text{best}$ 哈希表。

小结

• 第一题（荆棘林的最优砍断计划）：排序贪心的经典模型——”选子集并排序使约束最宽松”。关键洞察是失败尝试纯浪费锋利度，故最优策略只做必成功的尝试；按坚硬度从大到小排列让锋利度最充裕时对付最硬的目标
• 第二题（多约束条件下的元素匹配统计）：固定右端点 + 前缀哈希表是处理”$i \leq j$ 且值匹配”类统计问题的通用套路。核心技巧是先更新前缀再查询，使 $i = j$ 的情况自然包含
• 第三题（寻找满足条件的最优子序列）：三重技巧叠加——二分答案把最优化转判定、质因数分解把 GCD 约束转集合相交、哈希 DP 用质因子做键高效转移。遇到”最小化最大值 + 子序列约束”的组合，优先想到二分 + 可行性 DP