对于牛客网—语言学习篇—编程初学者入门训练—函数类型：BC156 牛牛的数组匹配及BC158 回文数解析

开篇介绍：

在前两篇博客中，我说会对这两道较为困难的题目进行解析，于是，它们来了，这两道题牛客网中评定的难度也是为中等，所以虽然看起来很难，但是也并不能算是多难，关键在于我们思路的一个突破局限以及发散思维，所以大家并不用对这两道题望而却步，大胆地去尝试，无所畏惧，失败并不可怕，可怕的是我们害怕失败，俗话说得好，失败是成功它妈，不经历风雨怎么看见彩虹，所以请大家相信自己，用于跨出自己的舒适区，大胆挑战难题，在当下这个内卷的时代，唯有坚持者胜！望诸君共勉！！！

下面给出这两道题的链接，我比较建议大家可以在看我的解析之前就去尝试着作答题目，毕竟唯有自己亲身体验过，才知道自己行不行。

牛牛的数组匹配_牛客题霸_牛客网https://www.nowcoder.com/practice/3d3406f4a7eb4346b025cc592be5b875?tpId=290&tqId=2370143&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E8%25AF%25AD%25E8%25A8%2580%25E5%25AD%25A6%25E4%25B9%25A0%25E7%25AF%2587%26topicId%3D290回文数_牛客题霸_牛客网https://www.nowcoder.com/practice/a432eb24b3534c27bdd1377869886ebb?tpId=290&tqId=171415&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E8%25AF%25AD%25E8%25A8%2580%25E5%25AD%25A6%25E4%25B9%25A0%25E7%25AF%2587%26topicId%3D290

BC156 牛牛的数组匹配：

我们先讲这道题，这道题的难度算是较小的一道，我们先看题目：

题意分析：

拿到一道题目，我们首先要做的就是进行对题目的分析，理解题目的意思，寻找题目给我们埋的坑并躲过去。

所以，我们来分析这道题目想要我们做的是什么？首先该题要求我们输入两个整数，第一个整数是后续输入的第一个数组的数据长度，第二个整数则是后续输入的第二个数组的数据长度，在输入完两个整数之后，我们便要依次给两个数组输入数据，解决完这些后，题目便要求我们去寻找第二个数组中哪一段连续的子数组最接近第一个数组的数据之和，这里的子数组的意思是假设有22 42 33  55四个数据，第一个子数组就是22 42，第二个数组就是22 42 33，第三个子数组则是22 42 33 55，第四个子数组是42 33，第五个子数组是42 33 55，第六个子数组是33 55 ，除此之外还有22/42/33/45这四个单独数字的子数组，其实这个知识类似高中数学中集合的子集的概念，大学生肯定不陌生，了解之后子数组的概念之后，我们便知道题目的意思就是让我们去判断数组中的哪一段子数组之和最接近第一个数组之和，那么就是需要我们把第二个数组的每一个子数组之和去与第一个数组之和进行比较，这样子才会避免遗漏某个子数组，当将所有子数组都进行比较之后，再去把最接近的那一段子数组表达出来，如果多段子数组同样接近，那就输出最前面（即最左边）的那一段子数组。

开始解题：

知道了题目的意思之后，我们就可以开始思考如何去解决这一道题目了，首先我们肯定可以明确的就是创建变量接收所输入的数据这一步骤，根据上文，我们可以知道，题目要输入两个整型，两个数组，所以我们也要相应的创建这么几个变量，这一步的话，相信大家肯定是手拿把掐，所以我也就不在这里过多叙述，直接上代码：

int n, m;
scanf("%d%d", &n, &m);
int arr_a[100] = {0};
int arr_b[100] = {0};
for (int i = 0; i < n; i++) 
{
    scanf("%d", &arr_a[i]);
}
for (int i = 0; i < m; i++) 
{
    scanf("%d", &arr_b[i]);
}

做完这一步之后，我们肯定就开始会不可避免的陷入迷茫了，接下来要做什么？其实不必迷茫，上面的题分析已经提到了，我们要去将第二个数组的一个个子数组之和分别去与第一个数组的总和比较，那我们首先肯定得知道第一个数组的总和，然后才能进行比较，所以，接下来一步，我们就得去计算第一个数组的总和，这一步不必多说，也是很简单的一步，创建一个变量在遍历第一个数组时去接收总和就行，老生常谈的话题了，大家肯定不陌生，代码如下：

// 计算数组 a 的总和
int target = 0;
for (int i = 0; i < n; i++) {
    target += arr_a[i];
}  

又完成了一步，这也就代表着我们离成功更进一步了，那么接下来，我们要做什么呢？哦！我知道，我要想办法去求第二个数组的子数组之和，对的，很聪明，我们接下来就是要实现这一步，只不过问题是，我们要怎么做呢？不必着急，且听我道来

首先，我们得清楚子数组的概念，而经过了上述的题意分析，想必大家肯定是了解甚多了，只是单单知道概念还不够，我们还需要知道子数组的特征，这样子我们才能想办法使用代码去实现这一步骤，我们再看一个例子:

1. 长度为 1 的子数组（单个元素）

• [22]（下标 0，即 arr [0]）
• [42]（下标 1，即 arr [1]）
• [33]（下标 2，即 arr [2]）
• [55]（下标 3，即 arr [3]）

