跳转至

分拣流水线:连续片段扫描

出题人解法:划分数字片段,按字母类别收集结果。Codex(GPT-6):以整数百分位完成精确求和,使用摊还常数时间的字符追加,并补充边界证明和数据验证。

首选方案

从左到右扫描。遇到字母时转换大小写,追加到对应结果串;遇到数字或小数点时,读完当前极长数字片段。数字片段中有小数点就是 B 类,否则是 A 类。

设一个小数的整数部分为 \(w\) ,小数部分补足两位后为 \(f\) ,以 \(100w+f\) 表示它的百分位数。例如 .1 为 \(10\) ,7. 为 \(700\) . 用两个 64 位整数分别累加整数和百分位数。输出小数时,将后者除以 \(100\) 得到整数部分,余数补足两位。

令 \(N=|S|\) . 数字片段至多有 \(N\) 个,单个数小于 \(10^6\) ,所以整数和小于 \(N\cdot10^6\) ,百分位总和小于 \(N\cdot10^8\le10^{13}\) . 64 位有符号整数足够,不需要二进制浮点近似或舍入。长串前导零不会增大中间值。

正确性

两个数之间必有字母,因此每个极长数字片段对应且仅对应一个数,扫描不会合并或拆开数。每个数恰好累加一次,是否含小数点决定正确的类别;补足两位只是乘以十的幂,不改变数值。每个字母也恰好追加一次,扫描顺序保证了各结果串的相对顺序。故四行输出均满足要求。

复杂度与实现

扫描时间为 \(O(N)\) ,包括输入与两个结果串的空间为 \(O(N+1)\) . 用 push_back 追加,避免反复复制整个结果串。空输入和缺少某类字符时,也输出完整四行;小数点前或后没有数字时相应部分按零处理。

程序见 std.cpp。流式状态扫描与本方案并列:它沿用配套讲解中的逐字符思路,直接从输入流读取,省去完整输入串;时间仍为 \(O(N)\) ,空间为 \(O(L+1)\) ,其中 \(L\) 是字母总数。首选程序保留显式片段边界,便于对应题意。两者都能通过完整数据。

测试配方见 plan.json,涵盖空串、空输出行、长串前导零、单侧小数、总和超过单个数上界及最大长度。测量见评测说明。