大厂真题 / 阿里巴巴

阿里 5.9 笔试真题 - 算法岗

本场考试概述

考试时间：2026年5月9日 考试岗位：算法岗 难度评级：中等偏难

考点分析：

1. 第一题：构造 + 数论分类讨论（难度中等）
2. 第二题：思维 + 不变量分析（难度中等偏难）
3. 第三题：数位 DP + 高位贪心（难度困难）

建议策略：

1. 构造题先观察小数据规律，再尝试找循环节（如本场 4 个连续数自带和为 0 的解）
2. 模拟超时时优先寻找结构性结论，统计量往往就是答案的边界
3. 异或/二进制相关题目优先按位独立处理，配合数位 DP 模板

第一题：有符号型排列

题目描述

给定一个整数 $n$，构造一个长度为 $n$ 的数组 $a$，满足：

• 所有元素之和等于 $0$
• $\lvert a_1 \rvert, \lvert a_2 \rvert, \ldots, \lvert a_n \rvert$ 恰为 $1$ 到 $n$ 的一个排列
• 对每个 $i$，$a_i \neq 0$ 且 $\lvert a_i \rvert = $ 排列中对应的值

若无解输出 $-1$；若有解可输出任意一组。多组测试数据，$n$ 之和不超过 $10^5$。

样例

输入

3
2
3
4

输出

-1
1 2 -3
1 -2 -3 4

思路分析

第一步：分析有解条件

绝对值序列 $1, 2, \ldots, n$ 由题目钉死是排列，唯一能动的只有每个数前面的正负号。问题等价于：给 $1$ 到 $n$ 每个数贴正号或负号，让带符号的总和等于 $0$。

设正数集合的和为 $P$，负数集合的绝对值和为 $Q$，则 $P + Q = n(n+1)/2$ 且 $P - Q = 0$，解出 $P = Q = n(n+1)/4$。

所以 $n(n+1)/2$ 必须是偶数，即 $n(n+1)/4$ 为整数。$n$ 和 $n+1$ 是相邻整数，分析 $n \bmod 4$：

• $n \equiv 0 \pmod{4}$：$n$ 被 4 整除，$n(n+1)/4$ 是整数 ✓
• $n \equiv 1 \pmod{4}$：$n$ 是奇数，$n+1 \equiv 2$，只含一个因子 2，$n(n+1)/4$ 不是整数 ✗
• $n \equiv 2 \pmod{4}$：$n$ 含一个因子 2 但不含 4，$n+1$ 是奇数，$n(n+1)/4$ 不是整数 ✗
• $n \equiv 3 \pmod{4}$：$n$ 是奇数，$n+1$ 被 4 整除，$n(n+1)/4$ 是整数 ✓

结论：$n \bmod 4 = 1$ 或 $2$ 时无解。

第二步：四元组构造法

观察连续四个数 $x, x+1, x+2, x+3$，它们的首尾和与中间和相等：$x + (x+3) = (x+1) + (x+2) = 2x+3$。让首尾贴正号、中间贴负号：

每四个连续数自带一组和为 0 的解，互不干扰。

第三步：起点处理

• $n \equiv 0 \pmod{4}$：从 1 开始每 4 个一组套用四元组
• $n \equiv 3 \pmod{4}$：前 3 个数 $1 + 2 + (-3) = 0$ 自成一组，剩下 $n - 3$ 个数（是 4 的倍数）继续套四元组

题解代码

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    out = []
    for _ in range(T):
        n = int(input())
        if n % 4 == 1 or n % 4 == 2:
            out.append("-1")
            continue
        parts = []
        start = 1
        if n % 4 == 3:
            parts.extend(["1", "2", "-3"])
            start = 4
        for x in range(start, n + 1, 4):
            parts.append(str(x))
            parts.append(str(-(x + 1)))
            parts.append(str(-(x + 2)))
            parts.append(str(x + 3))
        out.append(" ".join(parts))
    print("\n".join(out))

solve()

复杂度分析

时间复杂度：$O(n)$，每个数只处理一次。 空间复杂度：$O(n)$，存储构造结果。

第二题：迷宫指示牌

题目描述

一条长度为 $n$ 的走廊，位置编号 $1$ 到 $n$。每个位置有一个指示牌 L 或 R。

