大厂真题 / 拼多多

拼多多 8.16 笔试真题 - 算法岗

本场考试概述

考试时间：2026年8月16日

考试岗位：算法岗

难度评级：中等偏难

考点分析：

• 第一题：异或与按位与、二重枚举
• 第二题：队列性质、栈出序列模拟
• 第三题：按输入顺序动态规划、树状数组维护前缀最大值
• 第四题：按结束时间排序、动态规划与二分查找

第 1 题：神秘三件套

题意

商品价格为 $1$ 到 $n$ 的整数。选择价格分别为 $a,b,c$ 的三件商品，要求：

1. $1 \leq a \leq b \leq c \leq n$；
2. $a \mathbin{\oplus} b \mathbin{\oplus} c=0$；
3. 三个价格能够作为三角形的三条边，即任意两边之和严格大于第三边。

求满足条件的三元组数量。

输入输出

输入一行，一个整数 $n$。

数据范围：$1 \leq n \leq 2500$。

输出一个整数，表示合法三元组的数量。

样例 1

输入

6

输出

1

合法三元组为 $(3,5,6)$。

样例 2

输入

10

输出

2

思路

由异或条件可得

因此只需枚举 $a,b$，第三个数随之唯一确定。枚举时令 $a \leq b$，再检查 $b \leq c \leq n$，即可保证价格有序且都在范围内。

由于 $c$ 是最大边，三角形条件只需检查 $a+b>c$。整数加法满足

代入 $c=a \mathbin{\oplus} b$ 后，$a+b>c$ 当且仅当 $a \mathbin{\&} b$ 非零。于是每对 $(a,b)$ 只需常数次位运算即可判定。

正确性证明

对任意被算法计数的 $(a,b,c)$，算法令 $c=a \mathbin{\oplus} b$，所以三数异或为零；检查 $a \leq b \leq c \leq n$ 保证范围与顺序合法；检查 $a \mathbin{\&} b$ 非零，根据上述恒等式等价于 $a+b>c$。又因为 $c$ 为最大边，其余两条三角形不等式自动成立，因此该三元组一定合法。

反之，对任意合法三元组，由异或条件必有 $c=a \mathbin{\oplus} b$。算法枚举到它的 $a,b$ 时，范围与顺序检查会通过；合法三角形满足 $a+b>c$，故 $a \mathbin{\&} b$ 非零，算法必定将它计数。每个有序三元组对应唯一一对 $(a,b)$，不会重复。因此算法恰好统计全部合法答案。

题解代码

import sys


def solve():
    n = int(sys.stdin.readline())
    answer = 0

    for a in range(1, n + 1):
        for b in range(a, n + 1):
            c = a ^ b
            if b <= c <= n and (a & b) != 0:
                answer += 1

    print(answer)


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：$O(n^2)$，枚举所有满足 $a \leq b$ 的数对。

空间复杂度：$O(1)$，只使用若干整数变量。

易错点

• 价格从 $1$ 开始，异或得到的 $c=0$ 不合法。
• 必须检查 $c \geq b$，否则会把未按非降顺序排列的三元组计入。
• 三角形要求严格大于；这里对应 $a \mathbin{\&} b$ 非零，而不是允许等于零。

第 2 题：魔法通道

题意

一串彩球按字符串 $S$ 的顺序进入暂存区，并按字符串 $T$ 的顺序离开。暂存区可能采用以下一种模式：

• 队列：先进先出；
• 栈：后进先出。

每次可以让下一个彩球进入，也可以让暂存区允许取出的一端弹出一个彩球，最终所有彩球都要离开。判断 $T$ 在队列模式和栈模式下是否可实现。

输入输出

输入共两行：第一行是仅含小写英文字母的字符串 $S$，第二行是字符串 $T$。两者长度相同，且所含字符及各字符数量相同。

数据范围：$1 \leq \lvert S \rvert=\lvert T \rvert \leq 100000$。

若仅队列可行，输出 queue；若仅栈可行，输出 stack；若两者均可行，输出 both；若两者均不可行，输出 neither。

样例 1

输入

abc
abc

输出

both

队列会保持原顺序；栈模式也可以让每个字符入栈后立即出栈。

样例 2

输入

abc
cba

输出

stack

三个字符全部入栈后依次弹出即可得到 cba，队列则只能得到 abc。

思路

队列不会改变元素的相对顺序，因此队列模式可行当且仅当 $S=T$。

栈模式使用贪心模拟。依次把 $S$ 中的字符压栈，并用指针 $j$ 指向 $T$ 中下一个需要输出的字符。每次压栈后，只要栈顶等于 $T_j$，就立刻弹出并移动 $j$。扫描完成后，若 $T$ 已全部匹配，则存在合法的入栈、出栈操作序列。

“能弹就弹”不会损失可行解：当前栈顶正是下一项输出时，它最终必须先于栈中其他元素离开；立即弹出只是在执行一个不可避免的操作。

