稀疏整数求和
P5949. 稀疏整数求和
场次:2026年10月28日-非AI方向 · 来源:CodeFun2000 P5949
题目描述
给定两个位数可能极多的非负整数,请求出它们相加后的结果。
这类整数的十进制表示通常只有少量数位不为 ,所以仅记录非零数字片段。每个片段写作 c:p,其中 是片段系数, 是十进制位权的指数。
一个 c:p 片段所贡献的数值为 ; 对应系数最右侧数字所在的数位。
表示方式需要遵守以下约定:
- 指数满足 ,允许的最大单项为 999:1999999999。
- 按数位从高向低列出片段,任何片段的系数中都不能出现数字 ;遇到零位时应断开片段。
- 系数 至多包含 个数字。若一段连续非零数字更长,就从左端开始,每次取尽可能多且不超过 位的数字作为一组。例如,8765432 应划为 876、543、2。
- 每个整数的编码末尾都附上标记 0:0,数值为零时只写这一标记。相邻项之间以空格隔开。
- 所有输入编码均合法。每行编码的字符数连同空格计入后小于 ,并保证求和结果中各片段的指数也小于 。
例如:
- 十进制数 8765004009 的编码为 876:7 5:6 4:3 9:0 0:0。
- 十进制数 8765004000 的编码为 876:7 5:6 4:3 0:0。
输入格式
- 首行给出其中一个非负整数的编码。
- 次行给出另一个非负整数的编码。
两行均采用上述片段表示方式。
数据范围: 指数 ;系数至多 位且不含数字 ;每行编码(含空格)字符数小于 ;保证结果中所有片段的指数也小于 。
输出格式
输出这两个数相加得到的数值。
结果也须按上述约定编码:连续非零数字从高位起每次最多取 位,并在末尾附上 0:0。
示例
示例 1
输入:
567:3 89:1 0:0
444:3 321:0 0:0输出:
1:6 122:2 11:0 0:0说明: 两行分别代表 和 ,相加可得 。
零位将结果分为 1 与 12211 两段;后一段再从左向右划为 122、11,故得到上面的编码。
示例 2
输入:
999:3 999:0 0:0
1:0 0:0输出:
1:6 0:0说明: 相加的数值是 与 ,得到 。连续进位后,只有指数为 的数位非零,编码因此只包含这一片段和结束标记。
解题思路
输出到底是什么:一份合规的片段编码,而不是一串十进制数字
题目给的不是两个普通整数,而是两个整数的一种压缩编码。要求输出的也是同一种编码:从高位到低位列出片段,每段系数不含 、至多 位,末尾跟 0:0。
这决定了实现方式。若把输入展开成真正的整数再加, 可以到 ,意味着要存一个 亿位的十进制数 —— Python 的大整数按 30 个二进制位一组来存,光这一个数就要近 ,而且进位要一位一位走完。这条路在数据范围面前直接断掉。
真正的信息量在另一头:一行编码的字符数不到 ,说明非零数字的位数很少。所以整份算法都应该建立在「只记录非零的位」这个稀疏表示上,从头到尾不造那个大整数。
第一步:把编码摊成「第几位上是几」
c:p 的含义是「系数 的最右一位落在十进制第 位」。把 拆成数字(从右往左),第 个数字( 从 起)就落在第 位:
def decode(line):
"""一行编码 -> {十进制位: 该位上的数字}"""
digits = {}
for token in line.split():
c_str, p_str = token.split(":")
p = int(p_str)
for i, ch in enumerate(reversed(c_str)):
d = int(ch)
if d: # 系数里不会有 0,这里只是防御
digits[p + i] = digits.get(p + i, 0) + d
return digits拿 567:3 走一遍:reversed("567") 是 7, 6, 5,于是第 位是 、第 位是 、第 位是 。再配上 89:1(第 位 、第 位 ),得到的正是 的每一位。
末尾那个 0:0 不用特判:它的系数是 ,逐位展开时每一个 d 都是 ,被 if d 跳过,对结果没有任何影响。
用字典而不是数组存「位 → 数字」,是因为 可以到 ,而真正出现的位只有几百个。
第二步:同位相加,再从低位往高位进位
两个数相加,只有同一位上的数字会碰到一起。把两份稀疏表加起来,得到的是「每一位上的数字和」,它可能超过 (两个 相加是 ),需要向高位进位:
carry, d = divmod(value, 10) # d 留在本位,carry 进到 p + 1关键是处理顺序:必须从最低位开始,否则刚进上去的 会被已经扫过的位漏掉。而稀疏表里大部分位是空的,按 硬扫会走 步,同样不可行。
用一个小顶堆只装「真正有数字的位」,就能以「从低到高」的顺序遍历它们,且不碰空位。进位只会落到 ,它比当前位大,所以一定还没被处理过 —— 直接把 塞进堆即可,不会打乱顺序:
from heapq import heapify, heappop, heappush
def normalize(digits):
"""把每位上的数字和逐位进位,压成 0..9 的稀疏数字表"""
cache = dict(digits)
heap = list(cache.keys())
heapify(heap)
in_heap = set(heap)
out = {}
while heap:
p = heappop(heap) # 当前最低的、有数字的位
in_heap.discard(p)
carry, d = divmod(cache.pop(p), 10)
if d:
out[p] = d # 本位最终是几
if carry:
if p + 1 in cache: # 高位已经有数字,累加即可
cache[p + 1] += carry
else:
cache[p + 1] = carry
if p + 1 not in in_heap:
heappush(heap, p + 1)
in_heap.add(p + 1)
return outin_heap 用来避免同一个位被重复入堆:如果 本来就在堆里等着,只更新 cache 就够了;如果它是被进位新造出来的,才需要入堆。
第三步:把稀疏数字重新切成合规的片段
进位结束后,out 里只剩 到 的数字,且值为 的位根本不在表里 —— 这正好对应题面「遇到零位就断开片段」的规则。于是编码分两层:
- 按连续性分段:把位从高到低排好,相邻位差 就属于同一段,否则断开。段内每个数字都非零。
- 段内从左端每 位切一块:拼接出这一段的数字串 (高位在前),依次取
s[0:3]、s[3:6]……
第 步里每块要算出自己的指数,也就是「这块最右一位落在第几位」。段的最低那位记作 low,段长记作 len(s);第 个块(从 起)长度为 len(chunk),它右边还剩 len(s) - k - len(chunk) 个数字,所以
def encode(digits):
"""稀疏数字表 -> 片段编码"""
if not digits: # 结果为零:只写结束标记
return "0:0"
parts = []
pos = sorted(digits, reverse=True) # 从高位到低位
i = 0
while i < len(pos):
run = [pos[i]] # 一段连续的非零位
j = i + 1
while j < len(pos) and pos[j] == run[-1] - 1:
run.append(pos[j])
j += 1
low = run[-1] # 这一段的最低位
s = "".join(str(digits[p]) for p in run)
k = 0
while k < len(s): # 从左端开始,每次最多 3 位
chunk = s[k:k + 3]
p = low + len(s) - k - len(chunk)
parts.append(f"{int(chunk)}:{p}")
k += 3
i = j
parts.append("0:0") # 末尾的结束标记
return " ".join(parts)用题面自己的例子验一遍切割方向:8765432 的段是 "8765432",low = 0。
| 块 | s[k:k+3] | 指数 | 片段 | |
|---|---|---|---|---|
| 1 | 876 | 876:4 | ||
| 2 | 543 | 543:1 | ||
| 3 | 2 | 2:0 |
结果 876:4 543:1 2:0,与题面「876、543、2」的划法一致。从右端切会得到 8、765、432 这种不合规的分组,数值虽然一样,编码却不合法。
实现落点
decode只记录非零位,0:0天然被忽略;normalize用堆保证「低位先处理」,out里不保留 位,省掉了编码阶段的零判断;encode的两层循环分别对应「按零位断段」与「段内三位一组」;- 结果为零时
digits为空,直接输出0:0,不需要额外的分支去拼空行。
完整代码实现
"""
P5949. 稀疏整数求和 - 稀疏位表 + 逐位进位 + 重新分组编码
整数用 c:p 片段表示:c * 10^p,p 是 c 最右一位所在的十进制位。
系数至多 3 位、不含 0,连续非零数字从左端起每 3 位一组,
编码以 0:0 结尾。读入两行编码,输出两数之和的同种编码。
输入格式:
- 第一行:一个非负整数的编码;
- 第二行:另一个非负整数的编码。
输出格式:
- 一行:两数之和的编码,末尾附 0:0。
核心思路:
指数最大到 2e9,展开成大整数不现实(约 20 亿位),所以全程用
{位: 数字} 的稀疏表:
1. 把每个片段按位摊开(最右一位落在 p,向左依次 +1);
2. 同位相加,用小顶堆按位从低到高处理进位(进位只会落到 p+1);
3. 从高位扫描连续非零段,段内从左端每 3 位切一块,重新算指数。
时间复杂度:O(D log D),D 为非零数字的位数(输入每行不足 512 字符)
空间复杂度:O(D)
"""
# https://codefun2000.com/p/P5949
import sys
from heapq import heapify, heappop, heappush
# @sample-start
"""
样例输入 1:
567:3 89:1 0:0
444:3 321:0 0:0
样例输出 1:
1:6 122:2 11:0 0:0
"""
# @sample-end
# @sample-start
"""
样例输入 2:
999:3 999:0 0:0
1:0 0:0
样例输出 2:
1:6 0:0
"""
# @sample-end
def decode(line):
"""一行编码 -> {十进制位: 该位上的数字和}。"""
digits = {}
for token in line.split():
c_str, p_str = token.split(":")
p = int(p_str)
for i, ch in enumerate(reversed(c_str)):
d = int(ch)
if d: # 0:0 里全是 0,自动被跳过
digits[p + i] = digits.get(p + i, 0) + d
return digits
def normalize(digits):
"""把每位上的数字和进位,压成 0..9 的稀疏数字表。"""
cache = dict(digits)
heap = list(cache.keys())
heapify(heap)
in_heap = set(heap)
out = {}
while heap:
p = heappop(heap) # 当前最低的、有数字的位
in_heap.discard(p)
carry, d = divmod(cache.pop(p), 10)
if d:
out[p] = d
if carry:
if p + 1 in cache:
cache[p + 1] += carry
else:
cache[p + 1] = carry
if p + 1 not in in_heap:
heappush(heap, p + 1)
in_heap.add(p + 1)
return out
def encode(digits):
"""稀疏数字表 -> 片段编码(每段从高位起最多 3 位,末尾附 0:0)。"""
if not digits:
return "0:0" # 数值为零时只写结束标记
parts = []
pos = sorted(digits, reverse=True) # 从高位到低位
i = 0
while i < len(pos):
run = [pos[i]] # 一段连续的非零位
j = i + 1
while j < len(pos) and pos[j] == run[-1] - 1:
run.append(pos[j])
j += 1
low = run[-1]
s = "".join(str(digits[p]) for p in run)
k = 0
while k < len(s):
chunk = s[k:k + 3] # 从左端开始,每次最多 3 位
p = low + len(s) - k - len(chunk)
parts.append(f"{int(chunk)}:{p}")
k += 3
i = j
parts.append("0:0")
return " ".join(parts)
def solve():
lines = [ln for ln in sys.stdin.read().splitlines() if ln.strip()]
digits = {}
for ln in lines:
for p, d in decode(ln).items():
digits[p] = digits.get(p, 0) + d
print(encode(normalize(digits)))
def run_tests():
"""运行嵌入的示例与边界用例,方便本地自测。"""
import io
cases = [
("567:3 89:1 0:0\n444:3 321:0 0:0\n", "1:6 122:2 11:0 0:0"),
("999:3 999:0 0:0\n1:0 0:0\n", "1:6 0:0"),
# 题面例子:8765004009 + 0
("876:7 5:6 4:3 9:0 0:0\n0:0\n", "876:7 5:6 4:3 9:0 0:0"),
# 零加零:只有结束标记
("0:0\n0:0\n", "0:0"),
# 8765432 + 0:验证「从左端每 3 位一组」
("876:4 543:1 2:0 0:0\n0:0\n", "876:4 543:1 2:0 0:0"),
# 最高位进位:999:1999999999 + 1:0
("999:1999999999 0:0\n1:0 0:0\n", "999:1999999999 1:0 0:0"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected!r}, 实际={output!r} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:
摊开两份编码。 第一行 567:3 89:1:
567:3→ 第 位 、第 位 、第 位 ;89:1→ 第 位 、第 位 。
拼起来是 。第二行 444:3 321:0:
444:3→ 第 位都是 ;321:0→ 第 位 、第 位 、第 位 。
拼起来是 。
同位相加。 两张表逐位对齐后相加:
| 位 | ||||||
|---|---|---|---|---|---|---|
| 第一个数 | ||||||
| 第二个数 | ||||||
| 数字和 |
从低位进位。 堆里初始是 ,按从小到大取出:
| 取出位 | 取到的和 | divmod(和, 10) | 本位最终 | 进位去向 |
|---|---|---|---|---|
| 无 | ||||
| 第 位 | ||||
| 第 位 | ||||
| 第 位 | ||||
| 第 位 | ||||
| 无(是 ) | 第 位 | |||
| 无 |
最终非零位是 ,对应的数字依次是 ,拼出来:
与官方解释一致。注意第 位最终是 ,它不会进入 out,正好在 与 之间形成断口。
重新分组。 从高位扫:
- 第 位单独一段,段串
"1",一块1:6; - 第 位是零位,断开;
- 第 位连成一段,段串
"12211",low = 0、长度 :- 第 块
"122",指数 →122:2; - 第 块
"11",指数 →11:0。
- 第 块
拼上结束标记,输出 1:6 122:2 11:0 0:0,与官方样例逐字符相同。
用同样的流程看示例 2:999:3 999:0 是 (第 位都是 ),加 后第 位变成 ,进位把第 位一路清成 、第 位变 ,于是只剩一段 "1",输出 1:6 0:0。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 展开成十进制大整数再相加 | 可达 ,约 亿位、近 内存,不可行 | ||
| 稀疏位表 + 堆上进位(最优) | 为非零数字位数,每行不足 字符, 只有几百 |
里的对数来自堆:每位进出堆各一次。若把「所有出现过的位」先收集起来排序再扫,复杂度同样是 ,效果一样。
易错点总结
1. 段内从右端每 3 位切一块
把 chunk = s[k:k + 3] 改成从右端取(先取 s[-3:],再取剩下的),数值不会错,编码却违反题面「从左端开始」的约定。示例 1 的 "12211" 会被切成 211 与 12,输出变成 1:6 211:0 12:3 0:0;题面给的 8765432 也会被切成 8、765、432 而不是 876、543、2。逐字符比较时整行都不对,但它仍然是一个能还原出正确数值的合法编码,很容易被当成「输出格式小问题」放过。
2. 进位写回了高位,却没把这一位放回堆
normalize 里若只写 cache[p + 1] = carry,而漏掉后面那三行入堆的代码,那么当 原本不在输入里时,这位数字永远不会被取出、也不会进入 out。示例 2 因此输出 0:0(正确是 1:6 0:0)—— 唯一的非零位在进位后变成 ,新造出来的第 位被丢掉了;示例 1 则会丢掉高位的 1:6,只剩 122:2 11:0 0:0。