分类指标、阈值选择与决策树

import sys


def main():
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])
    pairs = []
    for i in range(n):
        pairs.append((float(data[1 + 2 * i]), int(data[2 + 2 * i])))
    pairs.sort(key=lambda p: -p[0])          # 分数从高到低
    total_pos = sum(label for _, label in pairs)
    tp = fp = 0
    best_f1, best_t = -1.0, pairs[0][0]
    i = 0
    while i < n:
        t = pairs[i][0]
        while i < n and pairs[i][0] == t:    # 并列分数一起跨过阈值
            if pairs[i][1] == 1:
                tp += 1
            else:
                fp += 1
            i += 1
        fn = total_pos - tp
        denom = 2 * tp + fp + fn
        f1 = 0.0 if denom == 0 else 2 * tp / denom
        if f1 > best_f1 + 1e-12:             # 并列不更新，保留先遇到的更大阈值
            best_f1, best_t = f1, t
    print(f"{best_t:.4f} {best_f1:.6f}")


main()

排序 O(n log n) 加一次线性扫描；每个候选阈值只做常数次加法。用两组题面示例和第 05 节的并列用例核对。

import sys


def main():
    data = sys.stdin.read().split()
    if not data:
        return
    t, d, q = int(data[0]), int(data[1]), int(data[2])
    pos = 3
    trees = []
    for _ in range(t):
        s = int(data[pos]); pos += 1
        nodes = [None] * (s + 1)              # 节点编号从 1 开始，1 号是根
        for i in range(1, s + 1):
            kind = data[pos]; pos += 1
            if kind == "L":
                nodes[i] = ("L", int(data[pos])); pos += 1
            else:
                feature = int(data[pos]) - 1   # 题目特征编号从 1 起，列表下标从 0 起
                threshold = float(data[pos + 1])
                left, right = int(data[pos + 2]), int(data[pos + 3])
                pos += 4
                nodes[i] = ("N", feature, threshold, left, right)
        trees.append(nodes)

    out = []
    for _ in range(q):
        x = [float(v) for v in data[pos:pos + d]]; pos += d
        votes = {}
        for nodes in trees:
            cur = 1
            while nodes[cur][0] != "L":        # 用循环从根走到叶，不用递归
                _, feature, threshold, left, right = nodes[cur]
                cur = left if x[feature] <= threshold else right   # 相等走左
            label = nodes[cur][1]
            votes[label] = votes.get(label, 0) + 1
        out.append(str(min(votes, key=lambda lab: (-votes[lab], lab))))   # 平票取小
    print("\n".join(out))


main()

题目允许所有树的节点总数到 5000，树可能是几千层的链——while 循环对任何深度都安全。用题面示例 2 → 0 / 2 / 2 和第 07 节的两组用例核对。

import sys


def fmt(num, den, digits):
    # 精确四舍五入：分子分母都是整数，先放大 10^digits 倍再按余数判断进位——不经过浮点，0.03125 这类恰好在中点的值也能正确进位
    if den == 0:                            # 分母为 0 的指标按 0 处理
        return "0." + "0" * digits
    q, r = divmod(num * 10 ** digits, den)
    if 2 * r >= den:
        q += 1
    s = str(q).rjust(digits + 1, "0")
    return s[:-digits] + "." + s[-digits:]


def main():
    data = sys.stdin.read().split()
    if not data:
        return
    n, k = int(data[0]), int(data[1])
    truth = data[2:2 + n]
    pred = data[2 + n:2 + 2 * n]
    tp = [0] * k
    fp = [0] * k
    fn = [0] * k
    for a, b in zip(truth, pred):
        a, b = int(a), int(b)
        if a == b:
            tp[a] += 1
        else:
            fp[b] += 1                      # 预测成 b，但真实不是 b
            fn[a] += 1                      # 真实是 a，却没预测成 a

    out = []
    macro_num, macro_den = 0, 1             # 宏平均 = Σ F1 / k，用整数分子分母累加，最后一次舍入
    for c in range(k):                      # 没出现过的类别也要输出、也计入宏平均
        denom = 2 * tp[c] + fp[c] + fn[c]
        out.append(f"{fmt(tp[c], tp[c] + fp[c], 4)} {fmt(tp[c], tp[c] + fn[c], 4)} {fmt(2 * tp[c], denom, 4)}")
        if denom:                           # F1 = 2TP / (2TP + FP + FN)；分母为 0 时按 0，不参与相加
            macro_num, macro_den = macro_num * denom + 2 * tp[c] * macro_den, macro_den * denom
    tps, fps, fns = sum(tp), sum(fp), sum(fn)
    out.append(f"{fmt(macro_num, macro_den * k, 6)} {fmt(2 * tps, 2 * tps + fps + fns, 6)}")
    print("\n".join(out))


main()

三个分母各写一个显式分支；没出现过的类别也输出一行、也计入宏平均。四舍五入用整数分子分母计算，不经过浮点——例如某类精确率恰好是 1/32 = 0.03125，题目要求四舍五入得 0.0313，而 f"{p:.4f}" 会按二进制存储值打出 0.0312。