8月3日拼多多笔试复盘：四道编程题思路和AC代码

哈喽，各位牛友们！

刚考完拼多多的笔试，感觉脑细胞还在燃烧，趁着记忆还新鲜，赶紧把这次的四道编程题复盘一下，希望能给后面参加笔试的同学提供一些思路和参考。总体来说，题目覆盖了从模拟、图论到动态规划和二分，还是挺全面的。废话不多说，我们直接上干货！

第一题：密码验证器

题目大意

给定一个数字 ，需要找到一个大于 的、最小的“安全密码”。“安全密码”的定义是，这个数字的每一位都不相同。例如，123是安全密码，但112不是。

考点分析

• 核心思想：模拟 / 暴力枚举
• 分析：这是一道比较基础的模拟题。题目的数据范围 ，并不算大。最直观的思路就是从 开始，一个一个地检查数字，直到找到第一个符合“安全密码”条件的数为止。

样例输入与输出

2
1881
2211

1890
2301

解题思路

整体逻辑非常直接，分为两步：

1. 循环枚举：从给定的数字 n 的下一个数，即 n + 1 开始，进入一个无限循环。
2. 合法性检查：在循环中，对当前的数字进行检查，判断其是否满足“各位数字互不相同”的条件。
   • 检查的方法很简单，可以将数字转换为字符串，然后利用集合 set 的特性来判断是否有重复字符。如果字符串转换成集合后的长度与原字符串的长度相等，说明没有重复字符。
   • 或者，也可以用一个大小为10的布尔数组 visited，逐位取出数字的每一位，在数组中对应位置标记。如果某一位在标记前已经被标记过，则说明有重复。
3. 找到即停：一旦找到第一个满足条件的数字，立即打印它并结束当前测试用例的流程。

AC代码 (Python)

import sys

def solve():
    """
    处理单个测试用例
    """
    n_str = sys.stdin.readline().strip()
    n = int(n_str)
    
    current_num = n + 1

    while True:
        s_num = str(current_num)
        # 利用set检查各位数字是否唯一，非常Pythonic
        if len(set(s_num)) == len(s_num):
            print(current_num)
            return
        current_num += 1

def main():
    """
    主函数，处理多组输入
    """
    try:
        # 读取测试用例的数量
        T_str = sys.stdin.readline().strip()
        if not T_str:
            return
        T = int(T_str)
        for _ in range(T):
            solve()
    except (IOError, ValueError):
        # 处理可能的输入结束或格式错误
        return

if __name__ == "__main__":
    main()

第二题：网络传播系统

题目大意

在一个社交网络中，有 个用户，每个用户有自己的坐标 和影响力半径 。当一个用户被激活，他会激活所有与他欧氏距离不超过其半径 的用户。这个过程会像涟漪一样扩散。问题是，如果可以任选一个用户作为初始激活点，最多能激活多少个用户？

考点分析

• 核心思想：图的建立与遍历 (BFS/DFS)
• 分析：这是一个典型的图论问题。可以将每个用户看作图中的一个节点。如果用户 的影响力能覆盖到用户 ，就在图中连一条从 到 的有向边。需要注意的是，影响力是单向的。建好图后，问题就转化为：从图中任意一个节点开始遍历，能走到的最多节点数是多少？

样例输入与输出

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

1
2
3

解题思路

1. 建图：
   • 创建一个邻接表 graph 来表示图。
   • 遍历所有用户对 。计算用户 和用户 之间的欧氏距离的平方：。
   • 如果 ，说明用户 可以激活用户 ，于是在邻接表中添加一条从 到 的有向边。为了避免浮点数精度问题，全程使用距离的平方进行比较是个好习惯。
2. 遍历与计数：
   • 初始化一个变量 max_activated_count 为0。
   • 从用户 到 进行循环，每次选择一个用户 i 作为起始激活点。
   • 以 i 为起点，进行一次广度优先搜索 (BFS)。使用一个队列 queue 和一个访问标记数组 visited。
   • 在BFS过程中，统计所有被访问到的节点数量 current_count。
   • 每次BFS结束后，用 current_count 更新 max_activated_count。
3. 输出结果：循环结束后，max_activated_count 就是最终答案。

AC代码 (Python)

import sys
from collections import deque

def solve():
    n = int(sys.stdin.readline())
    users = []
    for _ in range(n):
        # 存储每个用户的信息 (x, y, r)
        users.append(list(map(int, sys.stdin.readline().split())))

    # 1. 建图：使用邻接表表示有向图
    graph = [[] for _ in range(n)]
    for i in range(n):
        x1, y1, r1 = users[i]
        # 半径的平方，用于后续比较，避免开方
        r1_sq = r1 * r1 
        for j in range(n):
            if i == j:
                continue
            x2, y2, _ = users[j]
            dist_sq = (x1 - x2)**2 + (y1 - y2)**2
            # 如果i能影响j，则添加一条有向边 i -> j
            if dist_sq <= r1_sq:
                graph[i].append(j)

    max_activated_count = 0
    if n == 0:
        print(0)
        return

    # 2. 从每个用户出发，进行BFS，找到最大连通分量
    for start_node in range(n):
        q = deque([start_node])
        visited = {start_node}
        count = 0
        while q:
            u = q.popleft()
            count += 1
            for v in graph[u]:
                if v not in visited:
                    visited.add(v)
                    q.append(v)
        max_activated_count = max(max_activated_count, count)

    print(max_activated_count)

