大厂真题 / 携程

携程 5.10 笔试真题 - 研发岗

本场考试概述

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

考点分析：

第一题：数学不变量（难度简单）
第二题：位运算 + 按位贡献分析（难度中等）
第三题：贪心构造（难度中等）
第四题：树状数组 + 冒泡轨迹分析（难度困难）

建议策略：

第一、二题为基础思维题，优先稳拿
第三题贪心结构清晰，掌握”独立计数”性质即可 AC
第四题需要发现冒泡排序中元素右移的轨迹规律，时间不够可保前三题

第一题：资源平衡

题目描述

两个王国分别拥有 $x$ 和 $y$ 单位水晶。它们可以进行”平衡仪式”：拥有至少 2 单位水晶的王国消耗 2 单位自己的水晶，为另一个王国增加 1 单位水晶。仪式可由任一王国发起、进行任意次。问能否最终使双方水晶数量相等。

样例

输入

输出

YES
YES
YES
NO

思路分析

第一步：分析操作对差值的影响

设 $A$ 国发起仪式：$(x, y) \to (x-2, y+1)$，差值 $x - y$ 变化 $-3$。$B$ 国发起时差值变化 $+3$。无论谁发起，差值只能变化 $\pm 3$。

第二步：得出不变量

$(x - y) \mod 3$ 是操作的不变量。要让 $x = y$（即差值为 0），必须初始差值能被 3 整除。

第三步：充分性验证

若 $(x - y) \equiv 0 \pmod{3}$，设差为 $3k$。让拥有更多水晶的一方发起 $k$ 次仪式即可让两者相等（每次操作前发起方至少有 2 单位水晶可以验证）。

题解代码

import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    x, y = map(int, input().split())
    print("YES" if (x - y) % 3 == 0 else "NO")

复杂度分析

时间复杂度：$O(T)$ 空间复杂度：$O(1)$

第二题：删除

题目描述

给定长度为 $n$ 的正整数数组 $a$，记所有数按位与的结果为 $\text{AND}$。统计有多少个下标 $i$，满足删除 $a_i$ 后剩余元素的按位与严格变大。

样例

输入

输出

1
0
2

思路分析

第一步：理解”按位与变大”的含义

按位与的性质：删除元素只会让某些位从 0 变成 1（因为少了一个 0 的贡献），不会让 1 变成 0。所以”严格变大”等价于：存在某一位，删除后从 0 翻成了 1。

第二步：充要条件

某一位从 0 变成 1，说明原本全数组中该位为 0 的元素恰好只有 $a_i$ 一个。删掉它后，该位在剩余所有元素中都是 1，按位与结果该位变 1，整体变大。

第三步：逐位统计

对每一位 $b$（0 到 29），扫一遍数组统计该位为 0 的元素个数。若恰好只有 1 个，把对应下标标记为”可删除”。最终统计被标记的下标数量（同一个下标可能因多个位被标记，用布尔数组自然去重）。

题解代码

import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    mark = [False] * n
    for b in range(30):
        cnt = 0
        idx = -1
        for i in range(n):
            if not ((a[i] >> b) & 1):
                cnt += 1
                idx = i
                if cnt > 1:
                    break
        if cnt == 1:
            mark[idx] = True
    print(sum(mark))

复杂度分析

时间复杂度：$O(30n)$ 空间复杂度：$O(n)$

第三题：寿司

题目描述

有一个长度为 $n$、仅由小写字母组成的字符串 $s$（已丢失），以及一个保留下来的数组 $a$。其中 $a_i$ 表示在位置 $i$ 之前，与 $s_i$ 相同的字符个数。请根据数组 $a$ 重构任意一个满足条件的字符串；若不存在则输出 -1。

样例

输入

2
7
0 0 1 0 2 1 3
3
0 0 2

输出

abacaba
-1

思路分析

第一步：理解约束

$a_i$ 的含义是”在 $s$ 的前 $i$ 个字符中，和 $s_i$ 相同的字符恰好出现了 $a_i$ 次”。换句话说，$s_i$ 这个字母在位置 $i$ 之前已经出现过 $a_i$ 次。

第二步：贪心构造

从左到右扫描，维护 26 个字母各自当前的出现次数 $\text{cnt}[c]$。对位置 $i$，找任意一个满足 $\text{cnt}[c] = a_i$ 的字母填入，然后 $\text{cnt}[c]$ 加 1。

第三步：正确性

字母之间的计数相互独立。选了某个字母不会影响其他字母的计数，因此任选一个满足条件的字母都不会让后续位置变得无解。若 26 个字母都不满足则无解。

