咖啡


私信TA

用户名:Tianxn

访问量:58274

签 名:

十年OI一场空,不开LL见祖宗。

等  级
排  名 10
经  验 15651
参赛次数 2
文章发表 184
年  龄 22
在职情况 学生
学  校 西安航空学院
专  业 软件工程

  自我简介:

解题思路:
1、逻辑铺垫:这个题目最重要的无非两个部分:①回文数判断②k进制高精度加法。

                      在读入输入数据的时候,我们可以把m当成字符串处理,从而简化了后面判断回文和高精度加法。


2、题目思路:步数最多30步,我们可以直接枚举步数,每次判断是不是回文数,如果是回文数直接输出步数并结束,如果不是回文数就需要做一个k进制的高精度加法(这里是一个整数+该整数反转之后的结果),重复上述步骤,直到步数大于30然后直接输出Impossible然后结束程序。


3、回文数判断比较简单,况且是字符串,只需枚举一边检查头尾是否相同即可;

     k进制高精度加法:首先需要把字符化的整数分别存到两个整型数组中(一个正序一个反序),然后进行相加即可,最后返回相加的结果。


两个k进制大整数相加的进位处理:

x = 0; // 进位
c = a + b + x; // 相加
x = c / k; // 产生的进位
c = c % k; // 取余之后的结果


注意事项:

1、注意16进制中不一定就是大写A~F,有一个测试数据就是小写的(我就因为这个一直90分,找不到原因~~~)。

2、注意步数是从0开始的哦~~


另外代码注释很详细了,有错有不懂欢迎留言~~谢谢!

参考代码:

#include <iostream>
using namespace std;
const int RN = 105;

int n;
string m; // 把第二整数m当作字符串处理 
char fuz[] = "0123456789ABCDEF"; // 辅助数组 

// 回文数判断 
bool judge(string s) {
	for (int i = 0, len = s.size(); i <= len / 2; ++i) // 判断到中间即可 
		if (s[i] != s[len - i - 1]) return false;
	return true;
}

// k进制高精度加法 
string add(int k, string s) {
	int a[RN], b[RN], c[RN];
	string res = "";
	int len = s.size(), lenc = 1, x = 0; // lenc-和数组的下标,x-进位
	for (int i = 0; i < len; ++i) { // 字符串转整数存入数组中 
		if (isdigit(s[i])) b[len - i] = s[i] - '0'; // 字符在0~9之间(比如10进制或者2进制) 
		else b[len - i] = toupper(s[i]) - 'A' + 10; // 字符在A~F或a~f之间(比如16进制) 
		a[i + 1] = b[len - i]; // 求和的另一个整数就是本身反转之后的整数	
	}
	while (lenc <= len) {
		c[lenc] = a[lenc] + b[lenc] + x; // 求和(不要忘记进位) 
		x = c[lenc] / k; // k进制d的进位 
		c[lenc++] %= k; // k进制进位之后的余数 
	} 
	if (x) c[lenc] = x; // 最后一次相加产生的进位 
	else lenc--; // 最后一次相加没有产生进位(lenc是预留位置)
	for (int i = lenc; i > 0; --i) res += fuz[c[i]]; // 重组字符串(注意进制不同对应的字符就不同) 
	return res; 
}

int main() {
	cin >> n >> m;
	for (int i = 0; i <= 30; ++i) {
		if (judge(m)) { // 如果是回文数输出步数 
			cout << i << endl;
			return 0; // 及时结束 
		} else m = add(n, m); // 反转相加 
	}
	cout << "Impossible" << endl; // 如果超过 30 步则输出 Impossible!
	return 0;
}


 

0.0分

2 人评分

  评论区