正确性证明

队列中先进入的元素必先离开，所以其完整出序列唯一等于 $S$，队列判定显然正确。

对栈判定，算法每次弹出的字符都等于当前所需的 $T_j$，故若最终匹配完整个 $T$，模拟过程本身就是一组合法操作，栈模式可行。

反过来，假设存在得到 $T$ 的合法栈操作。当算法发现栈顶等于当前所需字符时，该字符在任何合法方案中都必须在栈内其他字符之前弹出；提前弹出不会改变尚未入栈字符的次序，也不会妨碍后续操作。因此可将任意合法方案逐步调整为算法的贪心弹出方式而不破坏可行性。若 $T$ 可由栈产生，算法最终必能匹配全部字符。结合两个独立判定，四种输出分类均正确。

题解代码

import sys


def stack_possible(source, target):
    stack = []
    j = 0

    for ch in source:
        stack.append(ch)
        while stack and j < len(target) and stack[-1] == target[j]:
            stack.pop()
            j += 1

    return j == len(target)


def solve():
    source = sys.stdin.readline().strip()
    target = sys.stdin.readline().strip()

    queue_ok = source == target
    stack_ok = stack_possible(source, target)

    if queue_ok and stack_ok:
        print("both")
    elif queue_ok:
        print("queue")
    elif stack_ok:
        print("stack")
    else:
        print("neither")


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：$O(n)$，每个字符至多入栈和出栈各一次，其中 $n=\lvert S \rvert$。

空间复杂度：$O(n)$，最坏情况下栈中暂存全部字符。

易错点

• 每次入栈后要用 while 连续弹出，不能只检查一次。
• 字符可能重复，不能用“字符第一次出现位置”之类的方法替代栈模拟。
• both 的情况不仅限于长度为一；例如输入序列与输出序列相同时总是两种模式都可行。

第 3 题：递增边路径

题意

给定一个含 $n$ 个节点、$m$ 条有向边的图。边按输入顺序编号，第 $i$ 条边从 $a_i$ 指向 $b_i$，权值为 $w_i$；图中可能存在自环和重边。

选择一条首尾相接的有向路径，要求路径中各条边的输入编号严格递增，并且边权也严格递增。求路径最多包含多少条边。

输入输出

第一行输入两个整数 $n,m$。接下来 $m$ 行，每行输入三个整数 $a_i,b_i,w_i$，表示一条有向边。

数据范围：$1 \leq n \leq 100000$，$1 \leq m \leq 100000$，$1 \leq a_i,b_i \leq n$，$0 \leq w_i \leq 100000$。

输出一个整数，表示满足条件的路径的最大边数。

样例 1

输入

3 3
3 1 3
1 2 1
2 3 2

输出

2

可以选择后两条边形成 $1\to2\to3$。不能再接输入中的第一条边 $3\to1$，因为它的编号更小。

样例 2

输入

5 5
1 3 2
3 2 3
3 4 5
5 4 0
4 5 8

输出

3

思路

按输入顺序处理边，当前边的所有候选前驱都已经处理，因此边编号严格递增这一维不必进入状态。

对每个节点 $v$，维护所有“以 $v$ 为终点”的已处理路径，并按最后一条边的权值查询最长长度。处理边 $(a,b,w)$ 时，需要找到以 $a$ 为终点且末边权严格小于 $w$ 的最长路径，然后接上当前边：

随后用 $dp$ 更新节点 $b$ 在权值 $w$ 处的最优值。每个节点分别离散化与它相关的边权，并使用维护前缀最大值的树状数组，即可完成单点取最大更新和前缀最大查询。所有节点离散化数组的总长度为 $O(m)$。

处理一条边时必须先查询、后更新。这样即使是自环，也不会让同一条边接到自己后面。查询到权值 $w$ 的前一位置，才能保证权值严格递增。

正确性证明

按输入顺序归纳。处理当前边 $(a,b,w)$ 前，假设各节点的数据结构已准确保存所有仅使用已处理边的路径最优值。任何以当前边结尾的合法路径，其前缀要么为空，要么终止于 $a$，且最后边权严格小于 $w$；这些前缀都已被树状数组记录。因此前缀查询得到其中最大长度，转移值恰是以当前边结尾的最长合法路径长度。

算法将该值写入节点 $b$ 的权值 $w$ 状态，且只做取最大，不会丢失已有更优路径，于是归纳不变式继续成立。先查后写排除了当前边作为自身前驱，严格前缀查询排除了等权前驱。最终每条合法路径都按其最后一条边被考虑，所有转移又只会生成首尾相接、编号和权值均严格递增的路径，所以全局最大值就是答案。

题解代码

import sys
from bisect import bisect_left


def query(tree, position):
    result = 0
    while position > 0:
        result = max(result, tree[position])
        position -= position & -position
    return result


def update(tree, position, value):
    size = len(tree) - 1
    while position <= size:
        tree[position] = max(tree[position], value)
        position += position & -position


