首页 > 代码库 > 题目1016:火星A+B(字符串拆分)

题目1016:火星A+B(字符串拆分)

问题来源

  http://ac.jobdu.com/problem.php?pid=1016

问题描述

  每次输入两个数,不同数位之间用逗号隔开,其中,第n位的进制就是第n个素数,即个位数是2进制的,十位数是3进制的,百位数是5进制的,千位数是7进制的...

问题分析

  先把样例整明白,2=1*2+0*1(二进制),38=1*(5*3*2*1)+1*(3*2*1)+1*(2*1)+0*1。

  其实知道上面的原理对解题并没有什么帮助,我们只要知道,对应数位的数字相加,超过了进制就进位就可以了。所以第一步,先把两个数各个数位上的数算出来,注意某些数位上的数有可能大于10。第二步,把对应数位上的数相加,并与其进制比较,大于等于的话就进位,最后可得到答案。

  下列的参考代码可能有点不好理解,因为我没有把AB两个数翻过来,原因是懒qwq。道理其实一样,进位每次最多只能进一位。

参考代码

//// Created by AlvinZH on 2017/5/24.// Copyright (c) AlvinZH. All rights reserved.// #include <iostream>#include <cstdio>#include <vector>#include <cmath>#include <algorithm>#include <cstring>using namespace std; const int Prime[26]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101}; int main(){    string s1,s2;    int num1[26],num2[26],ans[26];    while(cin>>s1>>s2)    {        if(s1=="0"&&s2=="0") break;        memset(num1,0, sizeof(num1));        memset(num2,0, sizeof(num2));        memset(ans,0, sizeof(ans));        int index1=1;        for(int i=0;i<s1.length();i++)        {            if(s1[i]!=,)            {                num1[index1]=num1[index1]*10+(s1[i]-0);            }            else index1++;        }        int index2=1;        for(int i=0;i<s2.length();i++)        {            if(s2[i]!=,)            {                num2[index2]=num2[index2]*10+(s2[i]-0);            }            else index2++;        }        //for(int i=1;i<=index1;i++) cout<<num1[i]<<endl;        //for(int i=1;i<=index2;i++) cout<<num2[i]<<endl;        int index=max(index1,index2);        for(int i=index;i>0;i--)        {            ans[i]=ans[i]+num1[index1]+num2[index2];            while(ans[i]>=Prime[index-i])            {                ans[i]-=Prime[index-i];                ans[i-1]++;            }            if(index1>0)                index1--;            if(index2>0)                index2--;        }        if(ans[0]!=0) cout<<ans[0]<<",";        for(int i=1;i<index;i++)            cout<<ans[i]<<",";        cout<<ans[index]<<endl;    }}/**************************************************************    Problem: 1016    User: Pacsiy    Language: C++    Result: Accepted    Time:10 ms    Memory:1520 kb****************************************************************/

 

作者: AlvinZH

出处: http://www.cnblogs.com/AlvinZH/

本人Github:https://github.com/Pacsiy/JobDu

本文版权归作者AlvinZH和博客园所有,欢迎转载和商用,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

题目1016:火星A+B(字符串拆分)