小球从某个起点 $s$ 出发，运动规则：看当前位置指示牌方向，沿该方向走直到遇到第一个此前从未到达过的位置停下。小球一直运动直到从左侧走出（位置 $0$）或右侧走出（位置 $n+1$）。

对每一个起点 $s = 1, 2, \ldots, n$，输出小球最终从哪一侧出界（L 或 R）。

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

样例

输入

2
5
LRRLL
3
LLL

输出

LLLRR
LLL

思路分析

第一步：暴力不可行

逐起点模拟最坏 $O(n^2)$，总共 $O(n^3)$ 超时。需要找一个能直接给出所有起点答案的结构性结论。

第二步：发现不变量——L 的消耗

把小球的每一次动作（沿指示牌跳到下一个未访问位置或越界）称为一”步”。每步只用当前位置上的指示牌，且跳过去后不会再从该位置出发——因此每步消耗的位置两两不同。

假设小球从起点 $s$ 出发，最终从左侧出界。从位置 $s$ 一路把访问区间左端从 $s$ 扩展到 $1$，用了 $s - 1$ 次向左扩展，每次消耗一个 L。最后再加出界那一步也消耗一个 L，共消耗 $s$ 个 L。

这 $s$ 个 L 都来自已访问的位置（区间 $[1, \text{右端}]$ 以内），而整串 L 的总数 $\text{cnt}_L$ 必然 $\geq s$。

结论：左出界 $\Rightarrow$ $s \leq \text{cnt}_L$。

第三步：对称分析右出界

类似地，右出界消耗 $n - s + 1$ 个 R。整串 R 总数为 $n - \text{cnt}_L$，所以 $n - s + 1 \leq n - \text{cnt}_L$，整理得 $s \geq \text{cnt}_L + 1$。

结论：右出界 $\Rightarrow$ $s > \text{cnt}_L$。

第四步：互补证明取等

每个起点要么左出要么右出。设左出起点集 $A$、右出起点集 $B$，有 $A \subseteq {1, \ldots, \text{cnt}_L}$ 且 $B \subseteq {\text{cnt}_L + 1, \ldots, n}$。由于 $\lvert A \rvert + \lvert B \rvert = n$ 且两个范围恰好各有 $\text{cnt}_L$ 和 $n - \text{cnt}_L$ 个位置，两个子集必须各自取满。

最终结论：前 $\text{cnt}_L$ 个起点输出 L，后 $n - \text{cnt}_L$ 个起点输出 R。

题解代码

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    out = []
    for _ in range(T):
        n = int(input())
        w = input().strip()
        cnt_l = w.count('L')
        out.append('L' * cnt_l + 'R' * (n - cnt_l))
    print("\n".join(out))

solve()

复杂度分析

时间复杂度：$O(n)$，统计 L 数量加拼接答案。 空间复杂度：$O(n)$，输出串。

第三题：xab

题目描述

给定整数 $x$，以及 $a$ 的取值范围 $[l_a, r_a]$ 和 $b$ 的取值范围 $[l_b, r_b]$（所有值 $\leq 10^9$）。

定义 $x$ 的「最佳拍档」为满足范围约束且使 $x \oplus a \oplus b$（异或）值最大的整数对 $(a, b)$。

求不同「最佳拍档」的个数。多组测试数据。

样例

输入

2
0
1 2
0 2
5
1 7
6 9

输出

2
2

思路分析

第一步：按位独立性

异或的每一位结果只依赖 $x$、$a$、$b$ 对应位的值，位之间互不影响。这提示我们按位独立决策。暴力枚举 $a, b$ 共 $O(\text{范围}^2)$ 种组合不可行，但按位处理只有 31 位，规模可控。

第二步：高位贪心框架

将数写成 31 位二进制。由于最高位上的 $2^k$ 比下面所有位加起来都大（$2^k > 2^0 + 2^1 + \ldots + 2^{k-1}$），比较整数大小先比最高位。

从最高位往最低位扫描：若当前位存在合法 $(a, b)$ 使 $x \oplus a \oplus b$ 的这位等于 1，那么所有让这位等于 0 的方案全部淘汰；否则只能接受 0。

第三步：数位 DP 维护范围约束

高位贪心中还需保证 $a \in [l_a, r_a]$、$b \in [l_b, r_b]$。经典做法是用 4 个边界标记（tight flag）：

