【NOIP1999】【Luogu1015】回文数（高精度，模拟）-白红宇

【NOIP1999】【Luogu1015】回文数（高精度，模拟）

阅读量：4556 次

发布时间：2019-06-08

本文共 1611 字，大约阅读时间需要 5 分钟。

problem

给定一个n进制的数m

每次进行如下操作：反转（比如把56变成65）后两数相加，得新数。

求最少经过几步可以得到新数为回文数，超过30步输出Impossible!

solution

判断回文或者反转一个数可以用STL的reverse。

两n进制数相加模拟高精即可（竖式手算

codes

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 105;string s="0123456789ABCDEF";string add(int k, string aa){
   //k进制，返回"aa"+"反转后的aa"    //反转    string bb = aa;    reverse(bb.begin(),bb.end());    //转存高精    int a[maxn], b[maxn], c[maxn];    memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c));    a[0] = aa.size();  b[0] = a[0];  c[0] = a[0]*2;//c可能进位    for(int i = 0; i < a[0]; i++){        //16进制特判        if(isdigit(aa[i]))a[a[0]-i] = aa[i]-'0';        else a[a[0]-i] = aa[i]-'A'+10;        //因为反转,a与b一定是等长的，可以一起算        if(isdigit(bb[i]))b[b[0]-i] = bb[i]-'0';        else b[b[0]-i] = bb[i]-'A'+10;    }    //模拟加法    int x = 0;//x是进位    for(int i = 1; i <= c[0]; i++){        c[i] = a[i]+b[i]+x;        x = c[i]/k; //k进制除k        c[i] %= k;  //k进制膜k    }    c[c[0]] = x;//最后一个进位    while(c[0]>1 && c[c[0]]==0)c[0]--;//除0    //返回答案    string ans;    for(int i = c[0]; i >= 1; i--)//存的是反序        ans += s[c[i]];    return ans;}bool check(string a){
   //判断回文    string b = a;    reverse(b.begin(), b.end());//反转字符串    return a==b;}int main(){    int n;  string m;    cin>>n>>m;    for(int i = 1; i <= 30; i++){
   //无脑模拟        m = add(n,m);//反转加一下        if(check(m)){
   //是回文就输出步数            cout<<"STEP="<
         <<'\n'; return 0; } } cout<<"Impossible!"<