首页 > 试题广场 >

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

[编程题]魔导数据包的混合进制编码
  • 热度指数：3174 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红正在术式终端前维护城市结界的能耗监控系统。为了压缩传输过程中的冗余数据，她需要对一个魔力值整数 latex 进行“混合进制编码”处理。
具体编码规程如下：
1. 符号位确定：首先根据 latex 的正负号确定编码序列的第一个数字 latex。若 latex，则 latex；若 latex，则 latex。
2. 进制分解：取 latex（latex 的绝对值）。给定一个包含 latex 个正整数的进制序列 latex。按照序列顺序，对 latex 依次进行如下操作：
对于每个 latex，当前位的编码数字 latex，随后更新 latex。
3. 字符映射：将得到的数字序列 latex 按顺序映射为小写字母，映射规则为 latex。将这些字母拼接，得到最终的编码字符串 latex。
4. 回文校验与提取：
- 若 latex 本身是一个回文字符串，则输出 latex 并在其后紧跟后缀 `(palindrome)`。
- 若 latex 不是回文字符串，则需要提取 latex 中长度最长的回文子串；若存在多个长度相等的最长回文子串，则输出其中字典序最小的一个。

输入描述:

	输入包含两行。

	第一行一个整数 latex（latex），代表待编码的魔力值。

	第二行包含若干个以空格分隔的整数，表示进制序列 latex（latex，latex）。


输出描述:

	输出一个字符串，表示按规程处理后的编码结果。
示例1

输入

-21
5 7 3

输出

bb

说明


	1. latex，故符号位 latex，映射为 'b'。

	2. 初始 latex。

	   - 第一位进制 latex：latex，latex。

	   - 第二位进制 latex：latex，latex。

	   - 第三位进制 latex：latex，latex。

	3. 序列为 latex，映射得到字符串 latex。

	4. "bbea" 不是回文串。其所有的回文子串包括 "b", "e", "a", "bb"。其中最长的是 "bb"，故输出 "bb"。
算法知识视频讲解
添加回答
江流石不转201806230002936头像 江流石不转201806230002936
import java.util.Scanner;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt();
int num = Math.abs(n);
List<Integer> list = new ArrayList();
list.add(n < 0 ? 1 : 0);
int remove = num;
int removeBy = 0;
while (in.hasNext()) {
int x = in.nextInt();
list.add(remove % x);
remove = remove / x;

}
char[] arr = new char[list.size()];
for (int i = 0; i < arr.length; i++) {
arr[i] = (char)('a' + list.get(i));
}

String s = new String(arr);
int len = s.length();
boolean[][] dp = new boolean[len][len];
int maxLen = 1;
int start = 0;
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j <= len-1; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
if (dp[i][j]) {
if (j - i + 1 > maxLen || (j - i + 1 == maxLen &&
(s.charAt(i) < s.charAt(start)))) {
start = i;
maxLen = j - i + 1;
}
}
}
}
if(maxLen==s.length()){
System.out.print(s+"(palindrome)");
}else{
System.out.print(s.substring(start, start + maxLen));
}

}
}
发表于 2026-04-21 04:26:58 回复(0)
Python3
路边的末流头像 路边的末流
#前面是简单的字符串模拟，后面使用中心扩展法提取最大回文子串，要注意有多个的话需要选字典序最小的
def center_expand(left, right):
    while left >= 0 and right < len(sss) and sss[left] == sss[right]:
            left -= 1
            right += 1

    huiwen = sss[left + 1:right]

    return huiwen

n = int(input())
b = list(map(int, input().split()))
d = []
ss = []
huiwen = ''

if n < 0:
    s = 1
    ss.append('b')
else:
    s = 0
    ss.append('a')

q = abs(n)

for i in b:
    d.append(q % i)
    q = q // i

for i in range(len(d)):
    ss.append(chr(d[i] + 97))

sss = ''.join(ss)

max_len = 0

for i in range(len(sss)):
    odd = center_expand(i, i)
    if len(odd) > max_len:
        max_len = len(odd)
        huiwen = odd
    even = center_expand(i, i + 1)
    if len(even) > max_len:
        max_len = len(even)
        huiwen = even

l = []
for i in range(len(sss)):
    odd = center_expand(i, i)
    even = center_expand(i, i + 1)
    if len(odd) == max_len:
        l.append(odd)
    if len(even) == max_len:
        l.append(even)

l.sort()

if huiwen == sss:
    print(f'{l[0]}(palindrome)')
else:
    print(l[0])
       


发表于 2026-04-15 19:22:34 回复(0)
C++
牛客902618362号头像 牛客902618362号
#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
vector<int> arr;
cin >> n;
int temp;
while (cin >>temp ) {
arr.push_back(temp);
}
vector<char> arr2(arr.size()+1, 'a');
if (n <0 ){
arr2[0] = 'b';
n = abs(n);
}else{
arr2[0] ='a';}

