POJ 2602 - Superlong sums


问题描述

无。

解题思路

非常恶心的大数相加

首先输入就够恶心了…哪有人逐位还要间断输入两个数的…

注意

  • 如果用 char[] 保存加数和被加数,要用 getchar() 输入,
  • 如果用 int[] 保存加数和被加数,要用 scanf()输入。
  • 用cin会超时,cin 是重载函数,没有指定格式,输入时比较浪费时间
  • 100W 的空间不能局部静态申请,单可以全局静态申请,也可以局部动态申请(用 new)

最恶心得是,我把结果开头的0(如果有的话)删去,竟然WA…!

Output file should contain exactly N digits in a single linerepresenting the sum of these two integers.

这是输出要求的格式,竟然要求 被加数、加数、和 的位数一致!!

按这样理解,这题是不允许最高位出现进位的…!!

AC 源码

解题方法一:使用 char[] 存储数字

//Memory  Time 
//11972K 1594MS 

#include<iostream>
#include<string>
using namespace std;

const int size=1000000;  //大数位数上限
int n;  //大数位数

int a[size+1];
int b[size+1];

void add(char* A,char* B,char* ans)
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    int pa=0,pb=0;

    int lena=strlen(A);
    int lenb=strlen(B);

    /*倒序*/

    for(int i=lena-1;i>=0;i--)
        a[pa++]=A[i]-'0';
    for(int j=lenb-1;j>=0;j--)
        b[pb++]=B[j]-'0';

    int len=lena>lenb?lena:lenb;
    char* c=new char[len+1];  //倒序的ans

    int w=0;  //低位到高位的进位
    for(int k=0;k<len;k++)
    {
        int temp=a[k]+b[k]+w;
        c[k]=temp%10+'0';
        w=temp/10;
    }
    len--;

    for(w=0;len>=0;len--)  //w和len均作指针使用,已无意义
        ans[w++]=c[len];
    ans[w]='\0';

    delete c;
    return;
}

char A[size+1];
char B[size+1];
char ans[size+1];

int main(int i)
{
    while(cin>>n)
    {
        getchar();
        for(i=0;i<n;i++)
        {
            A[i]=getchar();
            getchar();  //空格
            B[i]=getchar();
            getchar();  //回车
        }
        A[i]=B[i]='\0';

        add(A,B,ans);
        cout<<ans<<endl;
    }
    return 0;
}

解题方法二:使用 int[] 存储数字

//Memory  Time 
//17868K 1625MS

#include<iostream>
using namespace std;

int n;  //大数位数

void add(int* a,int* b,char* ans)
{
    char* c=new char[n+1];  //倒序的ans

    int w=0;  //低位到高位的进位
    for(int k=0;k<n;k++)
    {
        int temp=a[k]+b[k]+w;
        c[k]=temp%10+'0';
        w=temp/10;
    }

    n--;
    for(w=0;n>=0;n--)  //w和n均作指针使用,已无意义
        ans[w++]=c[n];
    ans[w]='\0';

    delete c;
    return;
}

int main(int i)
{
    while(cin>>n)
    {
        int* a=new int[n+1];
        int* b=new int[n+1];
        int* ta=new int[n+1];
        int* tb=new int[n+1];
        char* ans=new char[n+1];

        for(i=0;i<n;i++)
            scanf("%d %d",&ta[i],&tb[i]);

        /*倒序*/

        int pa=0,pb=0;
        for(i=n-1;i>=0;i--)
        {
            a[pa++]=ta[i];
            b[pb++]=tb[i];
        }

        add(a,b,ans);
        cout<<ans<<endl;

        delete a;
        delete b;
        delete ta;
        delete tb;
        delete ans;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1020 - Anniversary Cake POJ 1020 - Anniversary Cake
POJ 1020 - Anniversary Cake Time: 1000MS Memory: 10000K 难度: 中级 分类: 搜索 问题描述有一块边长为BoxSize的正方形的大蛋糕,现在给出n块不同尺寸的正方形的小蛋糕的边长,
2011-09-20
下一篇 
POJ 1276 - Cash Machine POJ 1276 - Cash Machine
POJ 1276 - Cash Machine Time: 1000MS Memory: 10000K 难度: 初级 分类: 背包 问题描述有各种不同面值的货币,每种面值的货币有不同的数量,请找出利用这些货币可以凑成的最接近且小于等于给
2011-09-15
  目录