P1015 [NOIP1999 普及组] 回文数
回文 普及
2023-09-27 14:28:34 时间
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; }
相关文章
- hdu 3068 最长回文(manacher&最长回文子串)
- hdu 3068 最长回文 【Manacher求最长回文子串,模板题】
- PHP算法之回文数
- leetcode 214. 最短回文串 解题报告
- BZOJ 3676: [Apio2014]回文串
- C#,回文分割问题(Palindrome Partitioning Problem)算法与源代码
- 【PAT乙级】1079 延迟的回文数 (20 分)
- C++第12周项目4——用函数解决素数、回文数等
- C++第11周项目3(10)——回文日
- JS leetcode 回文数 题解分析,数学不好是硬伤
- [NOIP2016普及组]回文日期
- (第五列)C语言常见基础题型,确定不看一下?:求10000到100000的五位回文数。
- 119、【回溯算法】leetcode ——131. 分割回文串:分割问题(C++版本)
- hdu 3068 最长回文 (manacher)
- [LeetCode] 1147. Longest Chunked Palindrome Decomposition 段式回文
- [LeetCode] 132. Palindrome Partitioning II 拆分回文串之二
- 判断是否是回文字符串(Java实现)
- 【bzoj3676】[Apio2014]回文串 回文自动机