首页 > 其他分享 >P1015 [NOIP1999 普及组] 回文数

P1015 [NOIP1999 普及组] 回文数

时间:2023-02-11 16:14:26浏览次数:59  
标签:10 进制 NOIP1999 P1015 int && 回文

P1015 [NOIP1999 普及组] 回文数

https://www.luogu.com.cn/problem/P1015

 

思路

将字符串m转换为10进制的值

翻转m,也转换为10进制值,

后运用10进制加这两个数

转换为对应进制n的字符串,

判断是否为回文

Code -- Partial AC

https://www.luogu.com.cn/record/101917196

四个测试过了三个,

检查发现,m可能有100位, 牵扯到大数加法运算,可参考:

https://www.cnblogs.com/LoginX/p/Login_X1.html

 

int n;
string m;

int strtoint(int n, string& m){
    int sum = 0;
    int pow = 1;
    int mlen = m.size();
    
    REP(i, mlen){
        char one = m[mlen-i-1];

        int ione = 0;

        if (one >= '0' && one <= '9'){
            ione = one - '0';
        } else if (one >= 'A' && one <= 'F'){
            ione = one - 'A' + 10;
        }

        sum += ione * pow;
        pow *= n;
    }
    
    return sum;
}

string inttostr(int n, int msum){
    string mstr;
    
//    cout << "n=" << n << "msum=" << msum << endl;
    
    while(msum>0){
        int r = msum % n;

//        cout << "r=" << r << endl;

        char one = '0';

        if (r >= 10 && r<=15){
            one = 'A' + r - 10;
        } else if (r >= 0 && r <= 9){
            one = '0' + r;
        }
        
        mstr.push_back(one);
        
        msum /= n;
    }
    
    reverse(mstr.begin(), mstr.end());
    
    return mstr;
}

bool ispalindrome(string str){
    int len = str.size();
    int half = len / 2;

    REP(i, half){
        char f = str[i];
        char s = str[len-i-1];
        
        if(f != s){
            return false;
        }
    }
    
    return true;
}

string reverse_add(int n, string m){
//    cout << "m=" << m << endl;

    int mint = strtoint(n, m);

//    cout << "mint=" << mint << endl;

    string mr = m;
    reverse(mr.begin(), mr.end());

//    cout << "mr=" << mr << endl;

    int mrint = strtoint(n, mr);

//    cout << "mrint=" << mrint << endl;

    int msum = mint + mrint;

//    cout << "msum=" << msum << endl;

    string msumstr = inttostr(n, msum);

//    cout << "msumstr=" << msumstr << endl;

    return msumstr;
}

int main()
{
    cin >> n >> m;
    
    int count = 0;
    
    while(true){
        bool ret = ispalindrome(m);
        //    cout << "ret=" << ret << endl;
        
        if (ret){
            break;
        }

        m = reverse_add(n, m);
        count++;
        
        if (count > 30){
            break;
        }
    }

    if (count <= 30){
        cout << "STEP=" << count << endl;
    } else {
        cout << "Impossible!" << endl;
    }

    return 0;
}

 

标签:10,进制,NOIP1999,P1015,int,&&,回文
From: https://www.cnblogs.com/lightsong/p/17111844.html

相关文章

  • 【蓝桥杯基础题】2020年省赛填空题—回文日期
    一、题目背景本题为2020年省赛填空题C/C++A组第7题C/C++B组第7题JavaA组第7题二、题目描述1.问题描述2020年春节期间,有一个特殊的日期引起了大家的注意:2020......
  • 算法刷题-回文数、找出小于平均值的数、旋转图像(C/C++)
    回文数给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。示例1:......
  • #yyds干货盘点# LeetCode面试题:回文数
    1.简述:给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。 示例1:输......
  • 【LeeCode】131. 分割回文串
    【题目描述】给你一个字符串 ​​s​​,请你将 ​​s​​ 分割成一些子串,使每个子串都是 回文串 。返回 ​​s​​ 所有可能的分割方案。回文串 是正着读和反着读都......
  • 【NOIP1999】【codevs1083】Cantor表(找规律)
    problemsolutioncodes#include<iostream>usingnamespacestd;intmain(){intn,k=1;cin>>n;//1.第n个数在第k条斜线上(前k条斜线的数的个数为等差数列)while(......
  • 【LeeCode】131. 分割回文串 -- 异常
    【题目描述】给你一个字符串 ​​s​​,请你将 ​​s​​ 分割成一些子串,使每个子串都是 回文串 。返回 ​​s​​ 所有可能的分割方案。回文串 是正着读和反着读都......
  • 杭电1282-回文
    回文数猜想ProblemDescription一个正整数,如果从左向右读(称之为正序数)和从右向左读(称之为倒序数)是一样的,这样的数就叫回文数。任取一个正整数,如果不是回文数,将该数与他的......
  • 回文数(LeetCode)
    题目测试样例思路如果这道诶就当成一个数字来做的话,其实很简单;看题目要求,很容易知道;负数都不是回文数,0是回文数,;然后在对整数加以判断就好只需将整数逆序然后......
  • #yyds干货盘点# LeetCode面试题:最长回文子串
    1.简述:给你一个字符串s,找到s中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题......
  • C++1155:回文三位数
    1155:回文三位数【题目描述】如果一个数从左边读和从右边读都是同一个数,就称为回文数。例如6886就是一个回文数,求出所有的既是回文数又是素数的三位数。【输入】(......