• eq_la：$a$ 的已确定前缀是否仍等于 $l_a$ 的对应前缀（贴着下界）
• eq_ra：$a$ 的已确定前缀是否仍等于 $r_a$ 的对应前缀（贴着上界）
• eq_lb、eq_rb：$b$ 的两个边界同理

4 个标记共 $2^4 = 16$ 种状态。定义 $f[s]$ 为按最大异或前缀走到当前位时，边界标记组合恰为 $s$ 的合法 $(a, b)$ 前缀方案数。

第四步：转移过程

处理第 $\text{pos}$ 位时，枚举 $a$ 的当前位 $a_b \in {0, 1}$ 和 $b$ 的当前位 $b_b \in {0, 1}$（共 4 种组合）：

1. 合法性检查：若 eq_la = 1 且 $a_b < l_a$ 的这位，违规跳过（$a$ 会低于下界）；eq_ra = 1 且 $a_b >$ 上界位同理
2. 更新标记：原本贴着且这位也相等才继续贴，否则脱钩
3. 计算当前位异或结果 $\text{cur} = x_b \oplus a_b \oplus b_b$
4. 将方案数累加到”cur=1 桶”或”cur=0 桶”

枚举完所有转移后，按高位贪心选择：若”cur=1 桶”非空则用它覆盖 $f$，否则用”cur=0 桶”。

第五步：最终答案

处理完最低位后，$\sum f[s]$ 即为达到最大异或值的 $(a, b)$ 对数。

题解代码

import sys
input = sys.stdin.readline

def count_best(x, la, ra, lb, rb):
    f = [0] * 16
    f[15] = 1  # 初始：空前缀同时贴着 4 个边界

    for pos in range(30, -1, -1):
        xb = (x >> pos) & 1
        la_b = (la >> pos) & 1
        ra_b = (ra >> pos) & 1
        lb_b = (lb >> pos) & 1
        rb_b = (rb >> pos) & 1

        nz = [0] * 16  # cur = 0 的桶
        no = [0] * 16  # cur = 1 的桶
        has_one = False

        for s in range(16):
            c = f[s]
            if c == 0:
                continue
            eq_la = s & 1
            eq_ra = (s >> 1) & 1
            eq_lb = (s >> 2) & 1
            eq_rb = (s >> 3) & 1

            for ab in (0, 1):
                if eq_la and ab < la_b:
                    continue
                if eq_ra and ab > ra_b:
                    continue
                n_la = 1 if eq_la and ab == la_b else 0
                n_ra = 1 if eq_ra and ab == ra_b else 0

                for bb in (0, 1):
                    if eq_lb and bb < lb_b:
                        continue
                    if eq_rb and bb > rb_b:
                        continue
                    n_lb = 1 if eq_lb and bb == lb_b else 0
                    n_rb = 1 if eq_rb and bb == rb_b else 0

                    ns = n_la | (n_ra << 1) | (n_lb << 2) | (n_rb << 3)
                    cur = xb ^ ab ^ bb
                    if cur == 1:
                        no[ns] += c
                        has_one = True
                    else:
                        nz[ns] += c

        f = no if has_one else nz

    return sum(f)

def solve():
    T = int(input())
    out = []
    for _ in range(T):
        x = int(input())
        la, ra = map(int, input().split())
        lb, rb = map(int, input().split())
        out.append(str(count_best(x, la, ra, lb, rb)))
    print("\n".join(out))

solve()

复杂度分析

时间复杂度：$O(31 \times 16 \times 4) = O(1984)$ 每组数据，常数级。 空间复杂度：$O(16)$，只维护当前层的状态数组。

小结

1. 第一题（有符号型排列）：关键洞察是 $n(n+1)/2$ 必须为偶数才有解（$n \bmod 4 \in {0, 3}$）。构造时利用”连续 4 个数首尾正、中间负和为 0”的四元组模式，简洁优雅。
2. 第二题（迷宫指示牌）：经典的”用不变量取代模拟”思维题。核心证明：左出界必消耗 $s$ 个 L，而整串最多 $\text{cnt}_L$ 个 L，所以左出当且仅当 $s \leq \text{cnt}_L$。答案只需数一次 L 的个数。
3. 第三题（xab）：异或按位独立的性质引出高位贪心框架，配合 4 个 tight flag 组成 16 状态的数位 DP，从高位到低位逐层贪心选择最大异或位。每组数据复杂度为常数级，适合大量测试组。