2. 长度为 2 的子数组（连续两个元素）

• [22, 42]（下标 0~1，即 arr [0]、arr [1]）
• [42, 33]（下标 1~2，即 arr [1]、arr [2]）
• [33, 55]（下标 2~3，即 arr [2]、arr [3]）

3. 长度为 3 的子数组（连续三个元素）

• [22, 42, 33]（下标 0~2，即 arr [0]、arr [1]、arr [2]）
• [42, 33, 55]（下标 1~3，即 arr [1]、arr [2]、arr [3]）

4. 长度为 4 的子数组（整个数组）

• [22, 42, 33, 55]（下标 0~3，即 arr [0]、arr [1]、arr [2]、arr [3]）

假设我们要求[22, 42, 33]这一个子数组的总和，那么我们要怎么实现呢？首先我们知道这个子数组的下标从0开始，到2结束。如果只是让我们求这一段子数组的总和的话，那肯定不难，我们可以使用这么一段代码实现：

int sum = 0;
for (int i = 0; i < 3; i++)
{
    sum = sum + arr_b[i];
}

可问题在于我们不是只求这么一段子数组的总和，我们还可能要求[42, 33, 55]、[22, 42]、[42, 33]等等一些子数组的总和，那这么看来，感觉只用一个循环，似乎不太够用呀，因为对于[22, 42, 33]这一段子数组，我们是令i从0开始，可是要是要求[42, 33, 55]这一段子数组，我们就得让i从1开始，可是这么一来，i就一个，怎么可能让它分身，又是从0开始，又是从1开始呢？

所以，很明显，i需要帮手，那j一听，直接大喊：我来！！！，哈哈，i一个不够，j来搭把手，这么一来，这个求每一段子数组之和的步骤就已经无限接近结束了，我们已经明确了需要两个循环，那么第一个i循环，肯定是要让它从0开始，不难子数组遍历就会不完全，但是j要从哪里开始呢？从1？从0？从10086？……哈哈哈

在解答这个问题之前，我们不妨思考一个问题，我们要把记录子数组之和这一步放在哪个循环里面呢？i循环还是j循环？亦或是两个都放？两个肯定不行，太贪心了，那么，是要放在i还是j呢？大家不用猜来猜去的了，答案是放在j循环中，上面我们知道了i从0开始，而i的作用是什么呢，我这里也直接给出答案，其实i的作用就是负责子数组中第一个元素的移动，比如求[22, 42, 33]时，i就是要为0，对应22，而求[42, 33, 55]时，i就得是1，对于42，我们在想想，什么时候才会进行子数组第一个元素为原数组的第二个元素开始呢？很明显肯定是要已经结束了子数组从第一个元素为原数组的第一个元素开始的所以遍历，即[22, 42, 33, 55]，这一个结束之后，才能进行移动（即子数组第一个元素为原数组的第二个元素开始），所以，i就是负责子数组的一个元素的移动，

那么知道了i的作用之后，我们也很快就能推测出j的作用了，很显然，j的作用就是负责子数组中除第一个元素之外的其他元素的移动，但是同时，j还得负担起接收数组第一个元素的功能（其实这个影响不大，我们可以用arr_b[i]来表示子数组中的第一个元素，但是我们也可以用arr_b[j]去表示子数组中的第一个元素，为了方便以及更直的观察·代码，我们一般使用arr_b[j]去表示子数组中的第一个元素，至于怎么让j实现这个功能，且看下文）。

于是，经过了上一段的了解，我们已经知道了i和j的作用，并且知道i是要从0开始，那么j要从哪里开始呢？其实答案也很显而易见，j要从i开始（如果你要用arr_b[i]来表示子数组中的第一个元素，那可以让j从i+1开始，再用arr_b[i]+arr_b[j]），因为j要负责子数组中除第一个元素之外的其他元素的移动，举个例子，帮助大家能更加清晰的了解：

假设i为0的时候，我们让j从i开始，直到到有效数据长度的前一个结束（因为数组从0开始存储），那么arr[j]就会依次是22、42、33、55,当j等于0（即i）的时候，就相当于是求子数组[22]的总和，当j==1的时候，就相当于是求子数组[22, 42]的总和，而当j==2的时候，就相当于是求子数组[22, 42, 33]的总和，而当j==3的时候，就相当于是求子数组[22, 42, 33, 55]的总和。

当到达了55（即数组中的最后一个元素）之后，通过上文我们知道了，要让i+1了，将子数组的第一个元素后移了，于是这个时候i就得变成1了，然后j再从i（也就是1开始），当j==1的时候，就相当于是求子数组[42]的总和，而当j==2的时候，就相当于是求子数组[42, 33]的总和，而当j==3的时候，就相当于是求子数组[42, 33, 55]的总和，接着i再+1，进行上述步骤的重复。

所以，我们也就知道要如何实现求出每一个子数组之和了，下面是这一部分的代码，大家结合着上文去理解，相信必定会简单如喝水。

// 枚举所有可能的连续子数组
int sum1 = 0;
for (int i = 0; i < m; i++)
{
    for (int j = i; j < m; j++)
    {
        sum = sum + arr[j];
    }
}

