拼多多 2026-8-23 笔试真题 - 算法岗

import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    m = data[0]
    lights = data[1:1 + m]

    presses = 0
    for state in lights:
        current = state ^ (presses & 1)
        if current == 0:
            presses += 1

    print(presses)


if __name__ == "__main__":
    solve()

import sys


def feasible(heights, operations, width, target):
    n = len(heights)
    expire = [0] * (n + 1)
    active = 0
    used = 0

    for i, height in enumerate(heights):
        active += expire[i]
        current = height + active
        if current >= target:
            continue

        need = target - current
        used += need
        if used > operations:
            return False

        active += need
        end = min(n, i + width)
        expire[end] -= need

    return True


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    length, operations, width = data[:3]
    heights = data[3:3 + length]

    low = min(heights)
    high = low + operations
    while low < high:
        middle = (low + high + 1) // 2
        if feasible(heights, operations, width, middle):
            low = middle
        else:
            high = middle - 1

    print(low)


if __name__ == "__main__":
    solve()

import heapq
import sys


def solve():
    input = sys.stdin.buffer.readline
    station_count, edge_count, capacity = map(int, input().split())
    charge_time = [0] + list(map(int, input().split()))
    graph = [[] for _ in range(station_count + 1)]

    for _ in range(edge_count):
        x, y, energy, travel_time = map(int, input().split())
        if energy <= capacity:
            graph[x].append((y, energy, travel_time))
            graph[y].append((x, energy, travel_time))

    width = capacity + 1
    infinity = 10**30
    distance = [infinity] * ((station_count + 1) * width)
    start = width + capacity
    distance[start] = 0
    heap = [(0, start)]

    while heap:
        current_time, state = heapq.heappop(heap)
        if current_time != distance[state]:
            continue

        station, battery = divmod(state, width)
        if station == station_count:
            print(current_time)
            return

        if battery < capacity:
            next_state = state + 1
            next_time = current_time + charge_time[station]
            if next_time < distance[next_state]:
                distance[next_state] = next_time
                heapq.heappush(heap, (next_time, next_state))

        for neighbor, energy, travel_time in graph[station]:
            if battery < energy:
                continue
            next_state = neighbor * width + battery - energy
            next_time = current_time + travel_time
            if next_time < distance[next_state]:
                distance[next_state] = next_time
                heapq.heappush(heap, (next_time, next_state))

    print(-1)


if __name__ == "__main__":
    solve()

import sys


def solve():
    input = sys.stdin.buffer.readline
    variable_count, record_count = map(int, input().split())
    node_count = 2 * variable_count

    parent = list(range(node_count))
    size = [1] * node_count
    potential = [0] * node_count

    def find(x):
        path = []
        current = x
        while parent[current] != current:
            path.append(current)
            current = parent[current]
        root = current

        total = 0
        for node in reversed(path):
            total += potential[node]
            potential[node] = total
            parent[node] = root
        return root

    def unite(a, b, difference):
        # value(a) - value(b) = difference
        root_a = find(a)
        root_b = find(b)
        if root_a == root_b:
            return potential[a] - potential[b] == difference

        if size[root_a] < size[root_b]:
            parent[root_a] = root_b
            potential[root_a] = potential[b] + difference - potential[a]
            size[root_b] += size[root_a]
        else:
            parent[root_b] = root_a
            potential[root_b] = potential[a] - difference - potential[b]
            size[root_a] += size[root_b]
        return True

    consistent = True
    for _ in range(record_count):
        operation, raw_u, raw_v, raw_w = input().split()
        u = int(raw_u) - 1
        v = int(raw_v) - 1
        w = int(raw_w)

        if not consistent:
            continue

        if operation == b"D":
            first_ok = unite(u, v, w)
            second_ok = unite(u + variable_count, v + variable_count, -w)
        else:
            first_ok = unite(u, v + variable_count, w)
            second_ok = unite(u + variable_count, v, -w)
        consistent = first_ok and second_ok

    if not consistent:
        print("NO")
        print(-1)
        return

    pinned = [False] * node_count
    for i in range(variable_count):
        root = find(i)
        mirror_root = find(i + variable_count)
        if root != mirror_root:
            continue

        # value(i) - value(i') = x_i - (-x_i) = 2*x_i。
        delta = potential[i] - potential[i + variable_count]
        if delta % 2 != 0:
            print("NO")
            print(-1)
            return
        pinned[root] = True

    free_roots = 0
    for node in range(node_count):
        root = find(node)
        if root == node and not pinned[root]:
            free_roots += 1

    print("YES")
    print(free_roots // 2)


if __name__ == "__main__":
    solve()