数字串拆积
P5491. 数字串拆积
场次:2026年10月22日-非AI方向 · 来源:CodeFun2000 P5491
题目描述
给定一串只由数字构成的字符串 。现在要放上恰好一个乘号,把它拆成左右两段(两段都不能空),各自视为十进制整数。请找出一种拆法,使两段乘积尽可能大,并返回该最大值。
前导 按通常十进制取值,例如 读成 。
请实现 maxSplitProduct(seq: str) -> int。
输入格式
一行字符串,用双引号包裹。引号内只含数字字符。
约束:
- 仅由数字 ~ 组成
输出格式
一个整数:所有合法拆法中,左右两段十进制值乘积的最大值。
示例
示例 1
输入:
"2222"输出:
484说明:
- 拆成 与 ,乘积
- 拆成 与 ,乘积
- 拆成 与 ,乘积
- 最大为
示例 2
输入:
"4051"输出:
2040说明:
- 最大为
示例 3
输入:
"10"输出:
0说明: 只有一种拆法 ,乘积为 。
解题思路
输出是什么: 个乘积里取最大的那个
长度为 的串只有 个合法切点。用 表示「左段取前 个字符」,那么 只能取 —— 左段为空, 右段为空,都被「两段非空」挡掉。候选集就这么大,题目要的是这 个数里的最大值。
这一步把题意彻底定死了:没有「怎么切更好」的策略问题,只有「每个切点算一遍」。
为什么不能只试「对半切」
一个看似聪明的想法是:两数乘积在位数接近时更大,所以只在中间切就行。数字串里只要出现 或前导零,这个直觉就失效。
1001 的长度是 ,「中间」是 ,得到 ;而 得到 ,是它的 10 倍。再看官方示例 3 的 10:唯一能切的位置贴着左端(),根本谈不上「中间」。乘积大小取决于两段的数值,而数值取决于每段自己的位数与内容,没有一条只看长度的规则能定下最优切点,所以老老实实枚举。
枚举的写法:切点走一遍,两段各转一次整数
def maxSplitProduct(seq: str) -> int:
"""枚举每个切点 k:左段取前 k 个字符,右段取剩下 n-k 个。"""
n = len(seq)
best = 0
for k in range(1, n): # k 取 1..n-1,保证两段都非空
left = int(seq[:k])
right = int(seq[k:])
if left * right > best:
best = left * right
return best三个细节都对得上题面:
range(1, n)的上下界就是「两段非空」:1让左段至少 1 个字符,n不取到让右段至少 1 个字符;seq[:k]与seq[k:]正好把串切成「前 个」和「后 个」,两段拼起来就是原串,一个字符不重不漏;int()会自动吃掉前导零,与「按通常十进制取值」一致(示例 2 里int("051")就是 ),不需要额外处理。
best 从 0 起:两段都是非负整数,乘积不可能小于 0,用 0 当初值就把「全零串」这种极端输入一并覆盖了("00" 只有 ,得 )。
还有一处不属于算法、但属于读入:官方输入把串放在一对双引号里,"2222" 整行读进来时首尾各有一个 ",要先剥掉再交给 maxSplitProduct,否则 int('"2222"') 直接抛 ValueError。这件事在 solve() 里做一次即可,函数本身只接收纯数字串。
数据范围由算法反推
是题面给的硬上限:最多 8 个切点,每个切点扫两段共 个字符做转换,合计是 的字符处理,规模小到可以直接枚举。字符串转换的这一步就是本题的全部开销,没有别的环节会盖过它。
完整代码实现
import sys
def maxSplitProduct(seq: str) -> int:
"""枚举每个切点 k:左段取前 k 个字符,右段取剩下 n-k 个。"""
n = len(seq)
best = 0
for k in range(1, n): # k 取 1..n-1,保证两段都非空
left = int(seq[:k])
right = int(seq[k:])
if left * right > best:
best = left * right
return best
def solve():
line = sys.stdin.readline().strip()
if not line:
return
print(maxSplitProduct(line.strip('"')))
if __name__ == "__main__":
solve()示例推演
示例 1:"2222"
,切点 取 1、2、3。
| 左段 | 左段值 | 右段 | 右段值 | 乘积 | best | |
|---|---|---|---|---|---|---|
| 1 | 2 | 2 | 222 | 222 | 444 | 444 |
| 2 | 22 | 22 | 22 | 22 | 484 | 484 |
| 3 | 222 | 222 | 2 | 2 | 444 | 484 |
输出 484,正是题面说明里列出的那三行候选中的最大值。
示例 2:"4051"
,切点 取 1、2、3。
| 左段 | 左段值 | 右段 | 右段值 | 乘积 | best | |
|---|---|---|---|---|---|---|
| 1 | 4 | 4 | 051 | 51 | 204 | 204 |
| 2 | 40 | 40 | 51 | 51 | 2040 | 2040 |
| 3 | 405 | 405 | 1 | 1 | 405 | 2040 |
第 1 行里 int("051") 得到 ,前导零被吃掉。输出 2040。
示例 3:"10"
,只有 一个切点:,输出 0。
复杂度分析
为数字串长度。
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 预先把每个切点的左右两段值都存成数组 | 存了 个大整数、每个最长 位;换来的只是省掉重复转换,空间却翻倍 | ||
| 逐切点现转两段再比较(最优) | 个切点,每个切点扫两段共 个字符;临时大整数随用随丢 |
时间里的 与 次「把 个字符转成整数」对应,比较与乘法都在这之上,不改变量级。空间不算乘积本身(它是返回值,不是存储),seq[:k]、seq[k:] 各是 的临时串。
易错点总结
1. 右段下标写成 seq[k+1:]
把 当成「左段最后一位的下标」而不是「左段长度」,两个切片就会差一位:seq[:k] 与 seq[k+1:] 之间漏掉了第 个字符。输入 1234 时 拿到 、 拿到 ,而正确答案是 的 ;更糟的是 时 seq[4:] 是空串,int('') 直接抛 ValueError,程序在第一组样例就崩。切点同时被用作切片上界与起始下标,差一位只有对照原始数字串才看得出来。
2. 切点范围写成 range(n)
for k in range(1, n) 少写一个 1(写成 range(n))或上界写成 n+1,就会产生空段。range(n) 在示例 1 的 "2222" 上会执行到 ,此时 seq[4:] 是空串,int('') 直接抛 ValueError: invalid literal for int() with base 10: ''——第一组样例就跑不过。范围的两端分别对应「左段非空」和「右段非空」,是题面两个约束的直接翻译。
3. 忘了剥掉输入里的双引号
官方输入的一行是 "2222" 而不是 2222。直接 int(line) 会抛 ValueError: invalid literal for int() with base 10: '"2222"',因为引号是字符串内容的一部分。剥引号要放在读入之后、调用 maxSplitProduct 之前,且只能用 strip('"') 去掉首尾各一个,不能用 int 硬转。