今天练习的是拼多多最新机考笔试题4题。

各大厂真题都整理了近两年的机考题，题库里面有详细思路和答案~

肥猫学长也提供机考辅导助攻（100%通过率）和面试辅导欢迎咨询。

微信号：jackwwang8

目前已经整理的题库有如下：如果有需要可以加我微信获取哦～

拼多多-27届秋招题目8.23

第1题 展廊灯带后缀点亮

题目描述

展廊中的灯带被分成段，从左到右编号为到。每段只有两种状态：表示点亮，表示熄灭。

值班员从左向右依次经过所有灯段。走到第段时，可以按下一次该位置的总控按钮，使区间中所有灯段的状态翻转，即变成，变成。每个位置最多操作一次，并且走过后不能返回。

请计算使全部灯段最终都为所需的最少操作次数。

输入描述

数据范围：

输出描述

输出一个非负整数，表示最少操作次数。

样例1

输入：

11

输出：

0

样例2

输入：

30 1 0

输出：

3

说明：依次在第段操作，状态会变为 1 0 1、1 1 0、1 1 1。

样例3

输入：

40 0 1 1

输出：

2

解题思路

扫描到位置时，左侧所有位置已经无法再修改。若第段此刻仍为，就必须在这里进行一次后缀翻转；若已经为，则不应操作，否则会平白增加次数。

不需要真的修改整个后缀。只需记录此前进行了多少次翻转的奇偶性：

可以用得到当前位置的真实状态。若结果为，答案加一并翻转 flip。由于每个位置的选择都是被当前状态唯一决定的，所得方案自然最优。

复杂度分析

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

import sysdef minimum_switch_count(states):    operation_count = 0    reversed_state = 0    for initial_state in states:        actual_state = initial_state ^ reversed_state        if actual_state == 0:            operation_count += 1            reversed_state ^= 1    return operation_countdef main():    input_data = sys.stdin.readline    input_data()    states = list(map(int, input_data().split()))    print(minimum_switch_count(states))if __name__ == "__main__":    main()

第2题 护栏补强

题目描述

一条护栏被分成段，第段的初始高度为。养护队最多可以施工次。

每次施工必须选择一个长度不超过的连续区间，并将区间内所有护栏段的高度增加。

请计算经过不超过次施工后，整条护栏最小高度能够达到的最大值。

输入描述

数据范围：

输出描述

输出一个整数，表示补强后最小高度的最大可能值。

样例1

输入：

4 2 23 1 1 3

输出：

3

说明：两次施工都覆盖中间区间，最终高度为 3 3 3 3。

样例2

输入：

1 10 15

输出：

15

样例3

输入：

3 0 24 2 8

输出：

2

解题思路

答案具有单调性：如果能把所有位置都提升到高度，那么任何不超过的目标高度也一定可行。因此可以二分最终的最小高度。

对给定目标，从左向右检查每个位置。设此前区间操作对当前位置累计增加了，若当前实际高度仍低于，缺口为：

此时必须新增 need 次操作，并且让这些操作从当前位置开始、尽量向右覆盖段。这样既满足当前位置，又能尽可能帮助后面的护栏，不会使方案变差。

使用差分数组记录新增操作在何处失效，就能在线性时间内完成一次可行性检查。当累计操作数超过时，当前目标不可行。

初始最小高度记为。答案不可能小于，也不可能超过，在这个区间内二分即可。

复杂度分析

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

import sysdef can_achieve(heights, operation_limit, window, target):    length = len(heights)    expiration = [0] * (length + 1)    active_increase = 0    used_operations = 0    for index, height in enumerate(heights):        active_increase += expiration[index]        shortage = target - height - active_increase        if shortage <= 0:            continue        used_operations += shortage        if used_operations > operation_limit:            return False        active_increase += shortage        end = index + window        if end < length:            expiration[end] -= shortage    return Truedef maximum_minimum_height(heights, operation_limit, window):    left = min(heights)    right = left + operation_limit    while left < right:        middle = (left + right + 1) // 2        if can_achieve(            heights,            operation_limit,            window,            middle,        ):            left = middle        else:            right = middle - 1    return leftdef main():    input_data = sys.stdin.readline    _, operation_limit, window = map(int, input_data().split())    heights = list(map(int, input_data().split()))    print(maximum_minimum_height(heights, operation_limit, window))if __name__ == "__main__":    main()

第3题 驿站补给最短耗时

题目描述

巡检车需要从号驿站前往号驿站。沿线共有个驿站和条双向道路。

第条道路连接驿站与，经过它需要消耗格电量，并花费时间。车辆电池容量为，从号驿站出发时电量为满格，并且电量始终不能超过。

在第个驿站可以逐格充电，每增加一格电量需要花费时间。

请计算到达号驿站的最短时间；如果无法到达，输出 -1。

输入描述

数据范围：

输出描述

输出一个整数，表示到达号驿站的最短时间。无法到达时输出 -1。

样例1

输入：

4 3 52 1 9 31 2 3 42 3 3 53 4 2 6

输出：

18

样例2

输入：

2 1 31 11 2 4 10

输出：

-1

说明：道路需要消耗格电量，超过容量，因此无法通行。

样例3

输入：

3 2 40 5 11 2 2 32 3 2 4

输出：

7

解题思路

到达同一个驿站时，剩余电量不同会影响后续决策，因此不能只把驿站编号作为最短路状态。

将状态定义为，表示车辆位于驿站，当前剩余格电量。起点状态是，初始耗时为。

每个状态有两类转移：

所有转移代价都非负，因此可以在这张扩展状态图上运行 Dijkstra。第一次从优先队列中取出任意状态时，其距离就是最短时间。若队列耗尽仍未到达终点，则返回 -1。

复杂度分析

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

