大厂真题 / 阿里巴巴

阿里 5.30 笔试真题 - AI研发岗

本场考试概述

考试时间：2026年5月30日 考试岗位：AI研发岗 难度评级：中等偏难

考点分析：

第一题：前后缀最值预处理（难度简单）
第二题：分类讨论 + 枚举（难度中等）
第三题：树状数组 + 中位定位（难度困难）

建议策略：

第一题从左到右、从右到左各扫一遍维护最近最大值位置即可，注意相等时更新策略
第二题分清”两行”“两列”“一行一列”“同一条线两次”四种情况，交点扣除是唯一易错点
第三题先想清楚触发条件等价于”某字母出现奇数次且当前位置是其中位”，一轮最多 26 次改动；时间紧可先写 $O(nk)$ 暴力骗小数据分

第一题：数组中的沉默元素计数

题目描述

给定一个长度为 $n$ 的数组 $a$。对于下标满足 $1 < i < n$ 的元素 $a_i$，若其左侧所有元素的最大值到它的距离，等于其右侧所有元素的最大值到它的距离，则称该位置是”沉默的”。

若左侧（或右侧）区域存在多个数值相等的最大值，则选择其中与 $i$ 距离最近的下标来计算距离。

求数组中一共有多少个位置不同的沉默元素。

多组测试数据，单个文件的 $n$ 之和不超过 $2 \times 10^5$。

样例

输入

输出

1
2

思路分析

第一步：明确需要计算什么

对每个内部位置 $i$（$1 < i < n$），需要知道两个量：

左侧区间 $[0, i-1]$ 内最大值中距 $i$ 最近的下标
右侧区间 $[i+1, n-1]$ 内最大值中距 $i$ 最近的下标

两个距离相等就计入答案。如果对每个 $i$ 单独扫一遍左右，总时间 $O(n^2)$，会超时。

第二步：前后缀分解

注意到”左侧最大值中距 $i$ 最近的下标”这个信息可以从左到右递推维护：

维护已扫描部分的最大值 best_val 和该最大值最近出现的下标 best_idx
到位置 $i$ 时，先记录 left_pos[i] = best_idx（用累积结果），再用 $a_i$ 更新累积量
更新条件用 $\geq$（而非 $>$）是关键：若新元素与当前最大值相等，必须把 best_idx 更新为当前位置。理由是对后续位置来说，同值最大中更靠右的那个距离更近

右侧对称地从右往左做。反向遍历时，同值更新自动保留较小下标（更靠左），恰好对应”距当前位置更近”。

第三步：两遍扫描各 $O(n)$，总计 $O(n)$

左扫只用到 $i$ 已经走过的前缀信息，右扫只用到 $i$ 还没走到的后缀信息，互不干扰。最后一次线性遍历统计即可。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    left_pos = [0] * n
    best_val = a[0]
    best_idx = 0
    for i in range(1, n):
        left_pos[i] = best_idx
        if a[i] >= best_val:
            best_val = a[i]
            best_idx = i

    right_pos = [0] * n
    best_val = a[n - 1]
    best_idx = n - 1
    for i in range(n - 2, -1, -1):
        right_pos[i] = best_idx
        if a[i] >= best_val:
            best_val = a[i]
            best_idx = i

    cnt = 0
    for i in range(1, n - 1):
        if i - left_pos[i] == right_pos[i] - i:
            cnt += 1
    print(cnt)

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：$O(n)$，左扫、右扫、统计各一次线性遍历 空间复杂度：$O(n)$，两个辅助数组

第二题：矩阵两次取线最大收益

题目描述

给定一个 $n \times m$ 的整数矩阵 $A$。进行两次操作：每次选择一整行或一整列，将所选行（或列）上的所有元素取走并累加到总和中。被取走后，该行（或列）上所有元素的值立即变为 $0$。

求能够获得的最大总和。

多组测试数据，所有测试中 $n \times m$ 的总和不超过 $5 \times 10^5$。

样例

输入

输出

39
26
9

思路分析

第一步：分析两条线的重叠关系

