大厂真题 / 阿里巴巴

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

本场考试概述

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

考点分析：

第一题：模拟（难度简单）
第二题：位运算 + 超集变换（难度中等）
第三题：二分答案（难度困难）

建议策略：

第一题是纯模拟题，注意区分左侧已处理计数和右侧原始计数即可快速拿下
第二题利用值域仅 10 位的特性，用超集 AND 变换替代暴力枚举
第三题需要推导公式将 $f(l,r)$ 用前缀和的前缀和 $O(1)$ 表示，再利用单调性二分

第一题：蝴蝶乐园

题目描述

给定长度为 $n$ 的字符串 $s$，从左到右依次处理位置 $0$ 到 $n-1$。

处理位置 $i$ 时：左侧（位置 $0$ 到 $i-1$）已经是处理后的最终字符，右侧（位置 $i+1$ 到 $n-1$）还是原始字符。

对每个位置 $i$，令 $c$ 为当前字符，$L$ 为左侧已处理部分中 $c$ 的出现次数，$R$ 为右侧原始字符中 $c$ 的出现次数。若 $L = R$，则将 $c$ 替换为下一个字母（$\text{‘z’}$ 变为 $\text{‘a’}$）；否则不变。

多组测试数据，$n$ 之和不超过 $10^6$。

样例

输入

3
1
a
3
aba
3
zzz

输出

b
aca
zaz

思路分析

第一步：理解处理顺序的关键

左侧计数基于已修改后的字符（因为左侧已处理完毕），右侧计数基于原始字符串（因为右侧尚未处理）。这是本题最容易出错的地方。

第二步：双计数数组模拟

维护两个长度为 26 的计数数组：

$\text{left}[c]$：记录左侧已处理部分中字符 $c$ 的出现次数
$\text{right}[c]$：记录原始字符串中当前位置右侧字符 $c$ 的出现次数

初始化时，$\text{right}$ 统计原始字符串 $s[1..n-1]$ 的字符频次。

第三步：逐位处理

遍历位置 $i$：读取当前字符 $c$，若 $\text{left}[c] = \text{right}[c]$ 则替换为下一个字母。处理完后，将修改后的字符计入 $\text{left}$；同时将原始字符串中下一个位置的字符从 $\text{right}$ 中移除。

题解代码

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(input().strip())
    orig = s[:]
    left = [0] * 26
    right = [0] * 26
    for i in range(1, n):
        right[ord(orig[i]) - 97] += 1
    for i in range(n):
        c = ord(s[i]) - 97
        if left[c] == right[c]:
            s[i] = 'a' if c == 25 else chr(ord(s[i]) + 1)
        left[ord(s[i]) - 97] += 1
        if i + 1 < n:
            right[ord(orig[i + 1]) - 97] -= 1
    print(''.join(s))

复杂度分析

时间复杂度：$O(n)$，每个字符处理一次，计数操作均为 $O(1)$。 空间复杂度：$O(|\Sigma|)$，两个大小为 26 的计数数组加上原始字符串的拷贝。

第二题：按位与

题目描述

给定数组 $a$（长度 $n$，$0 \leq a_i < 1024$）。可以反复选两个元素取按位 AND 并追加到数组末尾。求操作任意次后，数组中最多能有多少个不同的元素。

样例

输入

输出

4
5

思路分析

第一步：AND 的单调性

AND 只能把 1 变成 0，不会产生新的 1。所以所有可达值都是原数组某个非空子集的 AND。

第二步：判定准则

要造出值 $m$，参与 AND 的每个元素在 $m$ 的 0 位上可以任意，但在 $m$ 的 1 位上必须也是 1——否则那一位直接变 0。把数组中满足 $(a_i \mathop{\&} m) = m$ 的元素称为 $m$ 的”超集元素”。

AND 的元素越多，1 位只会越少。所以把 $m$ 的全部超集元素 AND 起来，是消除多余位的最佳组合——如果结果恰好等于 $m$，则 $m$ 可达；如果还多出某些 1 位，$m$ 不可达。

以 $a = [7, 3, 5]$（即 $[111_2, 011_2, 101_2]$）为例：

$m = 1$（$001_2$）：超集元素 ${7, 3, 5}$（都含第 0 位），AND = $001_2 = 1$，可达
$m = 2$（$010_2$）：超集元素 ${7, 3}$（含第 1 位），AND = $011_2 = 3 \neq 2$，不可达
$m = 5$（$101_2$）：超集元素 ${7, 5}$，AND = $101_2 = 5$，可达

第三步：超集 AND 变换

朴素做法对每个 $m$ 扫一遍数组取超集元素做 AND，$O(1024 \times n)$。可以用超集 AND 变换降到 $O(1024 \times 10)$：