def solve():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    edges = []
    values = [[] for _ in range(n + 1)]

    for _ in range(m):
        a, b, weight = map(int, input().split())
        edges.append((a, b, weight))
        values[a].append(weight)
        values[b].append(weight)

    for node in range(1, n + 1):
        values[node] = sorted(set(values[node]))

    trees = [[0] * (len(values[node]) + 1) for node in range(n + 1)]
    answer = 0

    for a, b, weight in edges:
        source_position = bisect_left(values[a], weight) + 1
        current = query(trees[a], source_position - 1) + 1

        target_position = bisect_left(values[b], weight) + 1
        update(trees[b], target_position, current)
        answer = max(answer, current)

    print(answer)


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：$O(m\log m)$，离散化排序以及每条边的一次查询和一次更新均在此界内。

空间复杂度：$O(n+m)$，保存边、各节点的离散化权值和树状数组。

易错点

• 必须按输入顺序转移，不能按权值重新排序边。
• 权值要求严格递增，因此查询位置是当前权值离散化位置的前一位。
• 自环和重边均可能出现；务必先查询再更新，防止一条自环边使用自己形成转移。
• 边权可以为 $0$，不能把零误当成“没有状态”。

第 4 题：机房维护

题意

有 $n$ 个维护任务，第 $i$ 个任务的开始时间、结束时间和收益分别为 $s_i,e_i,v_i$，占用半开区间 $[s_i,e_i)$。同一时刻只能执行一个任务，每个任务至多选择一次。

若一个任务在时刻 $t$ 结束，另一个任务恰在时刻 $t$ 开始，两者不冲突。求可获得的最大总收益。

输入输出

第一行输入整数 $n$。接下来 $n$ 行，每行输入三个整数 $s,e,v$。任务在输入中不保证有序。

数据范围：$1 \leq n \leq 200000$，$0 \leq s<e \leq 1000000000$，$1 \leq v \leq 1000000000$。答案可能超过 32 位整数范围。

输出一个整数，表示最大总收益。

样例

输入

5
1 3 50
2 5 40
4 6 70
6 7 30
7 9 60

输出

210

选择 $(1,3)$、$(4,6)$、$(6,7)$、$(7,9)$ 四个任务，收益为 $50+70+30+60=210$。

思路

这是加权区间调度。先将任务按结束时间升序排序，这样与当前任务兼容的已考虑任务必然构成排序后的一个前缀。

设 $dp_i$ 表示只考虑排序后前 $i$ 个任务时的最大收益，且 $dp_0=0$。对第 $i$ 个任务 $(s_i,e_i,v_i)$：

• 不选择它，收益为 $dp_{i-1}$；
• 选择它，在结束时间数组中二分找到最后一个满足 $e_j \leq s_i$ 的任务。设兼容前缀含 $j$ 个任务，则收益为 $dp_j+v_i$。

因此

使用 bisect_right 才会把结束时间恰好等于当前开始时间的任务包含进兼容前缀。

正确性证明

按照结束时间排序后，考虑前 $i$ 个任务的任意最优方案。若方案不选第 $i$ 个任务，它完全由前 $i-1$ 个任务组成，收益不超过 $dp_{i-1}$。若方案选择第 $i$ 个任务，其余所选任务的结束时间都不超过 $s_i$，因此全部位于二分得到的兼容前缀中，最优收益不超过 $dp_j+v_i$。

反过来，$dp_{i-1}$ 对应的方案不选择当前任务，显然合法；兼容前缀最优方案中的任务均在 $s_i$ 前结束，所以接上当前任务后仍无重叠，$dp_j+v_i$ 也可实现。两种情况取最大便得到前 $i$ 个任务的最优值。归纳至 $i=n$，所得即全局最大收益。

题解代码

import sys
from bisect import bisect_right


def solve():
    input = sys.stdin.readline
    n = int(input())
    tasks = []

    for _ in range(n):
        start, end, value = map(int, input().split())
        tasks.append((end, start, value))

    tasks.sort(key=lambda task: task[0])
    ends = [task[0] for task in tasks]
    dp = [0] * (n + 1)

    for i, (end, start, value) in enumerate(tasks, 1):
        compatible_count = bisect_right(ends, start, 0, i - 1)
        dp[i] = max(dp[i - 1], dp[compatible_count] + value)

    print(dp[n])


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：$O(n\log n)$，排序与每个任务的一次二分查找占主导。

空间复杂度：$O(n)$，用于保存排序后的任务、结束时间数组和动态规划数组。

易错点

• 任务必须按结束时间排序，不能按开始时间排序后直接套用该状态转移。
• 端点相接不冲突，应使用 bisect_right 查找结束时间不大于当前开始时间的前缀。
• 二分范围只需覆盖当前任务之前的部分，代码用右边界 i - 1 明确限制。
• 最大收益可达 $2\times10^{14}$；Python 整数不会溢出，其他语言需使用 64 位整数。