两条不同的行完全不相交，两条不同的列也不相交，只有”一行配一列”会在唯一一个交点格上重叠（该格被第一次清零，第二次只能贡献 $0$）。此外，两次选同一条线，第二次该线已全部为 $0$，收益为 $0$。

第二步：枚举四种候选方案

最优答案只可能来自以下四类：

两条不同的行：互不相交，收益 = 最大行和 + 次大行和
两条不同的列：互不相交，收益 = 最大列和 + 次大列和
一行 + 一列：交点格被算了两次但只能拿一次，收益 = $\text{row_sum_i} + \text{col_sum_j} - A[i][j]$，枚举所有 $(i,j)$ 取最大
同一条线选两次：第二次为 $0$，等价于只拿一条线的和。矩阵全负时多选只会拖累总和，这种情况必须考虑

第三步：取四者最大

分别 $O(n)$、$O(m)$、$O(nm)$、$O(n+m)$ 求出各候选最大值，总复杂度 $O(nm)$。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    A = []
    row_sum = [0] * n
    col_sum = [0] * m
    for i in range(n):
        row = list(map(int, input().split()))
        A.append(row)
        for j in range(m):
            row_sum[i] += row[j]
            col_sum[j] += row[j]

    NEG_INF = -10**30
    best = NEG_INF

    # 候选4：同一条线选两次（等价于只取最大单行/单列）
    best = max(best, max(row_sum), max(col_sum))

    # 候选1：两条不同的行
    if n >= 2:
        top1 = top2 = NEG_INF
        for v in row_sum:
            if v > top1:
                top2 = top1
                top1 = v
            elif v > top2:
                top2 = v
        best = max(best, top1 + top2)

    # 候选2：两条不同的列
    if m >= 2:
        top1 = top2 = NEG_INF
        for v in col_sum:
            if v > top1:
                top2 = top1
                top1 = v
            elif v > top2:
                top2 = v
        best = max(best, top1 + top2)

    # 候选3：一行 + 一列，交点扣除
    for i in range(n):
        ri = row_sum[i]
        for j in range(m):
            v = ri + col_sum[j] - A[i][j]
            if v > best:
                best = v

    print(best)

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：$O(nm)$，瓶颈在候选3的双重循环枚举交点 空间复杂度：$O(nm)$，存矩阵用于查询交点格

第三题：字符串等频递增变换

题目描述

给定一个长度为 $L$ 的小写字母字符串 $s$（下标从 $1$ 到 $L$），需要做 $k$ 次”操作”。

一次操作按 $i = 1, 2, \ldots, L$ 的顺序依次处理每个位置，修改立即生效。设位置 $i$ 的字符为 $c$，令 $x$ = 位置 $1$ 到 $i-1$ 中字符等于 $c$ 的数量，$y$ = 位置 $i+1$ 到 $L$ 中字符等于 $c$ 的数量。若 $x = y$，则将位置 $i$ 的字符修改为字母表中的下一个字母（z 变为 a），否则不变。

输出 $k$ 次操作后的最终字符串。

多组测试数据，$L$ 之和不超过 $2 \times 10^5$，$k$ 之和不超过 $10^5$。

样例

输入

2
2 1
ab
3 2
abc

输出

bb
bbe

思路分析

第一步：发现触发条件的等价形式

位置 $i$ 的字符 $c$ 在全串中共出现 $\text{cnt}$ 次。自己占 $1$ 个，左边有 $x$ 个、右边有 $y$ 个，所以 $x + y = \text{cnt} - 1$。触发条件 $x = y$ 代入得 $x = (\text{cnt} - 1) / 2$。

这告诉我们两件事：

$\text{cnt}$ 必须是奇数（否则 $x$ 不是整数）
$i$ 必须恰好是字符 $c$ 所有出现位置中从左数第 $\lfloor \text{cnt}/2 \rfloor + 1$ 个，即中位位置

第二步：每个字母一轮最多改一次

