题目链接

魔导数据包的混合进制编码

题目描述

小红需要对一个魔力值整数 进行“混合进制编码”。具体规则如下：

  1. 符号位：若 ，第一个数字 ；若 ，第一个数字 。
  2. 进制分解：取 。给定进制序列 。按顺序对每个 执行：
    • 当前位编码数字 。
    • 更新 。
  3. 字符映射：将数字序列 映射为小写字母（），得到字符串 。
  4. 回文处理：
    • 若 本身是回文串，输出 。
    • 否则，输出 中长度最长的回文子串。若有多个长度相等的最长回文子串，输出字典序最小的一个。

解题思路

  1. 编码过程：

    • 按照题目步骤，先确定符号位，再依次对进制序列取模并更新 。注意 的绝对值可能达到 ，需使用 64 位整数。
    • 得到的数字序列长度为 ，映射为字符后得到长度为 的字符串 。

  2. 回文校验与提取：

    • 首先检查 是否为回文。若是，直接按格式输出。
    • 若不是，需要寻找最长回文子串。由于字符串长度 可达 ，必须使用高效算法。
    • Manacher 算法：可以在 时间内求出以每个位置为中心的最长回文半径。
    • 提取最长子串：
      • 通过 Manacher 得到的半径数组，找到最大半径对应的长度 。
      • 遍历所有中心，记录所有长度等于 的回文子串。
      • 在这些子串中找到字典序最小的一个。

  3. 字典序比较优化：

    • 如果直接提取所有最长回文子串并排序，空间和时间可能会超限。
    • 实际上，由于 固定，我们可以通过比较子串内容来更新最小值。

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// Manacher 算法寻找最长回文子串
string findLongestPalindrome(string s) {
    if (s.empty()) return "";
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    int n = t.length();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int maxLen = 0;

    for (int i = 0; i < n; ++i) {
        if (i < right)
            p[i] = min(right - i, p[2 * center - i]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1])
            p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        if (p[i] > maxLen) maxLen = p[i];
    }

    string best = "";
    for (int i = 0; i < n; ++i) {
        if (p[i] == maxLen) {
            int start = (i - maxLen) / 2;
            string sub = s.substr(start, maxLen);
            if (best == "" || sub < best) {
                best = sub;
            }
        }
    }
    return best;
}

int main() {
    long long v;
    cin >> v;
    vector<int> b;
    int temp_b;
    while (cin >> temp_b) {
        b.push_back(temp_b);
    }

    string s = "";
    // 1. 符号位
    s += (char)((v >= 0 ? 0 : 1) + 'a');

    // 2. 进制分解
    long long x = abs(v);
    for (int base : b) {
        int d = x % base;
        s += (char)(d + 'a');
        x /= base;
    }

    // 3. 回文校验
    string rev_s = s;
    reverse(rev_s.begin(), rev_s.end());
    if (s == rev_s) {
        cout << s << "(palindrome)" << endl;
    } else {
        // 4. 提取最长回文子串
        cout << findLongestPalindrome(s) << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextLong()) return;
        long v = sc.nextLong();
        List<Integer> b = new ArrayList<>();
        while (sc.hasNextInt()) {
            b.add(sc.nextInt());
        }

        StringBuilder sb = new StringBuilder();
        // 1. 符号位
        sb.append((char) ((v >= 0 ? 0 : 1) + 'a'));

        // 2. 进制分解
        long x = Math.abs(v);
        for (int base : b) {
            int d = (int) (x % base);
            sb.append((char) (d + 'a'));
            x /= base;
        }

        String s = sb.toString();
        String revS = new StringBuilder(s).reverse().toString();

        if (s.equals(revS)) {
            System.out.println(s + "(palindrome)");
        } else {
            System.out.println(findLongestPalindrome(s));
        }
    }

    private static String findLongestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        StringBuilder tsb = new StringBuilder("#");
        for (int i = 0; i < n; i++) {
            tsb.append(s.charAt(i)).append("#");
        }
        String t = tsb.toString();
        int m = t.length();
        int[] p = new int[m];
        int center = 0, right = 0;
        int maxLen = 0;

        for (int i = 0; i < m; i++) {
            if (i < right) {
                p[i] = Math.min(right - i, p[2 * center - i]);
            }
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) {
                p[i]++;
            }
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            if (p[i] > maxLen) {
                maxLen = p[i];
            }
        }

        String best = null;
        for (int i = 0; i < m; i++) {
            if (p[i] == maxLen) {
                int start = (i - maxLen) / 2;
                String sub = s.substring(start, start + maxLen);
                if (best == null || sub.compareTo(best) < 0) {
                    best = sub;
                }
            }
        }
        return best;
    }
}

def solve():
    # 读取输入
    v = int(input())
    b_list = list(map(int, input().split()))
    
    # 1. 符号位
    res = []
    res.append(chr((0 if v >= 0 else 1) + ord('a')))
    
    # 2. 进制分解
    x = abs(v)
    for base in b_list:
        d = x % base
        res.append(chr(d + ord('a')))
        x //= base
        
    s = "".join(res)
    
    # 3. 回文校验
    if s == s[::-1]:
        print(f"{s}(palindrome)")
        return

    # 4. Manacher 算法寻找最长回文子串
    t = "#" + "#".join(s) + "#"
    n = len(t)
    p = [0] * n
    center = 0
    right = 0
    max_len = 0
    
    for i in range(n):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
            p[i] += 1
        if i + p[i] > right:
            center = i
            right = i + p[i]
        if p[i] > max_len:
            max_len = p[i]
            
    # 提取所有最长回文子串并找字典序最小的
    best = None
    for i in range(n):
        if p[i] == max_len:
            start = (i - max_len) // 2
            sub = s[start : start + max_len]
            if best is None or sub < best:
                best = sub
                
    print(best)

solve()

算法及复杂度

  • 算法：混合进制转换 + Manacher 算法。
  • 时间复杂度：。其中 为进制序列的长度。Manacher 算法可以在线性时间内找到所有回文中心。
  • 空间复杂度：。用于存储字符串和 Manacher 算法的辅助数组。