题前吐槽废话

好像没人水题解，我LVL 8了。

莫得用处、3天紫衫……

题解

这道题就是 $N$ 进制高精加法，和回文判断。这样我们一个 $while$ 循环就解决了，那我们先来实现一下。

主函数已经写好了：

#include <bits/stdc++.h>
using namespace std;
// n进制m，转换为数组a，翻转后得出b，l记录数组长度，cnt表示走了几步
int n, a[150], b[150], l, cnt = 0;
/*
这里说一句，为什么数组开150：
1. 题目说M长100
2. 30次加法最多增长30格
所以开150就对了
*/
string m;
bool judge(); // 判断回文
void add(); // 翻转和加法
int main()
{
    // 输入并处理
    scanf("%d", &n);
    cin >> m;
    l = m.length() - 1;
    for (int i = 0; i < m.length(); i++)
    {
        if (m[i] >= '0' && m[i] <= '9') a[i] = m[i] - '0';
        else a[i] = m[i] - 'A' + 10;
    }
    while (!judge() && cnt <= 30) // 注意cnt <= 30条件
    {
        add();
        cnt++;
    }
    if (cnt > 30) printf("Impossible!");
    else printf("STEP=%d\n", cnt); // 注意输出格式
    return 0;
}

我们先来看 $judge$ 判断回文，这里我们看一下数组分布图： 那么怎样判断回文呢？从外到里： 这一个一个箭头是不是想一个变量记录他的位置，而他的位置正可以通过循环一个一个导过来。

循环的终止条件在中间，我们看一下中间会怎样，这里有两种情况：总共偶数个、总共奇数个。如果总共有偶数个数： 我们发现他会一个一个直到碰到一起，如果再进行一次，就 $j > i$ 了。

如果有奇数个呢？ 我们发现，他在中间会重合，再走也 $j > i$。

那么循环三件套有了，就可以写出来了：

for (int i = 0, j = l; i <= j; i++, j--)

循环里面判断一下是不是 $a_i = a_j$ 就可以了。

我们写出 $judge$ 函数：

bool judge()
{
    for (int i = 0, j = l; i <= j; i++, j--)
    {
        if (a[i] != a[j]) return false;
    }
    return true;
}

注：从内到外也可以实现

接下来考虑一下 $add$ 函数。

我们先完成反转到 $b$ 数组，参照数组图，我们可以看出，$b_i = a_{l - i}$。

for (int i = 0; i <= l; i++)
    b[i] = a[l - i];

接下来就是高精加法：

for (int i = 0; i <= l; i++)
{
    a[i] = a[i] + b[i];

}

这里是 $n$ 进制，所以我们把平时的高精中的 $10$ 改成 $n$：

for (int i = 0; i <= l; i++)
{
    a[i] = a[i] + b[i];
    a[i + 1] += a[i] / n;
    a[i] %= n;
}

最后判断一下有没有进位：

if (a[l + 1] != 0)
    l++;

这样我们写出 $add$ 函数：

void add()
{
    for (int i = 0; i <= l; i++)
        b[i] = a[l - i];
    for (int i = 0; i <= l; i++)
    {
        a[i] = a[i] + b[i]; // 加法
        a[i + 1] += a[i] / n; // 进位
        a[i] %= n; // 去除进位
    }
    if (a[l + 1] != 0) // 判断是不是多了一位
        l++;
}

注：没有学过高精的萌新，可以查查dalao的博客、多看几遍代码，理解一下，这里就不详细讲解了（以后总要讲的）

最后！我们把代码拼接：

#include <bits/stdc++.h>
using namespace std;
// n进制m，转换为数组a，翻转后得出b，l记录数组长度，cnt表示走了几步
int n, a[150], b[150], l, cnt = 0;
/*
这里说一句，为什么数组开150：
1. 题目说M长100
2. 30次加法最多增长30格
所以开150就对了
*/
string m;
bool judge() // 判断回文
{
    for (int i = 0, j = l; i <= j; i++, j--)
    {
        if (a[i] != a[j]) return false;
    }
    return true;
}
void add() // 翻转和加法
{
    for (int i = 0; i <= l; i++)
        b[i] = a[l - i];
    for (int i = 0; i <= l; i++)
    {
        a[i] = a[i] + b[i]; // 加法
        a[i + 1] += a[i] / n; // 进位
        a[i] %= n; // 去除进位
    }
    if (a[l + 1] != 0) // 判断是不是多了一位
        l++;
}
int main()
{
    // 输入并处理
    scanf("%d", &n);
    cin >> m;
    l = m.length() - 1;
    for (int i = 0; i < m.length(); i++)
    {
        if (m[i] >= '0' && m[i] <= '9') a[i] = m[i] - '0';
        else a[i] = m[i] - 'A' + 10;
    }
    while (!judge() && cnt <= 30) // 注意cnt <= 30条件
    {
        add();
        cnt++;
    }
    if (cnt > 30) printf("Impossible!");
    else printf("STEP=%d\n", cnt); // 注意输出格式
    return 0;
}

$AC$ $Code$

#include <bits/stdc++.h>
using namespace std;
int n, a[150], b[150], l, cnt = 0;
string m;
bool judge()
{
    for (int i = 0, j = l; i <= j; i++, j--)
    {
        if (a[i] != a[j]) return false;
    }
    return true;
}
void add()
{
    for (int i = 0; i <= l; i++)
        b[i] = a[l - i];
    for (int i = 0; i <= l; i++)
    {
        a[i] = a[i] + b[i];
        a[i + 1] += a[i] / n;
        a[i] %= n;
    }
    if (a[l + 1] != 0)
        l++;
}
int main()
{
    scanf("%d", &n);
    cin >> m;
    l = m.length() - 1;
    for (int i = 0; i < m.length(); i++)
    {
        if (m[i] >= '0' && m[i] <= '9') a[i] = m[i] - '0';
        else a[i] = m[i] - 'A' + 10;
    }
    while (!judge() && cnt <= 30)
    {
        add();
        cnt++;
    }
    if (cnt > 30) printf("Impossible!");
    else printf("STEP=%d\n", cnt);
    return 0;
}