大厂真题 / 阿里巴巴

阿里 3.28 笔试真题 - 研发岗

本场考试概述

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

考点分析：

第一题：枚举数位长度（难度简单）
第二题：贪心/数学分析（难度中等）
第三题：DFS序 + 线段树（难度困难）

建议策略：

前两题偏思维，快速拿下
第三题线段树是拉分题，建议研发岗同学把DFS序+线段树组合作为必练模板

第一题：值

题目描述

给定一个正整数 x，请你构造一个十进制正整数 n，使得 n 的十进制数位长度与 n 的值的乘积恰好等于 x。

十进制数位长度指的是 n 的十进制表示中，去掉所有前导零后剩余的数字个数。例如：1 的数位长度为 1，10 的数位长度为 2，100 的数位长度为 3。

样例

输入

输出

题解：枚举数位长度

n 的位数最多 18 位，枚举位数 d 从 1 到 18，检查 x 能否被 d 整除且 x/d 恰好是 d 位数。

时间复杂度：O(18)。 空间复杂度：O(1)。

import sys
input = sys.stdin.readline

def digit_len(n):
    if n == 0:
        return 1
    length = 0
    while n > 0:
        length += 1
        n //= 10
    return length

def solve(x):
    for d in range(1, 19):
        if x % d != 0:
            continue
        n = x // d
        if digit_len(n) == d:
            return n
    return -1

T = int(input())
out = []
for _ in range(T):
    x = int(input())
    out.append(str(solve(x)))
print("\n".join(out))

第二题：不稳定or相似

题目描述

给定两个整数 n, m，你需要构造一个长度为 n 的非负整数数组 a，使其元素总和为 m。

本题有 q 次独立询问。第 i 次询问给出一对整数 (d, y)，你最多只能让数组中相邻数值不同的边的数量不超过 d，问在该限制下，是否存在某个数组 a 使 F(a) = y。若存在，输出 YES；否则输出 NO。

样例

输入

输出

NO
YES
NO
YES
NO
YES
NO

题解：贪心（数学分析）

分情况讨论：d=0 需常数列（m 整除 n 才行）；d=1 把 m 堆在端点，上界为 m；d>=2 堆在内部位置，上界为 2m。

时间复杂度：O(q)。

import sys
input = sys.stdin.readline

def max_f(n, m, d):
    ed = min(d, n - 1)
    if m == 0 or n == 1:
        return 0
    if ed == 0:
        return 0 if m % n == 0 else -1
    if ed == 1:
        return m
    return 2 * m

t = int(input())
out = []
for _ in range(t):
    n, m, q = map(int, input().split())
    for _ in range(q):
        d, y = map(int, input().split())
        mf = max_f(n, m, d)
        out.append("NO" if mf == -1 or y > mf else "YES")
print("\n".join(out))

第三题：递增

题目描述

给定一棵由 n 个节点（编号 1~n）和 n-1 条边构成的、根节点为 1 的树。初始时，每个节点 i 的权值为 i。

接下来共有 m 次修改操作。第 j 次操作给出一个节点 x：找出以 x 为根的子树中当前权值最小的节点，并将该节点的权值修改为 j+n。

请输出所有节点在所有操作完成后的最终权值。

样例

输入

输出

4 5 3

题解：DFS序 + 线段树

用 DFS 序将子树映射为连续区间，线段树维护区间最小值及其节点编号。每次查询子树最小值后，更新为 j+n。

时间复杂度：O((n + m) log n)。 空间复杂度：O(n)。

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1)

INF = 10**9

def dfs(root, n, adj):
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    order = [0] * n
    timer = 0
    stack = [(root, 0, False)]
    while stack:
        u, parent, visited = stack.pop()
        if not visited:
            tin[u] = timer
            order[timer] = u
            timer += 1
            stack.append((u, parent, True))
            for v in reversed(adj[u]):
                if v != parent:
                    stack.append((v, u, False))
        else:
            tout[u] = timer - 1
    return tin, tout, order

def push_up(node, seg_w, seg_id):
    if seg_w[2 * node] <= seg_w[2 * node + 1]:
        seg_w[node] = seg_w[2 * node]
        seg_id[node] = seg_id[2 * node]
    else:
        seg_w[node] = seg_w[2 * node + 1]
        seg_id[node] = seg_id[2 * node + 1]

def build(node, l, r, order, seg_w, seg_id):
    if l == r:
        seg_w[node] = order[l]
        seg_id[node] = order[l]
        return
    mid = (l + r) // 2
    build(2 * node, l, mid, order, seg_w, seg_id)
    build(2 * node + 1, mid + 1, r, order, seg_w, seg_id)
    push_up(node, seg_w, seg_id)

def query(node, l, r, ql, qr, seg_w, seg_id):
    if ql <= l and r <= qr:
        return seg_w[node], seg_id[node]
    if ql > r or qr < l:
        return INF, 0
    mid = (l + r) // 2
    lw, lid = query(2 * node, l, mid, ql, qr, seg_w, seg_id)
    rw, rid = query(2 * node + 1, mid + 1, r, ql, qr, seg_w, seg_id)
    return (lw, lid) if lw <= rw else (rw, rid)

def update(node, l, r, pos, w, nid, seg_w, seg_id):
    if l == r:
        seg_w[node] = w
        seg_id[node] = nid
        return
    mid = (l + r) // 2
    if pos <= mid:
        update(2 * node, l, mid, pos, w, nid, seg_w, seg_id)
    else:
        update(2 * node + 1, mid + 1, r, pos, w, nid, seg_w, seg_id)
    push_up(node, seg_w, seg_id)

def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)

    tin, tout, order = dfs(1, n, adj)

    seg_w = [0] * (4 * n)
    seg_id = [0] * (4 * n)
    build(1, 0, n - 1, order, seg_w, seg_id)

    ans = list(range(n + 1))  # ans[i] = i initially

    for j in range(1, m + 1):
        x = int(input())
        _, min_node = query(1, 0, n - 1, tin[x], tout[x], seg_w, seg_id)
        new_val = j + n
        ans[min_node] = new_val
        update(1, 0, n - 1, tin[min_node], new_val, min_node, seg_w, seg_id)

    print(" ".join(str(ans[i]) for i in range(1, n + 1)))

main()

小结

第一题枚举数位长度，O(18) 即可解决，属于签到题
第二题贪心数学分析，关键是推导出 F(a) 的上界与不同边数 d 的关系
第三题 DFS序 + 线段树是经典组合，将子树操作转化为区间操作，研发岗高频考点

这篇文章有帮助吗？

| GitHub 留言