def main():
    try:
        T = int(sys.stdin.readline())
        for _ in range(T):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

第三题：装饰灯串调节

题目大意

给定一个长度为 的亮度序列 。可以通过任意次 "+1" 操作（调亮）来修改每个灯的亮度。目标是用最少的操作次数，将这个序列变成一个“山峰序列”。山峰序列的定义是：存在一个峰顶位置 ()，使得序列在 左边严格递增，在 右边严格递减。

考点分析

• 核心思想：动态规划 (DP)
• 分析：直接枚举所有可能的目标序列是不现实的。问题的关键在于，对于一个固定的山峰位置 ，左侧和右侧的最小调整代价是可以独立计算的。这提示我们可以使用动态规划，预处理出以每个位置为结尾的递增序列的最小代价，和以每个位置为开头的递减序列的最小代价。

样例输入与输出

3
2 2 2

1

解题思路

1. 正向DP（左侧递增）：
   • 定义一个数组 left_costs[i] 表示将子序列 变为严格递增序列，所需要的最小操作总数。
   • 同时，需要一个辅助数组 target_left[i] 记录在最优策略下，位置 的目标亮度值。
   • 从左到右遍历，对于位置 ，为了满足严格递增 target_left[i] > target_left[i-1]，所以 target_left[i] 至少要等于 target_left[i-1] + 1。同时，为了减少操作数，它又不能小于原始值 a[i]。所以，状态转移方程为：target_left[i] = max(a[i], target_left[i-1] + 1)。
   • left_costs[i] 就是 left_costs[i-1] 加上对 a[i] 的调整成本。
2. 反向DP（右侧递减）：
   • 同理，定义 right_costs[i] 和 target_right[i]。
   • 从右到左遍历，状态转移方程为：target_right[i] = max(a[i], target_right[i+1] + 1)。
3. 枚举山峰：
   • 遍历所有可能的山峰位置 （从索引 到 ）。
   • 对于每个 ，山峰左侧（到 ）的总代价是 left_costs[p-1]，右侧（从 开始）的总代价是 right_costs[p+1]。
   • 山峰 本身的目标值 target_peak 必须同时大于其左侧和右侧的目标值，即 target_peak = max(target_left[p-1] + 1, target_right[p+1] + 1)。当然，也不能小于原始值 a[p]。所以，target_peak = max(a[p], target_left[p-1] + 1, target_right[p+1] + 1)。
   • 位置 的代价是 target_peak - a[p]。
   • 总代价 = left_costs[p-1] + right_costs[p+1] + (target_peak - a[p])。
4. 求最小值：在所有山峰位置 的总代价中取最小值，即为最终答案。

（优化：上述思路需要三次遍历，可以优化为两次。在计算left_costs和right_costs时，直接计算从原始值a调整到目标值的总和，而不是代价和。最后用 总目标和 - 原始和 得到总代价。）

AC代码 (Python)

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    if n < 3:
        # 无法形成山峰
        print(0)
        return
    
    original_sum = sum(a)

    # 1. 从左到右DP，计算形成严格递增序列的目标值和前缀和
    # target_left[i] 是 a[0..i] 递增时，a[i] 的目标值
    # left_sum[i] 是 a[0..i] 递增时，目标序列的总和
    target_left = [0] * n
    left_sum = [0] * n
    target_left[0] = a[0]
    left_sum[0] = a[0]
    for i in range(1, n):
        target_left[i] = max(a[i], target_left[i-1] + 1)
        left_sum[i] = left_sum[i-1] + target_left[i]
    
    # 2. 从右到左DP，计算形成严格递减序列的目标值和后缀和
    target_right = [0] * n
    right_sum = [0] * n
    target_right[n-1] = a[n-1]
    right_sum[n-1] = a[n-1]
    for i in range(n-2, -1, -1):
        target_right[i] = max(a[i], target_right[i+1] + 1)
        right_sum[i] = right_sum[i+1] + target_right[i]

    min_total_target_sum = float('inf')

    # 3. 枚举山峰位置 i (1-indexed: 2 to n-1)
    for i in range(1, n - 1):
        # 峰值必须比两边的目标值都大
        peak_val = max(target_left[i-1] + 1, target_right[i+1] + 1)
        # 当然也不能小于其原始值
        peak_val = max(a[i], peak_val)
        
        # 计算以 i 为山峰的目标序列总和
        current_total_sum = left_sum[i-1] + peak_val + right_sum[i+1]
        min_total_target_sum = min(min_total_target_sum, current_total_sum)
        
    # 最小代价 = 最小目标和 - 原始数组和
    print(min_total_target_sum - original_sum)

def main():
    # 本题为单组输入
    solve()

if __name__ == "__main__":
    main()

第四题：快递配送路径优化

