题解 | #[NOIP1999]回文数#

[NOIP1999]回文数

https://www.nowcoder.com/practice/a432eb24b3534c27bdd1377869886ebb

#include <any>
#include <iostream>
#include <string>
using namespace std;

string reverseNumber(string a);
string reverse(string a);
string addNumber(string a, string b, int N);
int ch2int(char ch);
char int2ch(int i);

string reverseNumber(string a)
{
    int flag = 1;
    string b;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        if (a[i] == '0')
        {
            if (flag != 1 || a.size() == 1)
                b = b + a[i];
        }
        else 
        {
            flag = 0;
            b = b + a[i];
        }
    }
    return b;
}

string reverse(string a)
{
    for (int i = 0, j = a.size() - 1; i < j; i++, j--)
        swap(a[i], a[j]);
    return a;
}

bool isReverseNumber(string a)
{
    if (a[a.size() - 1] == '0')
        return false;
    else
    {
        string b = reverse(a);
        if (b == a)
            return true;
        else
            return false;
    }
}

string addNumber(string a, string b, int N)
{
    string c;
    a = reverse(a);
    b = reverse(b);
    int maxlen = (a.size() < b.size())? b.size() : a.size();
    int carry = 0;
    for (int i = 0; i < maxlen; i++)
    {
        char ca = (i < a.size()) ? a[i] : '0';
        char cb = (i < b.size()) ? b[i] : '0';
        int ia = ch2int(ca);
        int ib = ch2int(cb);
        int sum1 = ia + ib + carry;
        int thisdight = sum1 % N;
        carry = sum1 / N;
        c = c + int2ch(thisdight);
        if (i == maxlen - 1 && carry == 1)
            c = c + '1';
    }
    c = reverse(c);
    return c;
}  

int ch2int(char ch)
{
    int i;
    if (ch >= '0' && ch <= '9')
        i  = ch - 48;
    else if (ch >= 'A' && ch <= 'F')
        i = ch - 55;
    return i;
}

char int2ch(int i)
{
    char ch;
    if (i >= 0 && i <= 9)
        ch = i + 48;
    else if (i >= 10 && i <= 15)
        ch = i + 55;
    return ch;
}
int main() {

    string num;
    int N = 0;
    cin >> N >> num;
    int t_max = 0;

    while (t_max < 30)
    {
        t_max++;
        string num_r = reverseNumber(num);
        string num_add = addNumber(num, num_r, N);
        if (isReverseNumber(num_add))
            break;
        else
            num = num_add;        
    }
    if (t_max < 30)
        cout << "STEP=" << t_max;
    else
        cout << "Impossible!";
    
    

}
// 64 位输出请用 printf("%lld")

有点繁杂,参考的网上的高精度加法。细心一点就好了。

C++题解 文章被收录于专栏

记录在牛客网用C++刷题的题解思路

全部评论

相关推荐

lxylxy_:其实是美团卷起来了
点赞 评论 收藏
分享
11-24 19:04
已编辑
湖南工商大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务