题型识别

What · 是什么

题型识别指拿到题面后快速判断「这是什么类型的题」，从而决定应对流程与评测规则。四大类：①传统题——输入→程序→输出，黑盒评测，比较输出（忽略行末空白），有 TL/ML；②交互题——程序与评测程序问答（见 interaction-strategy）；③提交答案题——不交程序，交答案文件（.out），无限时间空间，可手玩或写程序生成；④通信题——两个程序通过受限通道协作（如 Channel 编解码，对答有限位）。评测结果类型：AC 接受、CE 编译错误、WA 答案错误、PE 格式错误、RE 运行错误（非零返回）、TLE 超时、MLE 超内存、OLE 输出超量。ICPC 需全部测试点 AC 才算过题，OI 逐测试点给分。

Why · 为什么

How · 实现

伪代码

题型判定流程:
  1. 题面有无 grader/交互函数/询问格式? → 交互题
  2. 是否要求提交 .out 答案文件而非源码? → 提交答案题
  3. 是否两个程序互相通信? → 通信题
  4. 否则 → 传统题
应对:
  传统题 → 正常读入输出，注意 TL/ML
  交互题 → 封装 ask()，flush，控次数
  提交答案题 → 写生成程序/暴力构造答案文件
  通信题 → 设计编码方案

Python 实现

import sys


def identify_problem_type(desc):
    """按题面特征启发式识别题型，返回 (类型, 关键注意点)。"""
    d = desc.lower()
    if "grader" in d or "交互" in d or ("? " in d and "!" in d):
        return ("interactive", "封装询问并 flush，控制询问次数")
    if ".out" in d or "答案文件" in d or ("输出文件" in d and "提交答案" in d):
        return ("output-only", "不交程序，生成答案文件，无 TL/ML")
    if "两个程序" in d or "通信" in d or "channel" in d:
        return ("communication", "设计编码/解码，关注信息量限制")
    return ("traditional", "常规读入输出，注意 TL/ML 与输出格式")


def main():
    samples = [
        ("给定 n 个数，求最大值，输出一个整数", "traditional"),
        ("交互题：每次询问一个数 x，评测程序回答 x 是否大于答案", "interactive"),
        ("提交答案题：输出 1.out .. 10.out 十个答案文件", "output-only"),
        ("通信题：程序 A 给程序 B 发送信息，两程序需协作", "communication"),
    ]
    for desc, expect in samples:
        typ, note = identify_problem_type(desc)
        print(f"{typ:14s} | {note}")
        assert typ == expect, (desc, typ)
    verdicts = {"AC": "Accepted", "WA": "Wrong Answer", "TLE": "Time Limit Exceeded",
                "RE": "Runtime Error", "MLE": "Memory Limit Exceeded", "OLE": "Output Limit Exceeded",
                "CE": "Compile Error", "PE": "Presentation Error"}
    print("\nverdict mapping:", len(verdicts), "kinds")
    assert len(verdicts) == 8
    print("OK")


if __name__ == "__main__":
    main()

易错点

• 把交互题当传统题写（读入后一次性输出）——直接 ILE
• 提交答案题还在写读入输出的主程序而不是生成答案文件
• 输出末尾多余空格/换行被严格格式题判 PE（现代 OJ 常容忍或并 WA）
• 忽视 OLE：调试日志忘删导致输出超量
• 通信题误用共享内存/额外输出，被判定格式违规
• 把 RE 当 WA 排查：先看评测返回的 verdict 再对症

例题

信源

• OI Wiki✓ https://oi-wiki.org/contest/problems/
• OI Wiki✓ https://oi-wiki.org/contest/interaction/
• OI Wiki✓ https://oi-wiki.org/contest/icpc/