AcWing 791. 高精度加法（使用string，30行） c++

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 791. 高精度加法（使用string，30行） c++ 原题链接简单

作者：

二月 , 2019-10-30 17:21:23 , 所有人可见 , 阅读 7468

25

13

算法分析

使用string完成大数存储和加法操作。

时间复杂度 o(n)

c++代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// C = A + B;  
string add(const string& A, const string& B)
{
    string C;
    int t = 0;
    for (int i = A.size()-1, j = B.size()-1; i >= 0 || j >= 0 || t > 0; i--, j--)
    {
        if (i >= 0) t += (A[i] - '0');
        if (j >= 0) t += (B[j] - '0');
        C += ((t % 10) + '0');
        t /= 10;
    }

    reverse(C.begin(), C.end());
    return C;
}

int main()
{
    ios::sync_with_stdio(false);
    string A, B;
    cin >> A >> B;
    cout << add(A, B) << endl;
    return 0;
}

20 评论

Far_Rainbow 2022-01-26 09:36

有一处可以优化的地方就是C += ((t % 10) + '0'); 可以优化为C = (char)((t % 10) + '0') + C; ，这样就可以直接得到正确顺序，无需翻转了；另外我习惯使用auto结果翻车了，auto i = A.size()-1 会得到无符号整数，它恒大于等于0，所以这个地方只能用int

我要上大学 2022-03-03 15:04

666

Pobz 2023-01-05 16:34

#$\overline{大佬太强了}$

tle_machine 2022-02-03 17:12

C += ((t % 10) + ‘0’); 为什么我写成C=C+(t % 10) + ‘0’; 就报错了。。

Pobz 2023-01-05 16:52

#您现在弄懂了吗，为什么鸭

言 2023-04-17 11:05 回复了 Pobz 的评论

已回复楼主，可以看一下，不过都三个月了，可能你都已经知道了(/doge)

言 2023-04-17 15:40

因为string类型不能和int类型直接相加，+=的结合方式是从右到左，而且可以自动进行了类型转换。先算+=右边的，算完之后再去和+=左边相加，所以C += ((t % 10) + '0');是先算(t % 10) + '0'，算完之后+=自动把结果进行了类型转换，然后他们才继续相加，所以不会报错。如果你把第二种写法C=C+(t % 10) + '0';改成C=C+(char)(t % 10 + '0');应该就不会报错了。其实第一种写法C += ((t % 10) + '0');,可以写成C += t % 10 + '0';，因为 %的优先级比+更高，而且+=是先算右边再算左边，不过出于个人习惯加上也是可以的，毕竟可以防止出错^_^

自律 2021-05-09 22:44

ios::sync_with_stdio(false);
这一行是什么意思？有什么作用？
萌新求普及

林小胖 2021-05-27 12:19

加快输入的速率

自律 2021-05-27 15:38 回复了林小胖的评论

好的谢谢大佬

Pobz 2023-01-05 15:45

#~~百度：取消两个指针的同步，加快cin的速率，否则比scanf慢很多可能爆T，尤其是在读入大量数据时~~#

Pobz 2023-01-08 09:28

同样作用的还有cin.tie(0);解除与cout输出流的关联，这样每次cin 或 cout 之前都不会刷新彼此的缓冲区

帅帅琪 2023-08-02 19:52 回复了 Pobz 的评论

兄弟markdown语法用的挺好

bibitit 2023-10-24 23:27

提供一个没用string的写法，纯手写！

#include <cstdio>
#include <cstring>

namespace Spider {
template <typename T>
class vector {
    private:
        T *_data{};
        int _size{}, _len{};
    public:
        void push_back(T num) {
            if (_size == _len) {
                if (_len == 0) _len = 1;
                else _len <<= 1;
                T *newData = new T[_len];
                memcpy(newData, _data, _size * sizeof(T));
                delete[] _data;
                _data = newData;
            }
            _data[_size ++] = num;
        }

        void pop_back() {
            _size --;
        }
        int size() {
            return _size;
        }
        T &operator[](int x) {
            return _data[x];
        }
        T top() {
            return _data[_size - 1];
        }
};

class cin {
    public:
        cin &operator>>(vector<int> &num) {
            vector<int> a;
            char ch = getchar();
            while (ch < '0' || ch > '9')
                ch = getchar();
            while (ch >= '0' && ch <= '9') {
                a.push_back(ch - '0');
                ch = getchar();
            }
            while (a.size()) {
                num.push_back(a.top());
                a.pop_back();
            }
            return *this;
        }
} cin{};

class cout {
    public:
        cout &operator<<(vector<int> num) {
            while (num.size()) {
                putchar(num.top() + '0');
                num.pop_back();
            }
            return *this;
        }
} cout{};
}

using namespace Spider;

const int N = 1e5 + 10;

vector<int> a, b;

vector<int> add(vector<int> &a, vector<int> &b) {
    if (a.size() < b.size())
        return add(b, a);
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++) {
        t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}

int main() {
    cin >> a >> b;
    vector<int> c = add(a, b);
    cout << c;
    return 0;
}