UVa 13090 Base of MJ 进制转换题解：二分查找与溢出处理-北京尧图网络

最近整理 UVA 的旧题单又翻到 13090 这道题。标题叫 Base of MJ第一眼还以为是讲某个叫 MJ 的角色基地结果题目拿到手里才发现这就是一道典型的进制转换题。题解在网上不算多不少新手卡在进制范围的判断和溢出处理上所以决定把它拆开聊一聊。核心模型并不复杂给一个由数字和大写字母组成的字符串再给一个十进制目标值找到一个最小的进制使字符串按这个进制解读后等于目标值。这类问题在 UVA 里非常多理解这一题之后很多同类题都可以直接套用思路。说实话看到“Base”这个词很多刚入门的朋友会下意识往“基地”方向想甚至会脑补出什么地图题、模拟题。但刷多了就明白UVa 的题目名字经常只是包装比如用个人名、用个奇怪缩写实际考的都是最朴素的数学点。Base of MJ 里的 MJ 是什么来头我至今没考证清楚大概率就是题目里的一个角色名算法上没有任何特殊含义。我们真正要处理的是字符串、进制、十进制值三者之间的映射关系。1. 先弄懂“Base of MJ”到底在问什么1.1 去掉包装MJ只是题目角色题目原文我复述不全但核心模型很标准。它给你一个字符串比如101再给一个数字 n比如 5问的是存在哪个进制 base使得101按 base 进制解读时十进制值恰好等于 5base 等于 2 的时候成立因为 1*2^2 0*2^1 1*2^0 5。这题的“最小进制”往往就是答案如果不存在就输出题目要求的非法标记。为什么强调最小进制因为同一个字符串可能对应多个进制。比如10在二进制下是 2在三进制下是 3在十进制下是 10几乎每个进制都对应一个不同值。但反过来给定目标值 n 后满足条件的进制可能不止一个特别是只有一位字符的时候。A在 11 进制下值是 10在 12 进制下值还是 10在 100 进制下依然是 10。题目要是让你输出任意一个那还好办但通常要求最小的那个所以必须二分到边界。1.2 字符串里的A-Z不是字母是数字进制题里最常见的扩展字符集是 0-9 加上 A-Z。这 36 个符号分别代表数值 0 到 35。A 是 10B 是 11一直到 Z 是 35。为什么不用数字继续写因为十进制符号只有 10 个再往上就没得用了只能借字母。很多刚接触的同学会在读入A之后直接当成字符处理忘了转换成 10这属于第一类常见 WA。我习惯用一个统一的转换函数int charToVal(char c) { if (0 c c 9) return c - 0; return c - A 10; }这样无论处理数字还是字母都走同一条路不容易写乱。字符映射关系不复杂但它会在后面的进制下界判断、单字符特判里反复出现值得一开始就定清楚。1.3 输入输出约定怎么读、怎么判、怎么输出按经典 UVA 惯例这类题往往是多组数据读到 EOF每组一行给一个字符串和一个 long long。字符串只有大写字母和数字没有负号和小数点。输出通常带 Case 编号例如Case 1: 7。有些题目找不到答案时输出 -1有些会要求一个特定值比如输出 0 或某个提示。老题目格式五花八门我建议你动手前先把输出格式看清楚别把精力耗在 WA 在格式这种不值当的地方。如果你不确定原题的输出格式最稳的法子是看 UVA 的 Sample Output。我的代码示例里用 -1 表示无解实际提交时记得改成原题要求。2. 核心原理位权展开与字符映射2.1 位权展开式与迭代式进制转十进制说穿了就是“每一位乘以对应的位权再相加”。比如2F在 16 进制下的值是 2*16^1 15*16^0 47。这里的 16^1、16^0 就是位权。用数学公式写出来很长但编程时根本不用计算幂迭代式更简洁value 0 for each character c: value value * base digit(c)举一个例子字符串101在二进制下是怎么变成 5 的先读入 1value1再读入 0value1*202再读入 1value2*215。每一步都相当于把之前的结果乘一次 base再把当前数字放进来和十进制里“拼数”的思路一模一样。这个迭代式是后面所有实现的核心建议直接背下来。2.2 字符转数字三种写法的取舍除了上面给出的 if-else 版本字符转数字还可以写成查表或三元运算。查表最稳定但需要编译器提前构建适合一个程序里大量调用的情况。对于单道题if-else 就够了。我更推荐把它拆成独立函数而不是在主循环里写一堆判断因为后面判断合法进制的下界时也要用同一个映射。有人会直接用c - 0去处理A得到结果是负数然后某一步进制判断出错。我在给新生 review 代码时见过太多次了。所以尽早统一映射后患少很多。你甚至可以写一个常量数组把0-9A-Z映射到 0-35每次查询直接查表既快又不容易错。2.3 合法进制的下界由最大字符决定这一点是整个题的命门进制 base 里不可能出现“等于 base 或大于 base”的数字符号。二进制的合法数字只有 0 和 1所以字符串里如果出现2这个串在二进制下就是非法表示。同理一个包含A的字符串进制至少是 11因为 A 代表 10而数字符号必须严格小于进制。由此推出下界最小合法进制 maxDigit 1同时进制不能小于 2所以low max(2, maxDigit 1)。比如101最大数字是 1下界是 22F最大字符是F15下界是 16。这段逻辑很薄但它是后面二分范围的左端点一旦算错后面全白搭。计算 maxDigit 时直接用同一个字符映射函数遍历一遍字符串即可。3. 求进制范围合法区间的数学推导3.1 为什么不能蛮力枚举到天荒地老拿到这道题第一反应可能是从 low 开始往上枚举 base一个一个试。枚举本身没错但量级撑不住。假设目标 n 最大到 1e18字符串是某个长串可能在二进制下就已经超过 1e18这时枚举 2 到 1e18 显然不可接受。更严重的是合法进制的上界并不是 36。虽然字符集只有 36 个符号进制却可以远远超过 36。比如字符串A要想等于 10进制取 11、12、13 都成立上界是多少完全取决于目标 n。所以我们必须用数学方式把搜索区间压缩而不是默认枚举到 36 或 1e6 就结束。3.2 单调性证明进制增大值不会变小假设字符串从高位到低位是 d0, d1, ..., dm在进制 b 下的值为V(b) d0 * b^m d1 * b^(m-1) ... dm当 b 增大时只要所有 digit 都小于 b也就是 b 大于等于我们给定的下界每一项 d_i * b^(m-i) 只会随 b 的增大而增大或不变所以 V(b) 关于 b 是单调不减的。这是一条极其重要的性质有了单调性就能用二分搜索“第一个值不小于 target 的进制”再去验证是否恰好相等。这里要注意“不减”和“严格递增”的区别。只有一位的字符串V(b) 恒等于那个 digit不随 b 变化全零字符串也一样。但“不减”已经够二分用了因为我们要找的是“第一个 V(b) target”的位置。如果你把目标定成“找最小可行进制”那么 lower_bound 天然能处理多解区间。3.3 上界为什么取 target1 就足够很多人会问二分上界设多少设小了漏解设大了怕溢出。我的答案很直接取 target1再和下界取 max。为什么够分两种情况看。首先当 target0 时上界自然就是 low因为全零串在任何合法进制下都是 0不需要往上找。其次当 target0 且字符串最高位不为 0 时一旦 base 大于 targetV(base) 至少是 base 的若干倍必然大于 target所以答案只可能出现在 base target 的范围内。最高位是 0 的情况更特殊此时 V(b) 的值其实由后续部分决定增大 b 不会让它变大如果当前区间的值已经到不了 target再往上也到不了。因此把上界设在 target1既能覆盖所有可能解又不会让搜索空间膨胀。如果你嫌推导复杂就记住二分下界是 maxDigit1上界是 max(下界, target1)。这个上界比很多人推荐的“枚举到 1e9”小得多也严谨得多。4. 完整实现C题解与逐段拆解4.1 工具函数字符转数值先写一个独立的字符映射函数。它会反复被调用所以尽量简洁、可读不要在主函数里分散写。int val(char c) { if (0 c c 9) return c - 0; return c - A 10; }这个函数必须覆盖所有输入情况。题目保证只有 0-9 和 A-Z所以不需要处理小写字母。如果题目比较阴间地给了小写可以加一个判断先转成大写再转数值。不过 UVa 老题里一般不会这样刁难。4.2 带溢出保护的计算函数这个函数是整个解法的精华。很多人二分都写对了唯独在 value 累加时溢出导致 mid 处的比较结果异常。我用一个 limit 参数来限制值只要超过 target 就提前返回 target1这样既保证比较逻辑正确又不会溢出 long long。判断溢出用了一个很常见的技巧if (v (limit - d) / base) return limit 1;因为v * base d可能溢出所以改成先判断除法结果。在目标值不超过 1e18 的前提下这个写法是安全的。如果你用的是更大范围的数据类型也可以把 limit 换成4e18之类的值但核心逻辑不变。ll valueInBase(const string s, ll base, ll limit) { ll v 0; for (char c : s) { int d val(c); if (d base) return limit 1; if (v (limit - d) / base) return limit 1; v v * base d; } return v; }这段代码里有两层保护。第一层判断当前 digit 是否小于 base小于进制才合法第二层判断乘法是否会溢出。两层都通过才更新 v。这样做的好处是即使 base 非常大函数也能在线性时间内给出正确比较结果。4.3 二分查找与最小进制二分部分是标准的 lower_bound。我们从 low 开始直到 high不断取 mid调用 valueInBase 看是否达到 target。如果达到说明 mid 可行或可能偏大把右边界收缩到 mid否则把左边界收缩到 mid1。结束时 low 就是第一个可行进制。ll solve(const string s, ll target) { int maxDigit 0; for (char c : s) maxDigit max(maxDigit, val(c)); ll low max(2LL, (ll)maxDigit 1); ll high max(low, target 1); while (low high) { ll mid low (high - low) / 2; if (valueInBase(s, mid, target) target) high mid; else low mid 1; } return valueInBase(s, low, target) target ? low : -1; }注意mid low (high - low) / 2而不是(low high) / 2后者在数值大时可能溢出。虽然这里 low 和 high 都不超过 1e18 量级但养成这个习惯总是好的。二分结束后的验证也不能少因为“第一个不小于 target 的进制”不一定恰好等于 target。4.4 完整代码与复杂度分析把上面的工具函数、计算函数、二分函数拼到一起加上多组数据的输入输出就得到完整解法。#include bits/stdc.h using namespace std; using ll long long; int val(char c) { if (0 c c 9) return c - 0; return c - A 10; } ll valueInBase(const string s, ll base, ll limit) { ll v 0; for (char c : s) { int d val(c); if (d base) return limit 1; if (v (limit - d) / base) return limit 1; v v * base d; } return v; } ll solve(const string s, ll target) { int maxDigit 0; for (char c : s) maxDigit max(maxDigit, val(c)); ll low max(2LL, (ll)maxDigit 1); ll high max(low, target 1); while (low high) { ll mid low (high - low) / 2; if (valueInBase(s, mid, target) target) high mid; else low mid 1; } return valueInBase(s, low, target) target ? low : -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; ll n; int tc 0; while (cin s n) { ll ans solve(s, n); cout Case tc : ans \n; } return 0; }复杂度很容易算valueInBase 内部是 O(L)二分区间长度是 O(target)但因为每次折半所以总复杂度是 O(L * log(target))。如果 target 是 1e18log 约 60一个长度 1000 的字符串也只要几万次运算完全够用。至于空间除了存储字符串之外没有额外分配。4.5 关于 lower_bound 的设计细节我之所以强调用 lower_bound 而不是在二分里直接判等是因为“等于 target”的进制可能不止一个。单字符字符串在很大一段进制范围内值都不变都等于同一个数。比如A在 11、12、13 等进制下都是 10。如果 target 是 10我们想要的是 11而不是 12、13。lower_bound 会先找到第一个不小于 10 的进制正好是 11再验证一下是否等于 10完美。如果你在普通二分里写死if (value target) return mid; else ...当存在多个解时返回的 mid 可能是中间某个解不一定最小。所以先 lower_bound再验证是最省心的做法。这也是很多老手推荐“二分答案后校验”的原因。5. 实测踩过的坑那些WA到怀疑人生的边界5.1 单字符“任何进制都可以”是最容易漏掉的我第一版代码直接枚举进制然后验证相等遇到 s0, target0 时输出了 2题目如果觉得进制最小是 2那么 2 就是标准答案。可是当 sA, target10 时从 11 开始枚举验证成立后输出 11也没问题。问题出在二分判断里如果返回的值恰好等于 target但 mid 不是最小值就会错。所以边界必须单独想清楚。单字符情况有一个直观结论若 s 的长度为 1且 digit 等于 target则最小进制是 max(2, digit1)否则无解。因为单字符在不同进制下的数值不会变永远是那个 digit。这个结论可以在代码里做特判但用 lower_bound 也能覆盖只是你得确保二分上界不会把它排除。5.2 溢出保护一句除法判断救回整份代码没有溢出保护的版本长这样v v * base d;如果 base 很大v 很快爆 long long变成负数然后二分逻辑彻底崩溃。比如 s1000000000000000000000, target1进制从 2 开始valueInBase 到第三步就已经超过 long long 了。所以必须在乘法前判断公式是v (limit - d) / base。limit 取 target 而不是 LLONG_MAX能进一步避免无谓计算。这个技巧我在很多题解里见过自己踩过一次之后才知道它有多重要。还有一个容易忽略的细节limit - d如果 d 非常大比如 d 是 35limit 是 10那么limit - d变成负数除法结果也是负数比较会出问题。但由于我们在前面已经判断了d base而 base 的最小合法值是 maxDigit1所以 d 一定小于等于 maxDigit进制又至少是 maxDigit1所以当 base 合法时 d 不会大于 target不一定target 可能小于 d比如 sZ, target10那 d35target10base 至少是 36在 valueInBase 中第一步判断 d base35 36 为假进入溢出判断。此时(limit - d) / base(10-35)/36是负数v0 不大于负数然后v 0*3635 35返回 35接着二分会认为 35 10然后验等失败。逻辑没问题。所以只要先做d base判断后面的负数情况就不会造成错误结果。如果你实在不放心可以再加一句if (d limit) return limit 1;一劳永逸。5.3 前导零与全零串前导零不影响进制合法性但会影响单调性。s012A在 high 足够大时值主要由低位决定但单调不减仍然成立所以二分能用。全零串 s00在任意进制下都是 0如果 target0答案是下边界 low即 2。如果 target0无解。很多同学会在全零串的二分里卡住因为 value 永远是 0永远小于 target二分会把 low 一路推到 high最后验证失败这也算正常结果。建议在代码里对全零串直接特判如果所有 digit 都是 0目标也是 0输出最小进制目标不是 0输出无解。特判不算多余它让逻辑更清晰。不过即使不特判二分版本也能得到正确结果只是多跑几次循环而已。5.4 对拍暴力枚举就是最可靠的裁判写完二分我强烈建议你写一个暴力函数从 low 开始一直枚举到 1e6 或更远检查能否找到目标进制。把它和二分答案对拍几千组随机数据。随机数据怎么造就是随机生成一个由 0-9、A-Z 组成的字符串随机生成一个 target然后两个函数输出做比较。我实际对拍时抓到过一个隐藏问题字符串长度超过 1000二分时溢出保护正常但暴力枚举到很远的进制后valueInBase 因为 d base 直接返回 limit1导致比较失真。后来在暴力里也加上同样的判断才真正对齐。对拍代码不用很复杂甚至可以直接在本地写一个 50 行的 checker比人眼查边界可靠得多尤其是这种数据范围大、边界多的题。6. 从这一题总结进制问题的通用套路6.1 进制题最常见的四种变体我刷了几百道题后发现进制题的变体基本绕不开四种。第一种就是 UVa 13090 这种给字符串和十进制目标求最小进制。第二种是给一个十进制数反向求它在某个进制下的表示。第三种是给你一个等式比如ABC DEF GHI求能使等式成立的进制。第四种是判断一个字符串在哪些进制下是回文数、素数或满足某个数论性质。无论哪一种第一步都是先确定字符到数值的映射第二步确定合法进制的下界第三步再考虑用枚举还是二分。把这三步走稳变体再多也万变不离其宗。等式类的问题还要小心运算结果溢出通常会把两边的值同时算到一个 long long 里或者用高精度。6.2 选枚举还是选二分边界在哪里如果进制范围压得很小比如题目保证 base 在 2 到 36 之间那么直接枚举最省事代码也更好读。但如果没有这个保证目标值又很大就一定要二分。判断依据只有一个合法进制的可能范围有多大。范围小用枚举范围大用二分。二分时需要保证 value 关于 base 单调不减而进制题里这个性质几乎天然成立因为每一位数字符号都小于进制所以大进制下每一位的位权都不会变小。如果题目涉及等式两边比如 ABC你还可以先推导出进制的一个二次或一次函数用数学方式直接解出来速度更快。比如形如AB CD EF的式子展开后会得到一个关于 base 的线性方程解出来再验证是否满足每一位 digit 小于 base 即可。6.3 我的个人习惯最后说点我自己的做题习惯。拿到任何进制题我第一件事不是写代码而是先算下界和上界。下界由最大字符决定上界要么由题目限定要么用 target 相关值这两个端点写注释标出来后面调试会省很多时间。其次是保证字符转数字函数只有一个版本不要在多个地方重复写判断否则改一处忘一处迟早炸。最后每次交题前务必对拍一次特别是涉及 long long 和二分的问题极端数据远比你想象的多。如果你刚接触 UVa 13090建议先把暴力版本写出来跑一遍样例再用二分版本替换这样能直观感受到单调性质和边界条件的差别。只要把上面这些点吃透同类的进制题基本不会再让你头疼。我在实际刷题过程中最大的体会是进制题很少考高深算法考的就是基础功和细心尤其手动枚举几个样例之后很多隐藏问题会自己浮出来。

UVa 13090 Base of MJ 进制转换题解：二分查找与溢出处理

相关推荐

Python流程控制实战：条件判断、循环与异常处理核心解析

多智能体框架实战指南：从五万九千颗Star到跑通流水线

Vulkan稀疏资源实战：从内存分配到流式加载的显存优化指南

更多资讯

安卓玩转Unity重制版头文字D3：800×600分辨率调优实战

环形队列与自适应总线：高实时日志系统的硬件级优化

SpringBoot相册系统毕业设计实战：从搭建到一键打包

Unity开发者的iOS Native广告接入指南：AppLovin Max避坑实战

JSP教学管理系统从零到答辩：三层架构、数据库设计与避坑指南

Context-Mode实战：如何让大模型在正确的上下文中工作

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？