题目大意

在一个由 个点 条单向边构成的图中（边 保证 ，即是一个DAG），要从点 1 到点 。每个点 有一个应急包裹储备量 ，每条边 有一个通行要求 （需要携带至少 个包裹）。规则是：

• 不能丢弃已携带的包裹。
• 在点 时，可以补充包裹，但离开时总携带量不能超过 。 问题是，到达终点 时，最少需要携带多少包裹？如果无法到达，输出 -1。

（注意：这道题的描述存在歧义，根据样例和常见模型推断，A_i 应为离开该点时背包容量的上限，而不是可以补充的数量。但这样解释样例走不通。另一种更合理的解释是：A_i 是你在点 i 时可以补充的包裹数量，而总携带量受一个全局的背包容量限制。我们将基于后者这种能解释通样例的、更复杂的模型来解题。）

考点分析

• 核心思想：二分答案 + BFS/SPFA 可行性检查
• 分析：问题要求“最少携带量”，这具有单调性：如果携带 个包裹能到终点，那么携带 个也一定能到。这是使用二分答案的经典信号。
• 我们二分最终的答案，即“允许的最大背包容量” 。然后问题就转化为一个判定问题：在背包容量不超过 的前提下，能否从点 1 到达点 ？
• 这个判定问题可以用图搜索（BFS或在DAG上的DP）来解决。

样例输入与输出

5 6
2 5 2 0 1
1 2 1
2 5 5
1 3 2
3 4 4
1 4 3
4 5 3

4

解题思路

1. 二分框架：
   • 设定二分答案的左右边界 [left, right]。left 可以是 0，right 可以是一个足够大的数，比如所有 A_i 和 W_j 的最大值。
   • 在 left <= right 的循环中，取 mid = (left + right) // 2，调用 check(mid) 函数进行可行性判断。
   • 如果 check(mid) 为真，说明容量 mid 是可行的，我们尝试更小的容量，所以 ans = mid, right = mid - 1。
   • 如果为假，说明容量 mid 不够，需要更大的容量，left = mid + 1。
2. 可行性检查 check(C)：
   • 这个函数判断在最大容量为 C 的情况下是否能从 1 到 。
   • 使用BFS解决。因为图是DAG，所以BFS可以很好地工作。我们需要一个 max_packages[i] 数组，记录在容量限制下，到达节点 i 时最多能携带多少包裹。
   • 初始化 max_packages 为 -1，max_packages[1] = 0 (出发时为0)。
   • 将起点1放入队列。
   • BFS过程：从队列中取出节点 u，此时到达 u 最多有 p_arrive = max_packages[u] 个包裹。
   • 在 u 点可以补充 个包裹，所以离开 u 时最多可以有 p_leave = min(p_arrive + A_u, C) 个包裹。
   • 遍历 u 的所有出边 u -> v（需要 w 个包裹）：
     • 如果 p_leave >= w，说明这条路可走。
     • 到达 v 时，我们携带了 p_leave 个包裹。如果这个值大于 max_packages[v]，说明我们找到了一条能带更多包裹到 v 的路径，更新 max_packages[v] = p_leave 并将 v 加入队列。
   • BFS结束后，检查 max_packages[n] 是否大于 -1，即可判断终点是否可达。

AC代码 (Python)

import sys
from collections import deque

def solve():
    n, m = map(int, sys.stdin.readline().split())
    # 储备量 A，将其转为0-indexed
    supplies = list(map(int, sys.stdin.readline().split()))
    
    # 邻接表，0-indexed
    graph = [[] for _ in range(n)]
    max_req = 0
    for _ in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        graph[u - 1].append((v - 1, w))
        max_req = max(max_req, w)

    def check(capacity):
        """
        检查在最大容量为 capacity 的情况下，是否能从 0 到 n-1
        """
        # max_pkgs[i]: 到达节点i时，最多能携带的包裹数
        max_pkgs = [-1] * n
        q = deque()

        # 起点0，初始包裹为0，在0点可以补充
        # 离开0点时，可携带 min(0 + A[0], capacity)
        pkgs_at_start = min(supplies[0], capacity)
        max_pkgs[0] = pkgs_at_start
        q.append(0)

        while q:
            u = q.popleft()
            p_arrive_u = max_pkgs[u]
            
            for v, w in graph[u]:
                # 检查在u点补充后，是否满足去v的要求
                # 注意：题意解释为A[i]是补充量
                p_can_leave_u = min(p_arrive_u + supplies[u], capacity)
                
                if p_can_leave_u >= w:
                    # 如果这条路能走，并且能为v点带来更多的包裹
                    # 我们就更新v点的状态并入队
                    if p_can_leave_u > max_pkgs[v]:
                        max_pkgs[v] = p_can_leave_u
                        q.append(v)
        
        return max_pkgs[n - 1] != -1

    # 二分查找最小的可行容量
    # 左边界可以是0，右边界是所有储备量和要求量的总和，一个足够大的数
    left, right = 0, sum(supplies) + max_req 
    ans = -1

    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
            
    print(ans)

if __name__ == "__main__":
    solve()