华为 9.4 笔试真题 - AI 岗

import math
import sys


def merge_stats(a, b):
    na, ma, m2a = a
    nb, mb, m2b = b
    if na == 0:
        return b
    if nb == 0:
        return a
    delta = mb - ma
    n = na + nb
    mean = ma + delta * nb / n
    m2 = m2a + m2b + delta * delta * na * nb / n
    return n, mean, m2


def add_value(stat, x):
    n, mean, m2 = stat
    n2 = n + 1
    delta = x - mean
    mean2 = mean + delta / n2
    return n2, mean2, m2 + delta * (x - mean2)


def clean_values(ts, raw, quality):
    n = len(raw)
    previous = [-1] * n
    following = [-1] * n
    last = -1
    for i in range(n):
        previous[i] = last
        if quality[i] == 0:
            last = i
    last = -1
    for i in range(n - 1, -1, -1):
        following[i] = last
        if quality[i] == 0:
            last = i

    values = [float(x) for x in raw]
    for i in range(n):
        if quality[i] != 2:
            continue
        left, right = previous[i], following[i]
        if left != -1 and right != -1:
            ratio = (ts[i] - ts[left]) / (ts[right] - ts[left])
            values[i] = raw[left] + (raw[right] - raw[left]) * ratio
        elif left != -1:
            values[i] = float(raw[left])
        elif right != -1:
            values[i] = float(raw[right])
    return values


def smooth_values(values, window, threshold):
    n = len(values)
    block_size = max(1, math.isqrt(n))
    block_stats = []
    for start in range(0, n, block_size):
        stat = (0, 0.0, 0.0)
        for x in values[start:start + block_size]:
            stat = add_value(stat, x)
        block_stats.append(stat)

    def range_stats(left, right):
        stat = (0, 0.0, 0.0)
        while left <= right and left % block_size:
            stat = add_value(stat, values[left])
            left += 1
        while left + block_size - 1 <= right:
            stat = merge_stats(stat, block_stats[left // block_size])
            left += block_size
        while left <= right:
            stat = add_value(stat, values[left])
            left += 1
        return stat

    half = (window - 1) // 2
    result = values.copy()
    for i, value in enumerate(values):
        left = max(0, i - half)
        right = min(n - 1, i + half)
        count, mean, m2 = range_stats(left, right)
        variance = max(0.0, m2 / count)
        if abs(value - mean) > threshold * math.sqrt(variance):
            result[i] = mean
    return result


def score(values, quality):
    stat = (0, 0.0, 0.0)
    for x in values:
        stat = add_value(stat, x)
    n, mean, m2 = stat
    standard_deviation = math.sqrt(max(0.0, m2 / n))

    quality_weight = (1.0, 0.5, 0.25)
    denominator = sum(quality_weight[q] * abs(x) for x, q in zip(values, quality))
    if denominator == 0.0 or standard_deviation == 0.0:
        return 0

    total = 0.0
    for x, q in zip(values, quality):
        weight = quality_weight[q] * abs(x) / denominator
        total += weight * abs((x - mean) / standard_deviation)
    return math.floor(total * 100 + 0.5)


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, window, threshold = data[:3]
    ts, raw, quality = [], [], []
    pointer = 3
    for _ in range(n):
        t, value, q = data[pointer:pointer + 3]
        pointer += 3
        ts.append(t)
        raw.append(value)
        quality.append(q)

    cleaned = clean_values(ts, raw, quality)
    smoothed = smooth_values(cleaned, window, threshold)
    print(score(smoothed, quality))


if __name__ == "__main__":
    solve()

import sys


def solve():
    input = sys.stdin.buffer.readline
    n, capacity = map(int, input().split())
    infinity = 10**30
    dp = [infinity] * (capacity + 1)
    dp[0] = 0

    for _ in range(n):
        c1, t1, c2, t2 = map(int, input().split())
        next_dp = [infinity] * (capacity + 1)
        for used, total_time in enumerate(dp):
            if total_time == infinity:
                continue
            if used + c1 <= capacity:
                next_dp[used + c1] = min(next_dp[used + c1], total_time + t1)
            if used + c2 <= capacity:
                next_dp[used + c2] = min(next_dp[used + c2], total_time + t2)
        dp = next_dp

    best_time = min(dp)
    best_cost = next(cost for cost, time in enumerate(dp) if time == best_time)
    print(best_time, best_cost, capacity - best_cost)


if __name__ == "__main__":
    solve()