初始化 $f[v] = v$（出现在数组中），其余 $f[v] = -1$。对每个 bit $b$，遍历所有第 $b$ 位为 0 的 $m$，将 $f[m \mid 2^b]$ AND 进 $f[m]$。10 轮后，$f[m]$ 就包含了 $m$ 的全部超集元素的 AND。统计 $f[m] = m$ 的数量即为答案。

题解代码

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    f = [-1] * 1024
    for v in a:
        f[v] = v if f[v] == -1 else (f[v] & v)
    for b in range(10):
        for m in range(1024):
            if not (m & (1 << b)):
                m2 = m | (1 << b)
                if f[m2] != -1:
                    f[m] = f[m2] if f[m] == -1 else (f[m] & f[m2])
    print(sum(1 for m in range(1024) if f[m] == m))

复杂度分析

时间复杂度：$O(n + V \cdot \log V)$，其中 $V = 1024$，读入 $O(n)$，逐位合并 $O(1024 \times 10)$。 空间复杂度：$O(V)$，固定大小的掩码数组。

第三题：区间第k小

题目描述

给定长度为 $n$ 的非负整数序列 $a$。定义：

\[f(l, r) = \sum_{i=l}^{r} \sum_{j=l}^{i} a_j\]

求在所有 $\frac{n(n+1)}{2}$ 个区间 $[l, r]$ 中，$f$ 值从小到大排序后的第 $k$ 小值。

多组测试数据，$n$ 之和不超过 $10^5$。

样例

输入

输出

2
2

思路分析

第一步：公式推导——把 $f(l,r)$ 化为 $O(1)$

展开 $f(l,r)$ 观察每个 $a_j$ 被加了多少次：$a_l$ 出现在全部 $r - l + 1$ 个求和中，$a_{l+1}$ 出现在 $r - l$ 个，…，$a_r$ 出现在 1 个。即 $a_j$ 被加了 $r - j + 1$ 次。

引入前缀和 $S_i = a_1 + \dots + a_i$ 和前缀和的前缀和 $P_i = S_0 + S_1 + \dots + S_i$，可以推导出：

\[f(l, r) = P_r - P_{l-1} - (r - l + 1) \cdot S_{l-1}\]

这样任意区间的 $f$ 值可以 $O(1)$ 计算。

第二步：单调性观察

由于 $a_i \geq 0$，前缀和 $S$ 单调不减。固定 $l$ 后，$f(l, r)$ 关于 $r$ 单调不减——每多加一个非负元素，累积和只增不减。

第三步：二分答案

有了单调性，就可以二分 $f$ 的值 $X$：统计有多少区间的 $f(l,r) \leq X$。若数量 $\geq k$，说明第 $k$ 小值 $\leq X$；否则第 $k$ 小值 $> X$。

第四步：check 函数

给定 $X$，逐个枚举左端点 $l$。对固定的 $l$，$f(l,r)$ 关于 $r$ 单调不减，满足 $f(l,r) \leq X$ 的 $r$ 构成一段连续区间。将不等式展开：

\[P_r - r \cdot S_{l-1} \leq X + P_{l-1} - (l-1) \cdot S_{l-1}\]

右边对固定 $l$ 是常数，左边关于 $r$ 单调不减，因此可以二分找到最大的 $r$。

题解代码

import sys
input = sys.stdin.readline

def solve(n, k, a):
    S = [0] * (n + 1)
    P = [0] * (n + 1)
    for i in range(1, n + 1):
        S[i] = S[i - 1] + a[i]
    for i in range(1, n + 1):
        P[i] = P[i - 1] + S[i]

    def count_le(X):
        cnt = 0
        for l in range(1, n + 1):
            C = P[l - 1] - (l - 1) * S[l - 1]
            target = X + C
            lo2, hi2, best = l, n, l - 1
            while lo2 <= hi2:
                mid = (lo2 + hi2) // 2
                if P[mid] - mid * S[l - 1] <= target:
                    best = mid
                    lo2 = mid + 1
                else:
                    hi2 = mid - 1
            if best >= l:
                cnt += best - l + 1
        return cnt

    lo, hi = 0, P[n]
    while lo < hi:
        mid = (lo + hi) // 2
        if count_le(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    print(solve(n, k, a))

复杂度分析

时间复杂度：$O(n \log n \cdot \log V)$，其中 $V$ 为最大可能的 $f$ 值。外层二分 $O(\log V)$ 轮，每轮枚举 $n$ 个左端点各做一次 $O(\log n)$ 的内层二分。 空间复杂度：$O(n)$，存储前缀和数组。

小结

第一题是模拟题，关键在于区分”左侧已处理计数”和”右侧原始计数”，维护双计数数组即可
第二题利用 $a_i < 1024$（10 位）的值域特性，用超集 AND 变换在 $O(V \log V)$ 内判定所有可达值，避免了 $O(V \times n)$ 的暴力
第三题是经典的”第 $k$ 小值”问题框架：先推导 $O(1)$ 公式，再利用单调性做二分答案 + 二分 check

这篇文章有帮助吗？

| GitHub 留言