💻 魔导数据包的混合进制编码
华为 · 字符串 · 算法编程题
华为
字符串
n ≤ 1e6
时限 1 秒 / 256 MB
题目描述
小红正在术式终端前维护城市结界的能耗监控系统。为了压缩传输过程中的冗余数据，她需要对一个魔力值整数 n 进行“混合进制编码”处理。
具体编码规程如下：
1. 符号位确定：首先根据 n 的正负号确定编码序列的第一个数字 s 。若 n < 0 ，则 s = 1 ；若 n ≥ 0 ，则 s = 0 。
2. 进制分解：取 q = |n| （ n 的绝对值）。给定一个包含 m 个正整数的进制序列 b_1, b_2, ..., b_m 。按照序列顺序，对 q 依次进行如下操作：
对于每个 b_i ，当前位的编码数字 d_i = q mod b_i ，随后更新 q = ⌊ q / b_i ⌋ 。
3. 字符映射：将得到的数字序列 (s, d_1, d_2, ..., d_m) 按顺序映射为小写字母，映射规则为 0 → 'a', 1 → 'b', ..., 25 → 'z' 。将这些字母拼接，得到最终的编码字符串 S 。
4. 回文校验与提取：
- 若 S 本身是一个回文字符串，则输出 S 并在其后紧跟后缀 `(palindrome)`。
- 若 S 不是回文字符串，则需要提取 S 中长度最长的回文子串；若存在多个长度相等的最长回文子串，则输出其中字典序最小的一个。
输入输出
输入描述
输入包含两行。
第一行一个整数 n （ -10^6 ≤ n ≤ 10^6 ），代表待编码的魔力值。
第二行包含若干个以空格分隔的整数，表示进制序列 b_1, b_2, ..., b_m （ 1 ≤ m ≤ 10 ， 2 ≤ b_i ≤ 26 ）。
输出描述
输出一个字符串，表示按规程处理后的编码结果。
样例共 1 组
样例 1 · 1. n = -21 < 0 ，故符号位 s = 1 ，映射为 'b'。
2. 初始 q = |-21| = 21 。
- 第一位进制 b_1 = 5 ： d_1 = 21 mod 5 = 1 ， q = ⌊ 21 / 5 ⌋ = 4 。
- 第二位进制 b_2 = 7 ： d_2 = 4 mod 7 = 4 ， q = ⌊ 4 / 7 ⌋ = 0 。
- 第三位进制 b_3 = 3 ： d_3 = 0 mod 3 = 0 ， q = ⌊ 0 / 3 ⌋ = 0 。
3. 序列为 (1, 1, 4, 0) ，映射得到字符串 S = "bbea" 。
4. "bbea" 不是回文串。其所有的回文子串包括 "b", "e", "a", "bb"。其中最长的是 "bb"，故输出 "bb"。
算法解析依据一般
考点：字符串
数据规模 n ≤ 1e6 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
题目画像
- 数据规模：n ≤ 1e6，m ≤ 10
- 元素值域：b_i ≤ 26（注意整数类型选择，避免溢出）
- 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
- 源站时限：1 秒（牛客口径，非本题专属门槛）
解题思路
参考方向：字符串
按字符逐个处理，或利用字符串的前后缀性质加速匹配。
思路框架（字符串 通法 · 非本题专属）
- 明确操作对象是字符还是子串、是否需要保持原顺序。
- 子串问题常用双指针 / 滑动窗口；回文问题可用中心扩展或哈希。
- 多模式匹配考虑 Trie 或 KMP；只需计数则用哈希表统计字符频次。
- 注意字符集大小写敏感性与输入是否带引号。
实现要点：Python 切片 s[l:r+1] 取子串；注意字符串不可变，频繁拼接改用 list。
复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)
该范式的通法易错点
- 下标与切片边界差 1。
- 忽略了大小写、空白字符的影响。
对照本题
- 数据规模 n ≤ 1e6，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
- 元素值域最大到 26 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例解读
样例 1：输入 -21 / 5 7 3 → 输出 bb
- n = -21 < 0 ，故符号位 s = 1 ，映射为 'b'。
- 初始 q = |-21| = 21 。
- 第一位进制 b_1 = 5 ： d_1 = 21 mod 5 = 1 ， q = ⌊ 21 / 5 ⌋ = 4 。
- 第二位进制 b_2 = 7 ： d_2 = 4 mod 7 = 4 ， q = ⌊ 4 / 7 ⌋ = 0 。
- 第三位进制 b_3 = 3 ： d_3 = 0 mod 3 = 0 ， q = ⌊ 0 / 3 ⌋ = 0 。
- 序列为 (1, 1, 4, 0) ，映射得到字符串 S = "bbea" 。
- "bbea" 不是回文串。其所有的回文子串包括 "b", "e", "a", "bb"。其中最长的是 "bb"，故输出 "bb"。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解