解决了上面的问题之后，我们就要思考，怎么去判断哪一个子数组的和最接近第一个数组的总和，首先，大家应该不难想到，我们可以去使用作差法，将第一个数组的总和去减去第二个数组每一个子数组之和，也就是int diff = sum-sum1;，看哪一段子数组的diff最小，但是这里我们要注意，diff有可能会为负数，那么负数的比较肯定不行，所以我们应该得到差的绝对值，这样子才能进行正常的比较，于是，我们就需要c语言中的abs函数了：

abs函数：

abs函数的基本概念

abs函数用于计算一个数的绝对值。绝对值是指一个数在数轴上与原点的距离，无论该数是正数、负数还是零，其绝对值总是非负的。

abs函数的使用方法

abs函数通常接受一个数值参数，返回该参数的绝对值。语法如下：

abs(x)

其中，x可以是整数、浮点数或复数。

abs函数的返回值

对于整数和浮点数，abs函数返回其非负值。例如：

abs(-5)      # 返回 5
abs(3.14)    # 返回 3.14
abs(0)       # 返回 0

对于复数，abs函数返回其模（magnitude），即复数在复平面上的距离。例如：

abs(3 + 4j)  # 返回 5.0

abs函数的实际应用

绝对值函数在数学和编程中有广泛的应用，例如计算误差、距离或处理负数情况。以下是一个简单的示例，计算两个数的差的绝对值：

a = 10
b = 15
difference = abs(a - b)  # 返回 5

abs函数的注意事项

abs函数只能作用于数值类型的数据。如果传入非数值类型（如字符串或列表），会引发TypeError。例如：

abs("hello")  # 引发 TypeError

abs函数的扩展

在某些编程语言中，abs函数可能以不同的形式出现，例如在C语言中，可以使用fabs函数处理浮点数，abs函数处理整数。在Python中，abs函数统一处理所有数值类型。

所以diff应该是 diff =abs（ sum-sum1）。

知道了怎么比较子数组与第一个数组的总和之后，我们就得想办法解决怎么去比较每一个子数组与第一个数组的总和呢？其实这个也不难，由于我在之前的一篇博客中有讲过这一点，所以我这里就不进行赘述，大家可以直接看这一篇博客：对于判断素数（质数）以及牛客网—语言学习篇—编程初学者入门训练—复合类型：字符/字符数组的题目解析-CSDN博客其中的笨小猴这一部分，我在这里就直接给出代码：

for (int i = 0; i < m; i++) 
{
    int current_sum = 0;
    for (int j = i; j < m; j++) 
    {
        current_sum += arr_b[j];
        int diff = abs(current_sum - target);

        if (diff < min_diff || (diff == min_diff && i < start_idx)) 
        {
            min_diff = diff;
        }
    }
}

(diff == min_diff && i < start_idx)//如果多段子数组同样接近，那就输出最前面（即最左边）的那一段子数组

通过这段代码，我们可以知道，当出来了循环后此时的min_diff便是第二个数组中的某一段子数组与第一个数组总和之差的最小值

那么我们是通过min_diff知道了第二个数组中的某一段子数组与第一个数组总和之差的最小值，可问题是，题目要求我们把这一段子数组表达出来，我们光知道没有用，我们只知道差的最小值，又不知道是哪一段子数组，这就很纳闷了。

不用慌，当我们遇到困难的时候，不妨大声呼喊：i！！！j！！！，哈哈哈，是的，我们可以通过i和j去找到这一段子数组呀，因为经过上面的分析，大家也都知道，i和j的作用便是去枚举第二个数组的所有子数组，所以就代表着如果我们能知道当取得最小值那个时候的i和j，不就能顺理成章的知道了那一段子数组了吗，是的，不需要1999，也不需要199，更不需要99，只需要i和j，你就可以把子数组带回家。

所以知道了我们需要要i和j之后，剩下的也就很简单了，我们设置两个变量去接收（记录）i和j就行啦，大家应该这一个没问题吧，这个可以说是一个编程初学者的基础自我修养了，下面便给出代码：

// 枚举所有可能的连续子数组
for (int i = 0; i < m; i++) 
{
    int current_sum = 0;
    for (int j = i; j < m; j++) 
    {
        current_sum += arr_b[j];
        int diff = abs(current_sum - target);
        
        // 差值更小，或差值相等但起始点更左
        if (diff < min_diff || (diff == min_diff && i < start_idx)) 
        {
            min_diff = diff;
            start_idx = i;
            end_idx = j;
        }
    }
}

在进行完了这一步之后，我们就可以把子数组表达出来了，从 start_idx（i）开始，到end_idx（j）结束就行，如下：

// 输出结果
for (int i = start_idx; i <= end_idx; i++) 
{
     printf("%d ", arr_b[i]);
}

由此，本道小难题也就结束啦，下面给出完整代码，大家可以看着代码再次加强印象。

#include <stdio.h>

