跳转至

分拣流水线:流式状态扫描

出题人配套讲解已有逐字符累积的状态扫描。Codex(GPT-6):直接流式读入,以百分位整数代替浮点数,整理状态不变量。

程序:alternative.cpp。主解及比较见连续片段扫描。这是可通过完整数据的并列方案。

状态与转移

维护当前数去掉小数点后的整数值 \(v\) 、是否已经遇到小数点,以及小数点后读入的位数 \(d\) . 读入数字 \(c\) 时,令 \(v\gets10v+c\) ;若已经遇到小数点,再令 \(d\gets d+1\) . 遇到小数点时只改变标记。

遇到字母或输入结束时结算:无小数点就将 \(v\) 加入整数和;有小数点就将 \(v10^{2-d}\) 加入百分位和。随后清空数值状态,并把字母转换后追加到结果串。没有待结算数字时,结算只加入零,因此连续字母和末尾换行不会造成重复计数。

正确性与复杂度

不变量是:当前数值状态精确表示自上一个分隔字母以来读入的数字及小数点位置。逐位乘十加数字保持该不变量;结算将该数精确换算为所属类别的单位。每个片段仅在结束时贡献一次,字母按输入顺序收集,因此输出与题意一致。

令 \(N=|S|\) 、\(L\) 为字母总数。每个字符只处理一次,时间为 \(O(N)\) ;两个结果串占 \(O(L+1)\) 空间,其余状态为 \(O(1)\) . 按规定的输出顺序,字母必须等待两项总和计算完毕后再输出,所以仍需保存结果串。数值安全界与主解相同。