题解代码

import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0] * 26
    result = []
    valid = True
    for x in a:
        found = -1
        for c in range(26):
            if cnt[c] == x:
                found = c
                break
        if found == -1:
            valid = False
            break
        result.append(chr(ord('a') + found))
        cnt[found] += 1
    print(''.join(result) if valid else '-1')

复杂度分析

时间复杂度：$O(26n)$ 空间复杂度：$O(n)$

第四题：单数组交换

题目描述

给定长度为 $n$ 的数组 $a$ 和数组 $b$。对 $a$ 执行标准冒泡排序（将其排为非递减）。每次实际发生交换时，若交换位置为 $j$（交换 $a_j$ 和 $a_{j+1}$），代价为：若 $b_j < b_{j+1}$ 则代价 1，否则代价 0。求冒泡排序完成后所有交换的总代价。

样例

输入

2
4
2 1 2 1
3 1 2 2
6
17 15 12 10 18 3
1 5 1 3 1 2

输出

1
7

思路分析

第一步：直接模拟的瓶颈

标准冒泡排序是 $O(n^2)$，$n \leq 10^5$ 时无法承受。需要分析冒泡过程中每次交换落在哪些边界上。

第二步：分析元素的运动轨迹

定义两个量：

$L_i$：元素 $a_i$ 在排序过程中被”左推”的次数（左侧有多少个比它大的元素会从它身上跨过）= 左侧严格大于 $a_i$ 的元素个数
$R_i$：元素 $a_i$ “右移”的次数（右侧有多少个比它小的元素需要它越过）= 右侧严格小于 $a_i$ 的元素个数

第三步：右移横跨的边界区间

冒泡排序中，元素 $a_i$ 先被左推 $L_i$ 格到位置 $i - L_i$，然后连续右移 $R_i$ 格。第 $k$ 次右移跨过边界 $i - L_i + k - 1$。因此元素 $a_i$ 的所有右移横跨边界区间为 $[i - L_i, \ i - L_i + R_i - 1]$。

第四步：前缀和加速

定义 $\text{cum}[p] = \sum_{q=0}^{p-1} [b_q < b_{q+1}]$（边界处代价为 1 的前缀和）。元素 $a_i$ 贡献的总代价为 $\text{cum}[i - L_i + R_i] - \text{cum}[i - L_i]$。

第五步：用树状数组求 $L_i$ 和 $R_i$

从左到右扫描，用 BIT 求”已插入元素中严格大于 $a_i$ 的个数”得到 $L_i$
从右到左扫描，用 BIT 求”已插入元素中严格小于 $a_i$ 的个数”得到 $R_i$

题解代码

import sys

input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if n <= 1:
        print(0)
        return

    # 离散化
    sa = sorted(set(a))
    rank_map = {v: i + 1 for i, v in enumerate(sa)}
    rk = [rank_map[x] for x in a]
    m = len(sa)

    # 树状数组
    bit = [0] * (m + 2)
    def update(i):
        while i <= m:
            bit[i] += 1
            i += i & -i
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    # 从左到右求 L[i]: 已插入中严格大于 a[i] 的个数
    L = [0] * n
    for i in range(n):
        L[i] = query(m) - query(rk[i])
        update(rk[i])

    # 从右到左求 R[i]: 已插入中严格小于 a[i] 的个数
    bit = [0] * (m + 2)
    R = [0] * n
    for i in range(n - 1, -1, -1):
        R[i] = query(rk[i] - 1)
        update(rk[i])

    # 前缀和: cum[p] = [0, p) 内 b[q] < b[q+1] 的边界数
    cum = [0] * (n + 1)
    for q in range(n - 1):
        cum[q + 1] = cum[q] + (1 if b[q] < b[q + 1] else 0)

    # 对每个元素累加贡献
    cost = 0
    for i in range(n):
        if R[i] == 0:
            continue
        s = i - L[i]
        f = s + R[i]
        cost += cum[f] - cum[s]

    print(cost)

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

复杂度分析

时间复杂度：$O(n \log n)$，两次树状数组扫描 空间复杂度：$O(n)$

小结

第一题是纯数学题，找到差值模 3 的不变量即可一行判断
第二题按位分析贡献，统计每一位上为 0 的元素是否唯一
第三题贪心构造字符串，利用字母计数独立性保证任选合法字母都不破坏后续可行性
第四题是本场硬题，需要深入分析冒泡排序中元素的运动轨迹，用树状数组 + 前缀和将 $O(n^2)$ 降到 $O(n \log n)$

这篇文章有帮助吗？

| GitHub 留言