int main() 
{
    int n, m;
    scanf("%d%d", &n, &m);
    int arr_a[100] = {0};
    int arr_b[100] = {0};
    for (int i = 0; i < n; i++) 
    {
        scanf("%d", &arr_a[i]);
    }
    for (int i = 0; i < m; i++) 
    {
        scanf("%d", &arr_b[i]);
    }
    
    // 计算数组 a 的总和
    int target = 0;
    for (int i = 0; i < n; i++) 
    {
        target += arr_a[i];
    }
    
    int min_diff = abs(arr_b[0] - target); // 最小差值
    int start_idx = 0, end_idx = 0;        // 记录最优子数组的起始和结束索引
    
    // 枚举所有可能的连续子数组
    for (int i = 0; i < m; i++) 
    {
        int current_sum = 0;
        for (int j = i; j < m; j++) 
        {
            current_sum += arr_b[j];
            int diff = abs(current_sum - target);
            
            // 差值更小，或差值相等但起始点更左
            if (diff < min_diff || (diff == min_diff && i < start_idx)) 
            {
                min_diff = diff;
                start_idx = i;
                end_idx = j;
            }
        }
    }
    // 输出结果
    for (int i = start_idx; i <= end_idx; i++) 
    {
        printf("%d ", arr_b[i]);
    }
    return 0;
}

下面再给大家提供一个针对上面代码的超级详细的注释版本，帮助大家进一步理解。

// 引入标准输入输出库，该库包含了printf和scanf等输入输出函数的定义
// 没有这个库，程序将无法进行输入和输出操作
#include <stdio.h>

// 主函数，程序从这里开始执行
// int是函数返回值类型，表示该函数会返回一个整数
// main是函数名，是C语言规定的程序入口函数名
int main() 
{
    // 定义两个整数变量n和m
    // n将用于存储第一个数组（arr_a）的元素个数
    // m将用于存储第二个数组（arr_b）的元素个数
    int n, m;
    
    // 从标准输入（键盘）读取两个整数，分别存入n和m
    // %d是格式控制符，表示要读取一个十进制整数
    // &n和&m表示取变量n和m的地址，scanf需要通过地址来修改变量的值
    // 输入格式例如："3 5"，表示n=3，m=5
    scanf("%d%d", &n, &m);
    
    // 定义两个整型数组，大小均为100，初始值都设为0
    // arr_a将用来存储第一个数组的数据
    // arr_b将用来存储第二个数组的数据（我们要从这个数组中寻找目标子数组）
    // 数组大小设为100是为了满足大部分常见输入规模，避免数组越界
    int arr_a[100] = {0};
    int arr_b[100] = {0};
    
    // 循环读取arr_a的元素，共读取n个
    // 循环变量i从0开始，每次循环后加1，直到i >= n时结束循环
    // 因为数组下标从0开始，所以arr_a[0]是第一个元素，arr_a[n-1]是最后一个元素
    for (int i = 0; i < n; i++) 
    {
        // 从键盘读取一个整数，存入arr_a的第i个位置
        // 例如当i=0时，存入arr_a[0]；i=1时，存入arr_a[1]，以此类推
        scanf("%d", &arr_a[i]);
    }
    
    // 循环读取arr_b的元素，共读取m个
    // 原理同上面读取arr_a的循环
    for (int i = 0; i < m; i++) 
    {
        // 从键盘读取一个整数，存入arr_b的第i个位置
        scanf("%d", &arr_b[i]);
    }
    
    // 定义变量target，用于存储数组arr_a所有元素的总和
    // 这个总和是我们后续寻找子数组的目标值（要找和最接近target的子数组）
    int target = 0;
    
    // 循环遍历arr_a的所有元素，计算它们的总和
    // 从第一个元素（i=0）加到最后一个元素（i=n-1）
    for (int i = 0; i < n; i++) 
    {
        // 每次循环将arr_a[i]的值累加到target中
        // 等价于target = target + arr_a[i]
        target += arr_a[i];
    }
    
    // 定义变量min_diff，用于记录当前找到的子数组和与target的最小绝对差值
    // 初始值设为arr_b[0]与target的绝对差值（使用abs函数求绝对值）
    // 这样设置是因为一开始还没有找到任何子数组，先以第一个元素作为初始参考
    int min_diff = abs(arr_b[0] - target);
    
    // 定义变量start_idx和end_idx，用于记录最优子数组的起始下标和结束下标
    // 初始时，假设arr_b[0]是最优子数组，所以起始和结束下标都设为0
    int start_idx = 0, end_idx = 0;       
    
    // 外层循环：枚举子数组的所有可能起始位置
    // i表示子数组的起始下标，从0开始，到m-1结束（覆盖arr_b的所有元素作为起点）
    for (int i = 0; i < m; i++) 
    {
        // 定义变量current_sum，用于存储当前子数组的总和
        // 每次切换起始下标i时，都要将current_sum重置为0，重新开始计算新子数组的和
        int current_sum = 0;
        
        // 内层循环：枚举以i为起始下标的所有可能结束位置
        // j表示子数组的结束下标，从i开始（子数组至少包含一个元素），到m-1结束
        // 这样就能遍历所有以i为起点的连续子数组（i~i, i~i+1, ..., i~m-1）
        for (int j = i; j < m; j++) 
        {
            // 将arr_b[j]累加到current_sum中，得到从i到j的子数组的总和
            // 例如当i=0, j=0时，current_sum = arr_b[0]
            // 当i=0, j=1时，current_sum = arr_b[0] + arr_b[1]，以此类推
            current_sum += arr_b[j];
            
            // 计算当前子数组和（current_sum）与目标值（target）的绝对差值
            // 用abs函数确保差值为非负数，方便比较哪个子数组更接近目标
            int diff = abs(current_sum - target);
            
            // 判断当前子数组是否比之前找到的子数组更优：
            // 情况1：当前差值diff小于最小差值min_diff → 更接近目标，需要更新
            // 情况2：差值相等（diff == min_diff），但当前子数组的起始下标i更小 → 按题目要求选择更靠左的子数组
            if (diff < min_diff || (diff == min_diff && i < start_idx)) 
            {
                min_diff = diff;    // 更新最小差值为当前diff
                start_idx = i;      // 更新最优子数组的起始下标为当前i
                end_idx = j;        // 更新最优子数组的结束下标为当前j
            }
        }
    }
    
    // 循环打印找到的最优子数组的所有元素
    // 从start_idx开始，到end_idx结束（包括start_idx和end_idx）
    for (int i = start_idx; i <= end_idx; i++) 
    {
        // 打印arr_b[i]的值，后面加一个空格，使元素之间用空格分隔
        printf("%d ", arr_b[i]);
    }
    
    // 主函数返回0，表示程序正常执行结束
    // 在C语言中，main函数返回0通常表示成功，返回非0表示有错误
    return 0;
}