字母 $c$ 在中位位置被改走后，其出现次数 $\text{cnt}$ 减 $1$ 变为偶数，剩余同字母位置再也凑不出 $x = y$，本轮不再触发。所以一轮里最多发生 $26$ 次改动，与串长 $L$ 无关。

第三步：用树状数组快速定位中位

给每个字母维护一棵树状数组（BIT），记录它当前出现在哪些位置。需要两个快速操作：

单点更新（某位置字母改变时，从旧字母 BIT 移除、加入新字母 BIT）
查第 $k$ 小（找字母的中位位置）

BIT 上的 kth 查询通过倍增在 $O(\log L)$ 内完成。

第四步：堆调度一轮内的改动顺序

一轮要按位置从小到大处理。将 $26$ 个字母各自的中位位置放入小根堆，每次取出最靠左的处理。处理后只有两个字母的 BIT 变了（旧字母和新字母），重新计算它们的中位位置放回堆。

堆中可能有失效条目（位置已被越过或字母变为偶数次），取出时复核即可。

提前退出：若某一轮无任何触发（所有字母都是偶数次），字符串已定型，后续轮数全部跳过。

题解代码

import sys
import heapq
input = sys.stdin.readline

def solve():
    L, rounds = map(int, input().split())
    chars = bytearray(input().strip().encode())

    trees = [[0] * (L + 1) for _ in range(26)]
    freq = [0] * 26

    HEAD = 1
    while (HEAD << 1) <= L:
        HEAD <<= 1

    def bit_add(sym, p, val):
        tr = trees[sym]
        while p <= L:
            tr[p] += val
            p += p & -p

    def kth(sym, target):
        tr = trees[sym]
        node = 0
        step = HEAD
        rem = target
        while step:
            probe = node + step
            if probe <= L and tr[probe] < rem:
                node = probe
                rem -= tr[probe]
            step >>= 1
        return node + 1

    def median(sym):
        f = freq[sym]
        if f & 1:
            return kth(sym, (f >> 1) + 1)
        return -1

    for i in range(L):
        sym = chars[i] - 97
        freq[sym] += 1
        bit_add(sym, i + 1, 1)

    for _ in range(rounds):
        heap = []
        for sym in range(26):
            m = median(sym)
            if m >= 0:
                heap.append((m, sym))
        if not heap:
            break
        heapq.heapify(heap)

        cursor = 0
        fired = False

        while heap:
            mp, sym = heapq.heappop(heap)
            if mp <= cursor:
                continue
            cur_med = median(sym)
            if cur_med != mp:
                if cur_med > cursor:
                    heapq.heappush(heap, (cur_med, sym))
                continue

            fired = True
            next_sym = 0 if sym == 25 else sym + 1
            bit_add(sym, mp, -1)
            freq[sym] -= 1
            bit_add(next_sym, mp, 1)
            freq[next_sym] += 1
            chars[mp - 1] = next_sym + 97
            cursor = mp

            m1 = median(sym)
            if m1 > cursor:
                heapq.heappush(heap, (m1, sym))
            m2 = median(next_sym)
            if m2 > cursor:
                heapq.heappush(heap, (m2, next_sym))

        if not fired:
            break

    print(chars.decode())

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：$O(k \cdot 26 \cdot \log L)$，每轮最多 $26$ 次 BIT 操作，每次 $O(\log L)$ 空间复杂度：$O(26 \cdot L)$，$26$ 棵树状数组

小结

第一题是经典的前后缀预处理思路：维护滚动变量记录前缀/后缀最大值的最近位置，两遍扫描 $O(n)$ 解决。关键 trick 是同值用 $\geq$ 更新以保证”最近”语义
第二题看似复杂，实则只需想清楚两条线有几种相交关系——两行不交、两列不交、一行一列交一格、同线两次——分别求最优再取 max。别忘了”只取一条”对应全负场景
第三题核心洞察是触发条件等价于”中位位置”，加上”一轮每字母至多改一次”，将暴力 $O(nk)$ 降到 $O(k \cdot 26 \log n)$。树状数组的 kth 查询 + 堆调度是实现关键

这篇文章有帮助吗？

| GitHub 留言