拼多多 7.19 笔试真题 - 通用

import sys
input = sys.stdin.readline


def solve_case(n, before, after):
    left = -1
    right = -1

    for i in range(n):
        if before[i] != after[i]:
            if left == -1:
                left = i
            right = i

    target = after[left]
    can_expand_left = left > 0 and after[left - 1] == target
    can_expand_right = right + 1 < n and after[right + 1] == target

    if can_expand_left or can_expand_right:
        return "-1"
    return f"{left + 1} {right + 1} {target}"


def solve():
    test_count = int(input())
    answers = []

    for _ in range(test_count):
        n = int(input())
        before = input().strip()
        after = input().strip()
        answers.append(solve_case(n, before, after))

    print("\n".join(answers))


solve()

import sys
from collections import deque
input = sys.stdin.readline


def min_batches(n, max_drop, max_gap, capacity, lengths):
    lengths.sort()

    first_valid = [0] * n
    left = 0
    for right in range(n):
        while lengths[right] - lengths[left] > max_gap:
            left += 1
        first_valid[right] = left

    inf = n + 1
    previous = [inf] * (n + 1)
    answer = inf

    for discarded in range(min(max_drop, n) + 1):
        current = [inf] * (n + 1)
        if discarded == 0:
            current[0] = 0

        window = deque()

        for size in range(1, n + 1):
            prefix = size - 1

            while window and current[window[-1]] >= current[prefix]:
                window.pop()
            window.append(prefix)

            lower = max(first_valid[size - 1], size - capacity)
            while window[0] < lower:
                window.popleft()

            keep_last = current[window[0]] + 1
            drop_last = previous[size - 1] if discarded > 0 else inf
            current[size] = min(keep_last, drop_last)

        answer = min(answer, current[n])
        previous = current

    return answer


def solve():
    test_count = int(input())
    answers = []

    for _ in range(test_count):
        n, max_drop, max_gap, capacity = map(int, input().split())
        lengths = list(map(int, input().split()))
        answers.append(str(min_batches(n, max_drop, max_gap, capacity, lengths)))

    print("\n".join(answers))


solve()

import sys
from bisect import bisect_left
input = sys.stdin.readline


def solve():
    n = int(input())
    transformed = []

    for _ in range(n):
        time, position = map(int, input().split())
        transformed.append((time + position, time - position))

    transformed.sort(key=lambda point: (point[0], -point[1]))

    tails = []
    for _, value in transformed:
        index = bisect_left(tails, value)
        if index == len(tails):
            tails.append(value)
        else:
            tails[index] = value

    print(len(tails))


solve()

import sys
from collections import deque
input = sys.stdin.readline


def solve_case(n, state, edges):
    if sum(state) % 2 == 1:
        return "-1 0"

    graph = [[] for _ in range(n)]
    degree = [0] * n

    for edge_id, (u, v, _) in enumerate(edges):
        graph[u].append((v, edge_id))
        graph[v].append((u, edge_id))
        degree[u] += 1
        degree[v] += 1

    removed = [False] * n
    queue = deque(i for i in range(n) if degree[i] == 1)

    while queue:
        node = queue.popleft()
        removed[node] = True

        for neighbor, _ in graph[node]:
            if not removed[neighbor]:
                degree[neighbor] -= 1
                if degree[neighbor] == 1:
                    queue.append(neighbor)

    on_cycle = [not flag for flag in removed]
    cycle_edge = [on_cycle[u] and on_cycle[v] for u, v, _ in edges]
    skipped_edge = next(i for i, flag in enumerate(cycle_edge) if flag)

    parent = [-2] * n
    parent_edge = [-1] * n
    order = []
    parent[0] = -1
    queue = deque([0])

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor, edge_id in graph[node]:
            if edge_id == skipped_edge or parent[neighbor] != -2:
                continue
            parent[neighbor] = node
            parent_edge[neighbor] = edge_id
            queue.append(neighbor)

    remaining = state[:]
    selected = [False] * n
    base_cost = 0

    for node in reversed(order):
        if parent[node] == -1:
            continue
        if remaining[node] == 1:
            edge_id = parent_edge[node]
            selected[edge_id] = True
            base_cost += edges[edge_id][2]
            remaining[node] = 0
            remaining[parent[node]] ^= 1

    selected_cycle_cost = sum(
        edges[i][2]
        for i in range(n)
        if cycle_edge[i] and selected[i]
    )
    unselected_cycle_cost = sum(
        edges[i][2]
        for i in range(n)
        if cycle_edge[i] and not selected[i]
    )

    other_cost = base_cost - selected_cycle_cost + unselected_cycle_cost

    if base_cost < other_cost:
        return f"{base_cost} 1"
    if other_cost < base_cost:
        return f"{other_cost} 1"
    return f"{base_cost} 2"


def solve():
    test_count = int(input())
    answers = []

    for _ in range(test_count):
        n = int(input())
        state = list(map(int, input().split()))
        edges = []

        for _ in range(n):
            u, v, cost = map(int, input().split())
            edges.append((u - 1, v - 1, cost))

        answers.append(solve_case(n, state, edges))

    print("\n".join(answers))


solve()