即如上。

BC158 回文数：

这道题的难度，绝对算是难，我们先看题目：

光看题目就觉得这道题强的可怕有木有，我们还是老规矩，先来分析一下这道题目：

题意分析：

一、核心概念：回文数定义

题目中回文数的判定标准是 “首位不为零，且从左向右读和从右向左读完全一致” ，且该规则适用于任意进制（2~10、16 进制）。

例如（以 10 进制为例）：

• 121 是回文数：左右对称，首位 1 ≠ 0，正读反读均为 121。
• 12 不是回文数：反读为 21，与原数不同。
• 011 不合法（隐含规则）：首位为 0，不符合 “首位不为零” 要求，即便对称也不视为回文数。

二、题目流程逻辑

程序需实现的核心流程：

1. 输入：给定进制 N（2≤N≤10 或 N=16）和对应进制的数 M。
2. 迭代操作：
   • 对当前数 M，生成其 “反转数”（如 10 进制 87 的反转数是 78）。
   • 将 M 与反转数在 N 进制下相加，得到新数 M'。
   • 检查 M' 是否为回文数，若是则停止；若否，重复上述步骤（最多迭代 30 次）。
3. 输出：
   • 若 30 步内（含 30 步）得到回文数，输出 STEP=步数。
   • 若 30 步后仍未得到，输出 Impossible!。

三、典型示例拆解

以题目中 10 进制数 87 为例，完整流程如下：

最终输出 STEP=4，表示 4 步得到回文数。

二进制示例：初始数 M = 110（2 进制，对应十进制 6 ）

 最终输出 STEP=1。

8 进制示例：M=145（8 进制）完整迭代流程

最终输出 STEP=10

16 进制示例：M=1A5（16 进制，十进制 1×256 + 10×16 + 5 = 421）

结论：

该示例在第 12 步得到 16 进制回文数 67AAAA76，最终输出 STEP=12。

16 进制特有注意事项：

• 16 进制数字范围：0-9、A(10)、B(11)、C(12)、D(13)、E(14)、F(15)
• 加法规则：逢 16 进 1（如 F+2=11，16 进制）
• 回文数判定：首位非 0 且正读与反读完全一致（如 ABA 是回文数）

1. 字母处理：A-F 需严格区分大小写（通常用大写），计算时需转换为对应数值（A=10 至 F=15）。
2. 进位规则：相加结果≥16 时进位（如 F+2=11，16 进制），注意高位可能连续进位。
3. 反转数前导 0：如 10A21A0 反转后是 0A12A01，需忽略前导 0，有效反转数为 A12A01。

四、特殊场景说明

1. 进制适配：规则对任意进制生效。例如：

   • 2 进制数 101（对应 10 进制 5）：反转数为 101，相加后仍为 101，1 步即可判定为回文数。
   • 16 进制数 A3（对应 10 进制 163）：反转数为 3A（10 进制 58），需按 16 进制规则相加（A3 + 3A = DD，16 进制 DD 正读反读一致，是回文数）。

2. 边界情况：

   • 输入本身已是回文数（如 10 进制 121）：直接输出 STEP=0（0 步达成）。
   • 30 步内无法收敛（如某些 “利克瑞尔数” 特征数）：输出 Impossible!。

五、输入输出规则

• 输入：
  • 两行输入，第一行是进制 N，第二行是 N 进制表示的数 M（如 16 进制输入可能包含 A-F，需用对应格式读取）。
• 输出：严格匹配 STEP=ans 或 Impossible!，需注意大小写和格式。

开始解题：

看完了上面的题意分析之后，大家应该能对这道题目了解的多一些了，这边再推荐先去看看这篇博客中的进制转换：对于牛客网—语言学习篇—编程初学者入门训练—函数类型：函数的后7题题目题解析-CSDN博客

会对这道题的解答有所帮助。

所以，我们需要知道，这道题始终都要按照进制去进行转换以及相加，并且由于16进制的表达方式有字母，所以我们还得把16与其他进制分开来进行计算，而且在输入的时候，也得是非16进制统一使用%d输入，而16进制就得使用%x进行输入。