import heapqimport sysINFINITY = 10**30def minimum_travel_time(    station_count,    capacity,    charging_time,    graph,):    distance = [        [INFINITY] * (capacity + 1)        for _ in range(station_count + 1)    ]    distance[1][capacity] = 0    queue = [(0, 1, capacity)]    while queue:        elapsed, station, energy = heapq.heappop(queue)        if elapsed != distance[station][energy]:            continue        if station == station_count:            return elapsed        if energy < capacity:            charged_time = elapsed + charging_time[station]            if charged_time < distance[station][energy + 1]:                distance[station][energy + 1] = charged_time                heapq.heappush(                    queue,                    (charged_time, station, energy + 1),                )        for next_station, energy_cost, road_time in graph[station]:            if energy < energy_cost:                continue            next_energy = energy - energy_cost            arrival_time = elapsed + road_time            if arrival_time < distance[next_station][next_energy]:                distance[next_station][next_energy] = arrival_time                heapq.heappush(                    queue,                    (arrival_time, next_station, next_energy),                )    return -1def main():    input_data = sys.stdin.readline    station_count, road_count, capacity = map(        int,        input_data().split(),    )    charging_time = [0] + list(map(int, input_data().split()))    graph = [[] for _ in range(station_count + 1)]    for _ in range(road_count):        start, end, energy_cost, road_time = map(            int,            input_data().split(),        )        graph[start].append((end, energy_cost, road_time))        graph[end].append((start, energy_cost, road_time))    print(        minimum_travel_time(            station_count,            capacity,            charging_time,            graph,        )    )if __name__ == "__main__":    main()

第4题 和差方程最少标定

题目描述

计量室需要确定个样品的整数值。现有条记录，每条记录属于以下两种类型之一：

所有样品值必须是整数，可以为正数、负数或零。同一条记录中的两个下标允许相同。

首先判断所有记录是否存在一组整数解。如果存在，还要计算至少需要实测多少个样品，才能唯一确定全部个值。

输入描述

数据范围：

输出描述

样例1

输入：

2 2S 1 2 8D 1 2 2

输出：

YES0

样例2

输入：

1 1S 1 1 5

输出：

NO-1

说明：方程变成，不存在整数解。

样例3

输入：

3 2D 1 2 1D 2 3 1

输出：

YES1

解题思路

每个关系式都只含两个变量，并且变量系数只可能是或。可以使用带权并查集维护每个变量相对于所在连通块根变量的一次表达式：

其中。

将一条记录统一写成：

差关系对应，和关系对应。

若两个变量属于不同连通块，就将一个根连接到另一个根，并计算新的符号和偏移。若属于同一连通块，代入表达式后会得到以下情况：

一个连通块的根如果尚未被方程确定，就代表该块仍有一个自由变量，需要实测其中任意一个样品；已经被确定的块不需要实测。孤立点也是一个独立的自由连通块。

最终答案就是所有“根值尚未确定”的连通块数量。

复杂度分析

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

import sysclass EquationUnionFind:    def __init__(self, variable_count):        self.parent = list(range(variable_count + 1))        self.sign = [1] * (variable_count + 1)        self.offset = [0] * (variable_count + 1)        self.fixed_root_value = [None] * (variable_count + 1)    def find(self, variable):        path = []        current = variable        while self.parent[current] != current:            path.append(current)            current = self.parent[current]        root = current        for node in reversed(path):            direct_parent = self.parent[node]            old_sign = self.sign[node]            self.sign[node] = old_sign * self.sign[direct_parent]            self.offset[node] += old_sign * self.offset[direct_parent]            self.parent[node] = root        return root    def add_equation(self, first, second, second_coefficient, value):        first_root = self.find(first)        second_root = self.find(second)        first_sign = self.sign[first]        second_sign = self.sign[second]        first_offset = self.offset[first]        second_offset = self.offset[second]        remaining = (            value            - first_offset            - second_coefficient * second_offset        )        if first_root == second_root:            root_coefficient = (                first_sign                + second_coefficient * second_sign            )            if root_coefficient  0:                return remaining  0            if remaining % root_coefficient != 0:                return False            required_value = remaining // root_coefficient            known_value = self.fixed_root_value[first_root]            if known_value is not None and known_value != required_value:                return False            self.fixed_root_value[first_root] = required_value            return True        self.parent[first_root] = second_root        self.sign[first_root] = (            -first_sign * second_coefficient * second_sign        )        self.offset[first_root] = first_sign * remaining        first_fixed = self.fixed_root_value[first_root]        second_fixed = self.fixed_root_value[second_root]        if first_fixed is not None and second_fixed is not None:            return first_fixed == (                self.sign[first_root] * second_fixed                + self.offset[first_root]            )        if first_fixed is not None:            self.fixed_root_value[second_root] = self.sign[first_root] * (                first_fixed - self.offset[first_root]            )        return Truedef solve(variable_count, equations):    union_find = EquationUnionFind(variable_count)    for relation, first, second, value in equations:        second_coefficient = -1 if relation == "D" else 1        if not union_find.add_equation(            first,            second,            second_coefficient,            value,        ):            return "NO", -1    visited_roots = set()    measurement_count = 0    for variable in range(1, variable_count + 1):        root = union_find.find(variable)        if root in visited_roots:            continue        visited_roots.add(root)        if union_find.fixed_root_value[root] is None:            measurement_count += 1    return "YES", measurement_countdef main():    input_data = sys.stdin.readline    variable_count, equation_count = map(int, input_data().split())    equations = []    for _ in range(equation_count):        parts = input_data().split()        equations.append(            (                parts[0],                int(parts[1]),                int(parts[2]),                int(parts[3]),            )        )    status, measurement_count = solve(variable_count, equations)    print(status)    print(measurement_count)if __name__ == "__main__":    main()