for (int i =0; i < arr.size(); i++){
arr2[i+1] = (n % arr[i]) + 'a';
n= floor(n/arr[i]);
}

// for (char i : arr2){
// cout << i << " ";
// }
int m=0 ;
int e = arr2.size()-1;
while (arr2[m]== arr2[e] && m <= e){
m++;
e --;
}
if (m> e){
for (char i : arr2){
cout << i;
}
cout << "(palindrome)";
return 0;
}
auto checker = [&arr2](int i, int bl, int l) {
for (int j =0; j < l; j++){
if (arr2[i+j] < arr2[bl+j]){
return true;
}else if (arr2[i+j] > arr2[bl+j]){
return false;
}
}
return true;
};

vector<vector<bool>> dptable(arr2.size(), vector<bool>(arr2.size(), false));
int best= 1;
int bl =0;
int br = 0;
for(int i =0 ; i < arr2.size(); i++){
dptable[i][i] = true;
if (arr2[i] < arr2[bl]){
bl =i; br =i;
}
}
for (int i= 0; i < arr2.size()-1; i++){
dptable[i][i+1] = (arr2[i]== arr2[i+1]);
if ( dptable[i][i+1] && (best < 2 || (best==2 && checker(i, bl, 2)))){
bl =i; br =i+1;
best =2;
}
}
for (int i = 3 ; i <= arr2.size() ; i++){
for (int j = 0; j < arr2.size() -i +1 ; j ++ ){
int k = j + i -1;
dptable[j][k] = dptable[j+1][k-1] && (arr2[j]== arr2[k]);
if ( dptable[j][k] && (best < i || (best == i && checker(j, bl, i)))){
bl = j; br =k;
best = i;
}
}
}
// for (int i =0; i< arr2.size(); i++){
// for (int j=0; j < arr2.size(); j++){
// cout << dptable[i][j]<< " ";
// }
// cout << endl;
// }
// cout << best << " "<< bl << " "<< br ;

for (int i = bl; i<= br; i++){
cout << arr2[i];
}
}
3道题 check palindrome ，LCS  palindrome DP， sort string 合体也是无敌了
发表于 2026-04-13 11:26:27 回复(0)
Java
准备进厂的coder很胆小头像 准备进厂的coder很胆小
这一个题我就写了一个多小时...
发表于 2026-04-12 23:54:44 回复(0)
TCP_200头像 TCP_200
做这一道题，感觉像做了两道题
import java.util.*;
import java.io.*;
 
public class Main {
    private static String solve(StringBuilder sb) {
        int len = sb.length();
        boolean[][] dp = new boolean[len][len];
        int res = 1;
        int l = 0;
        String s = sb.substring(0, 1);
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
            if (res == 1 && sb.charAt(i) < sb.charAt(l)) {
                l = i;
                s = sb.substring(l, l + 1);
            }
            if (i + 1 < len) {
                if (sb.charAt(i) == sb.charAt(i + 1)) {
                    dp[i][i + 1] = true;
                    if (res == 1) {
                        res = 2;
                        l = i;
                        s = sb.substring(l, l + 2);
                    } else {
                        if (sb.substring(i, i + 2).compareTo(s) < 0) {
                            l = i;
                            s = sb.substring(l, l + 2);
                        }
                    }
                }
            }
        }
        for (int i = len - 3; i >= 0; i--) {
            for (int j = i + 2; j < len; j++) {
                if (sb.charAt(i) == sb.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (j - i + 1 == res) {
                        if (sb.substring(i, j + 1).compareTo(s) < 0) {
                            l = i;
                            s = sb.substring(i, j + 1);
                        }
                    } else if (j - i + 1 > res) {
                        res = j - i + 1;
                        l = i;
                        s = sb.substring(i, j + 1);
                    }
                }
            }
        }
        return s.length() == len ? s + "(palindrome)" : s;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine().trim()); // 待编码的魔力值
 
        List<integer>s = new ArrayList<>();
        if (n < 0) {
            s.add(1);
            n = -n;
        } else s.add(0);
 
        String[] bases = br.readLine().trim().split("\\s+");
        int len = bases.length;
        int[] b = new int[len];
        for (int i = 0; i < len; i++) {
            b[i] = Integer.parseInt(bases[i]);
            s.add(n % b[i]);
            n /= b[i];
        }
        StringBuilder sb = new StringBuilder();
        for (int num : s) {
            sb.append((char)(num + 'a'));
        }
        pw.println(solve(sb));
        pw.flush();
    }
}


发表于 2026-04-11 14:51:55 回复(0)
提交观点

问题信息

难度：
5条回答 151浏览

热门推荐

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号