首先，我们要实现对M的回文转换，这里需要注意，将一个数翻转不用按照进制去转换，对于非16进制的数字，我们就正常使用对于牛客网—语言学习篇—编程初学者入门训练—函数类型：函数的题目前7题解析-CSDN博客这篇博客中所提到的反转数字的方法，进行反转即可，不过，对于16进制，我们就不能那么反转了，因为16进制中有字母表示大于10的数，所以我们得用16去除，去求商，避免字母被无情识别错，下面是具体代码：

/**
 * 功能：计算指定进制下的反转数（回文数的反转形式）
 * 参数：
 *   M - 待反转的数字（以十进制数值存储，无论输入进制）
 *   N - 进制（2-10或16）
 * 返回值：反转后的数字（十进制数值存储）
 */
long long huiwen(long long M, int N)
{
    long long out = 0;  // 存储反转结果
    while(M != 0)       // 循环提取每一位，直到原数变为0
    {
        if (N < 11)     // 处理10进制及以下（基数为10）
        {
            // 取出M的最后一位（对10取余），拼接到反转结果的末尾
            out = 10 * out + M % 10;
            M /= 10;    // 移除M的最后一位
        }
        else            // 处理16进制（基数为16）
        {
            // 取出M的最后一位（对16取余），拼接到反转结果的末尾
            out = 16 * out + M % 16;
            M /= 16;    // 移除M的最后一位
        }
    }
    return out;  // 返回反转后的数
}

接下来，我们就得设计一个在N进制的情况下，实现M与其反转数的相加的函数，而且，这里的这个函数就必须要在输入的N进制下进行相加，不难就会出现与题不符。

我在这边直接给大家提供一个方法：

一、阶段 1：变量初始化（函数开头）

这一步是 “准备工具”—— 定义 4 个变量并赋初始值，为后续加法计算打基础，每个变量都有明确的分工：

jin（进位）的作用：

在加法运算中，“进位” 是为了处理 “当前位相加结果超过进制上限” 的情况，是实现多位数正确加法的核心机制。它的作用类似手工计算加法时的 “逢几进一” 规则（比如 10 进制逢 10 进 1、16 进制逢 16 进 1），确保每一位的计算都符合当前进制的计数逻辑。

一、进位的本质：解决 “位值溢出” 问题

任何进制下，每一位的数字都有固定的范围（比如 10 进制每一位是 0-9，16 进制每一位是 0-F）。当某一位的相加结果超过这个范围时，无法用单个数字表示，就需要把 “超出范围的部分” 拆成两部分：

1. 当前位保留值：用 “结果对进制取余” 得到（比如 10 进制下 13 取余得 3，作为当前位数字）；
2. 进位值：用 “结果对进制取商” 得到（比如 10 进制下 13 取商得 1，作为向更高位的进位）。

进位值会传递到更高一位，与更高一位的数字一起参与计算 —— 这就是 “进位” 的核心作用：把当前位无法容纳的 “溢出值” 传递给高位，保证加法结果的正确性。

二、阶段 2：循环逐位计算（核心逻辑，while(M != 0)）

循环的本质是 “模拟手工加法的逐位计算”—— 从数字的 最低位（个位） 开始，依次处理十位、百位…… 直到原数 M 的所有位都处理完（M=0 时循环结束）。
循环内分两种场景：10 进制及以下（N<11）、16 进制（N=16），仅 “取位方式” 和 “位权基数” 不同，逻辑完全一致。

场景 1：处理 10 进制及以下（以 N=10，M=123，huiw_M=321 为例）

10 进制每一位的范围是 0-9，遵循 “逢 10 进 1” 规则，循环内每一轮处理 1 位，共分 6 小步：

循环多轮示例：处理完个位后，M=12，huiw_M=32，i=1，进入下一轮处理十位：

• 步骤 1：num=12%10 + 32%10 + 0=2+2+0=4；
• 步骤 2：4%10=4，pow(10,1)=10，out=4 + 4×10=44；
• 步骤 3：4/10=0（无进位）；
• 步骤 4：M=12/10=1；
• 步骤 5：huiw_M=32/10=3；
• 步骤 6：i=2（接下来处理百位）。

再下一轮处理百位：

• 步骤 1：num=1%10 + 3%10 +0=1+3+0=4；
• 步骤 2：4%10=4，pow(10,2)=100，out=44 +4×100=444；
• 步骤 3：4/10=0；
• 步骤 4：M=1/10=0（原数处理完）；
• 步骤 5：huiw_M=3/10=0（反转数处理完）；
• 步骤 6：i=3；
• 此时 M=0，循环结束。

场景 2：处理 16 进制（以 N=16，M=0xAB（十进制 171），huiw_M=0xBA（十进制 186）为例）

16 进制每一位的范围是 0-F（对应 0-15），遵循 “逢 16 进 1” 规则，步骤与 10 进制一致，仅 “取位基数” 和 “位权基数” 从 10 换成 16：

下一轮处理十位：

• 步骤 1：num=0xA%16 + 0xB%16 +1=10+11+1=22；
• 步骤 2：22%16=6，pow(16,1)=16，out=5 +6×16=101（十进制 101 对应 16 进制 0x65）；
• 步骤 3：22/16=1（jin=1）；
• 步骤 4：M=0xA/16=0（原数处理完）；
• 步骤 5：huiw_M=0xB/16=0（反转数处理完）；
• 步骤 6：i=2；
• 循环结束。

