华为 9.4 笔试真题 - 研发岗

import sys
from functools import lru_cache


ASCII_TILES = "123456789ABCDEFGHIabcdefghi"


def tile_index(ch):
    if "1" <= ch <= "9":
        return ord(ch) - ord("1")
    if "a" <= ch <= "i":
        return 9 + ord(ch) - ord("a")
    return 18 + ord(ch) - ord("A")


@lru_cache(maxsize=None)
def can_form_melds(state):
    total = sum(state)
    if total == 0:
        return True
    if total % 3 != 0:
        return False

    first = next(i for i, count in enumerate(state) if count)
    counts = list(state)

    if counts[first] >= 3:
        counts[first] -= 3
        if can_form_melds(tuple(counts)):
            return True
        counts[first] += 3

    if first + 2 < 9 and counts[first + 1] and counts[first + 2]:
        counts[first] -= 1
        counts[first + 1] -= 1
        counts[first + 2] -= 1
        if can_form_melds(tuple(counts)):
            return True

    return False


def is_winning(counts):
    used_suits = sum(
        any(counts[start:start + 9]) for start in (0, 9, 18)
    )
    if used_suits > 2:
        return False

    for pair in range(27):
        if counts[pair] < 2:
            continue
        counts[pair] -= 2
        valid = all(
            can_form_melds(tuple(counts[start:start + 9]))
            for start in (0, 9, 18)
        )
        counts[pair] += 2
        if valid:
            return True
    return False


def solve():
    hand = sys.stdin.buffer.readline().strip().decode()
    counts = [0] * 27
    for ch in hand:
        counts[tile_index(ch)] += 1

    answer = []
    for ch in ASCII_TILES:
        index = tile_index(ch)
        if counts[index] == 4:
            continue
        counts[index] += 1
        if is_winning(counts):
            answer.append(ch)
        counts[index] -= 1

    print("".join(answer) if answer else -1)


if __name__ == "__main__":
    solve()

import heapq
import re
import sys


DEPENDENCY = re.compile(r"^(\d+)(?:(>=|<=|>|<)(\d+)\.(\d+)\.(\d+))?$")


def parse_version(text):
    return tuple(map(int, text.split(".")))


def version_satisfies(actual, operator, required):
    if operator == ">=":
        return actual >= required
    if operator == "<=":
        return actual <= required
    if operator == ">":
        return actual > required
    if operator == "<":
        return actual < required
    return True


def solve():
    input = sys.stdin.buffer.readline
    m = int(input())
    versions = [None] * m
    dependencies = [[] for _ in range(m)]

    for _ in range(m):
        parts = input().split()
        package = int(parts[0])
        versions[package] = parse_version(parts[1].decode())
        for raw in parts[2:]:
            match = DEPENDENCY.fullmatch(raw.decode())
            target = int(match.group(1))
            operator = match.group(2) or ""
            required = None
            if operator:
                required = tuple(int(match.group(i)) for i in (3, 4, 5))
            dependencies[package].append((target, operator, required))

    for package in range(m):
        for target, operator, required in dependencies[package]:
            if not version_satisfies(versions[target], operator, required):
                print(-1)
                return

    graph = [[] for _ in range(m)]
    indegree = [0] * m
    for package in range(m):
        for target, _, _ in dependencies[package]:
            graph[target].append(package)
            indegree[package] += 1

    ready = [package for package in range(m) if indegree[package] == 0]
    heapq.heapify(ready)
    order = []

    while ready:
        package = heapq.heappop(ready)
        order.append(package)
        for dependent in graph[package]:
            indegree[dependent] -= 1
            if indegree[dependent] == 0:
                heapq.heappush(ready, dependent)

    if len(order) != m:
        print(-2)
    else:
        print(*order)


if __name__ == "__main__":
    solve()

import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    h, w = data[0], data[1]
    values = [
        data[2 + row * w:2 + (row + 1) * w]
        for row in range(h)
    ]

    negative_infinity = -10**30
    dp = [[negative_infinity] * h for _ in range(h)]
    dp[0][0] = values[0][0] + values[0][w - 1]

    for step in range(1, h + w - 1):
        next_dp = [[negative_infinity] * h for _ in range(h)]
        low_row = max(0, step - (w - 1))
        high_row = min(h - 1, step)

        for row_a in range(low_row, high_row + 1):
            col_a = step - row_a
            for row_b in range(low_row, high_row + 1):
                col_b = w - 1 - (step - row_b)

                if row_a == row_b and col_a == col_b:
                    continue

                best_previous = negative_infinity
                for down_a in (0, 1):
                    previous_a = row_a - down_a
                    if previous_a < 0:
                        continue
                    for down_b in (0, 1):
                        previous_b = row_b - down_b
                        if previous_b >= 0:
                            best_previous = max(
                                best_previous,
                                dp[previous_a][previous_b],
                            )

                if best_previous != negative_infinity:
                    next_dp[row_a][row_b] = (
                        best_previous
                        + values[row_a][col_a]
                        + values[row_b][col_b]
                    )

        dp = next_dp

    print(dp[h - 1][h - 1])


if __name__ == "__main__":
    solve()