回文数 洛谷

回文数 洛谷

[NOIP1999 普及组] 回文数 - 洛谷

题目大意：给出一个数n和一个100位以内的n进制数s，每步操作令s=s+s的头尾翻转，问30步操作内最少多少步能将s变成一个回文数

2<=n<=10或n=16

思路：因为最多只有30步，100位数，所以模拟的时间复杂度肯定够，直接上高精度非10进制加法运算模板

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+ 5;
const ll MOD = 998244353;
int n;
bool check(string x)
{//检查是否是回文数string y = x;reverse(y.begin(), y.end());return y == x;
}
void init()
{}
string add(string x1, string x2,int d)
{//高精度d进制加法string ret;int l = x1.length();//本题中两数位数相同int pre = 0;for (int i = l - 1; i >= 0; i--){//从后向前逐位遍历int x = x1[i] - '0' + x2[i] - '0' + pre;//当前位的和加上进位if (d == 16){if (x1[i] >= 'A' && x1[i] <= 'F'){//16进制的字母要单独处理x -= x1[i] - '0';x += x1[i] - 'A' + 10;}if (x2[i] >= 'A' && x2[i] <= 'F'){x -= x2[i] - '0';x += x2[i] - 'A' + 10;}}pre = x / d;//进位x = x % d;//当前位的数if (d == 16){if (x >= 10){ret += 'A' + x - 10;continue;}}ret += '0' + x;//先放到最后一位}if (pre){//处理最后的进位if (d == 16 && pre >= 10){ret += 'A' + pre - 10;}elseret += '0' + pre;}reverse(ret.begin(), ret.end());//最后再把整个倒过来return ret;
}
void solve()
{cin >> n;init();string s;cin >> s;int cnt = 0;while (cnt <= 30){if (check(s)){cout << "STEP=" << cnt << '\n';return;}cnt++;string s2 = s;reverse(s2.begin(), s2.end());s = add(s, s2, n);//cout << s << '\n';}cout << "Impossible!";cout << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;t=1;// cin>>t;while (t--){solve();}return 0;
}