三、阶段 3：处理最后剩余的进位（循环结束后）

循环结束时，原数和反转数的所有位已处理完，但可能还存在 “未传递的进位”（比如 10 进制 999+999，最后一步会产生进位 1，需要作为新的最高位）。这一步的作用是 “补全最后遗漏的进位”：

四、阶段 4：返回结果（return out）

将最终计算出的总和 out 返回给调用者（比如主函数）。这里的 out 是以 十进制数值形式存储的（比如 16 进制的 0x165，在out中是十进制 357），后续可根据需要转换为对应进制的表示。

设计完了上面两个函数之后，我们便可以开始着手主函数了，主函数的功能很简单，记得使用不同的占位符去接收输入值哦，然后就是计算需要几步，我们设置变量step接收要几步，至于要怎么判断，那自然简单，我们用while循环判断，当M不为回文数的话，就进去相加，然后再判断是否为回文，详细主函数如下：

int main() {
    int N;              // 存储进制（2-10或16）
    scanf("%d", &N);    // 读取进制
    
    long long M;        // 存储初始数（以十进制数值存储）
    if (N < 11)
        // 10进制及以下：直接读取十进制数
        scanf("%lld", &M);
    else
        // 16进制：以十六进制格式读取（自动转换为十进制数值）
        scanf("%X", &M);
    
    int step = 0;       // 记录迭代步数
    int flag = 1;       // 标记是否在30步内得到回文数（1为成功，0为失败）
    
    // 循环：若当前数不是回文数，则继续迭代
    while (M != huiwen(M, N))
    {
        // 若步数超过30，标记为失败并退出循环
        if (step > 30)
        {
            flag = 0;
            break;
        }
        // 迭代：当前数 = 当前数 + 其反转数（指定进制下）
        M = sum(M, huiwen(M, N), N);
        step++;  // 步数加1
    }
    
    // 根据结果输出
    if (flag == 1)
    {
        printf("STEP=%d\n", step);  // 输出成功的步数
    }
    else 
    {
        printf("Impossible!\n");    // 输出失败信息
    }
    
    return 0;
}

由此，这道题才算是完整结束，下面给出本题完整代码：

#include <stdio.h>
#include <math.h>

long long huiwen(long long M, int N)
{
    long long out = 0;
    while(M!=0)
    {
    if (N < 11)
    {
            out = 10 * out + M % 10;
            M /= 10;
    }
    else {
            out = 16 * out + M % 16;
            M /= 16;
    }
    }
    return out;
}
long long sum(long long M, long long huiw_M, int N)
{
    int num = 0, jin = 0, i = 0;
    long long out = 0;
    while(M!=0)
    {
    if (N < 11)
    {
            num = M % 10 + huiw_M % 10 + jin;
            out = out + num % N * pow(10, i);
            jin = num / N;
            M /= 10;
            huiw_M /= 10;
            i++;
    }
    else {
            num = M % 16 + huiw_M % 16 + jin;
            out = out + num % N * pow(16, i);
            jin = num / N;
            M /= 16;
            huiw_M /= 16;
            i++;
        }
    }
    if (N < 11)
        out = out + jin * pow(10, i);
    else
        out = out + jin * pow(16, i);
    return out;
}
int main() {
    int N;
    scanf("%d", &N);
    long long M;
    if (N < 11)
        scanf("%lld", &M);
    else
        scanf("%X", &M);
    int step = 0, flag = 1;
    while (M != huiwen(M, N))
    {
        if (step > 30)
        {
            flag = 0;
            break;
        }
        M = sum(M, huiwen(M, N), N);
        step++;
    }
    if (flag == 1)
    {
        printf("STEP=%d\n", step);
    }
    else {
        printf("Impossible!\n");
    }
    return 0;
}

再来上一版详细注释的：

#include <stdio.h>   // 标准输入输出库，用于输入输出操作
#include <math.h>    // 数学库，用于pow函数计算幂（位权）

/**
 * 功能：计算指定进制下的反转数（回文数的反转形式）
 * 参数：
 *   M - 待反转的数字（以十进制数值存储，无论输入进制）
 *   N - 进制（2-10或16）
 * 返回值：反转后的数字（十进制数值存储）
 */
long long huiwen(long long M, int N)
{
    long long out = 0;  // 存储反转结果
    while(M != 0)       // 循环提取每一位，直到原数变为0
    {
        if (N < 11)     // 处理10进制及以下（基数为10）
        {
            // 取出M的最后一位（对10取余），拼接到反转结果的末尾
            out = 10 * out + M % 10;
            M /= 10;    // 移除M的最后一位
        }
        else            // 处理16进制（基数为16）
        {
            // 取出M的最后一位（对16取余），拼接到反转结果的末尾
            out = 16 * out + M % 16;
            M /= 16;    // 移除M的最后一位
        }
    }
    return out;  // 返回反转后的数
}

/**
 * 功能：在指定进制下，计算原数与它的反转数之和（处理进位）
 * 参数：
 *   M - 原数（十进制数值存储）
 *   huiw_M - 原数的反转数（十进制数值存储）
 *   N - 进制（2-10或16）
 * 返回值：两数相加的结果（十进制数值存储）
 */
long long sum(long long M, long long huiw_M, int N)
{
    int num = 0;        // 存储当前位的总和（原数当前位 + 反转数当前位 + 进位）
    int jin = 0;        // 进位值（初始为0）
    int i = 0;          // 当前处理的位数（用于计算位权）
    long long out = 0;  // 存储最终的和
    
    while(M != 0)       // 循环处理每一位，直到原数处理完毕
    {
        if (N < 11)     // 10进制及以下的加法
        {
            // 计算当前位总和（原数末位 + 反转数末位 + 进位）
            num = M % 10 + huiw_M % 10 + jin;
            // 当前位结果 = 总和 % 进制，乘以位权（10的i次方）后加入结果
            out = out + num % N * (long long)pow(10, i);
            jin = num / N;  // 计算新的进位（总和 / 进制）
            M /= 10;        // 移除原数的最后一位
            huiw_M /= 10;   // 移除反转数的最后一位
            i++;            // 位数加1，准备处理更高位
        }
        else            // 16进制的加法
        {
            // 计算当前位总和（原数末位 + 反转数末位 + 进位）
            num = M % 16 + huiw_M % 16 + jin;
            // 当前位结果 = 总和 % 16，乘以位权（16的i次方）后加入结果
            out = out + num % N * (long long)pow(16, i);
            jin = num / N;  // 计算新的进位（总和 / 16）
            M /= 16;        // 移除原数的最后一位
            huiw_M /= 16;   // 移除反转数的最后一位
            i++;            // 位数加1，准备处理更高位
        }
    }
    
    // 处理最后剩余的进位（若有）
    if (N < 11)
        out = out + jin * (long long)pow(10, i);  // 10进制进位加入结果
    else
        out = out + jin * (long long)pow(16, i);  // 16进制进位加入结果
    
    return out;  // 返回总和
}

int main() {
    int N;              // 存储进制（2-10或16）
    scanf("%d", &N);    // 读取进制
    
    long long M;        // 存储初始数（以十进制数值存储）
    if (N < 11)
        // 10进制及以下：直接读取十进制数
        scanf("%lld", &M);
    else
        // 16进制：以十六进制格式读取（自动转换为十进制数值）
        scanf("%X", &M);
    
    int step = 0;       // 记录迭代步数
    int flag = 1;       // 标记是否在30步内得到回文数（1为成功，0为失败）
    
    // 循环：若当前数不是回文数，则继续迭代
    while (M != huiwen(M, N))
    {
        // 若步数超过30，标记为失败并退出循环
        if (step > 30)
        {
            flag = 0;
            break;
        }
        // 迭代：当前数 = 当前数 + 其反转数（指定进制下）
        M = sum(M, huiwen(M, N), N);
        step++;  // 步数加1
    }
    
    // 根据结果输出
    if (flag == 1)
    {
        printf("STEP=%d\n", step);  // 输出成功的步数
    }
    else 
    {
        printf("Impossible!\n");    // 输出失败信息
    }
    
    return 0;
}

由此，大功告成。

结语：

到这里，两道中等难度的编程题解析就彻底收尾了。回顾整个过程，从 “牛牛的数组匹配” 中对 “子数组枚举” 的逻辑拆解，到 “回文数” 中对 “多进制反转、进位加法” 的细节攻克，其实每道题的难点都不是 “无从下手”，而是 “如何把模糊的思路转化为清晰的代码步骤”—— 比如枚举子数组时要明确 i 和 j 的分工，处理多进制加法时要牢记 “逢 N 进一” 的本质，判断回文时要注意前导 0 的坑。

很多时候，我们觉得编程题难，不是因为逻辑多复杂，而是容易被 “未知的细节” 吓退。就像刚开始看 “回文数” 时，会担心 16 进制的字母处理、进位的传递；看 “数组匹配” 时，会纠结子数组的遍历会不会遗漏。但只要沉下心，把大问题拆成小步骤 —— 先理清楚题意，再拆解核心需求（比如求总和、枚举子数组、判断回文），最后逐个实现每个小功能，难题自然会慢慢化解。

编程能力的提升，从来不是靠 “刷一道难题顿悟”，而是靠每道题里对细节的打磨：比如这次学会了用双层循环枚举子数组，下次遇到类似的 “连续区间问题” 就能复用；这次吃透了多进制的加法逻辑，下次碰到进制转换相关的题目也能举一反三。哪怕过程中会出错 —— 比如忘记处理最后一次进位、忽略 “相同差值选最左子数组” 的规则，这些错误也是成长的一部分，因为每一次修正，都是对逻辑的一次加固。

最后想和大家说，别害怕 “中等难度” 的题目，它们是衔接基础和进阶的关键。基础题帮我们掌握语法，中等题帮我们锻炼逻辑拆解能力，而这种能力，才是未来应对更复杂问题的核心。下次再遇到难题时，不妨告诉自己：“先拆成小步骤，我能行”。坚持下去，你会发现，曾经觉得难的题，终会变成你笔下 “理所当然” 的代码。

编程之路没有捷径，但每一步都算数。继续加油，我们下次解析再见！