二分模板

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// C = A + B, A >= 0, B >= 0
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;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// C = A + B, A >= 0, B >= 0
void add(char c[], char a[], char b[], int len){
	int i = 0;
    while(i < len) {           //根据你们人类的习惯，先从个位数开始加
        c[i] = (c[i] + a[i] + b[i]) % '0';  //数组中存储的是字符串，相加的是ASCLL码中所对应的数值；%48，'1'实际上是49
		if(c[i] > 9) {     //%48之后，s中存储的就是实际意义上的1，2，3了
            c[i + 1]++;
            c[i] %= 10;
        }
        i++;
    }
    
   if(!c[i]) i--;   //去掉多余的0，如4+5=9，i++，运算后i=1，s[1]=0,不能输出
    for (  ; i >= 0; i--)  printf("%d", c[i]);   //因为从低位开始加的，需要倒过来输出
    puts("");
}



题目描述：

给定两个正整数（不含前导 0），计算它们的和。

输入格式
共两行，每行包含一个整数。

输出格式
共一行，包含所求的和。

数据范围

1≤整数长度≤100000

输入样例：

12
23

输出样例：

35

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);//为了方便计算，让A中保存较长的数字， B中保存较短的数字

    vector<int> C;//保存结果的数组
    int t = 0;//进位，开始时是0
    for (int i = 0; i < A.size(); i ++ )//依次计算每一位
    {
        t += A[i];//加上 A 的第 i 位上的数字
        if (i < B.size()) t += B[i];//加上 B 的第 i 位上的数字
        C.push_back(t % 10); //C 中放入结果
        t /= 10;//t 更新成进位
    }

    if (t) C.push_back(t);//最后如果进位上有数，放进结果数组
    return C;//返回结果
}

int main()
{
    string a, b;//以字符串形式保存输入的两个整数
    vector<int> A, B;//保存两个整数的数组
    cin >> a >> b;//接收输入
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');//倒序存储第一个数
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');//倒序存储第二个数
    auto C = add(A, B);//调用加和函数
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];//倒序输出C中的数字
    cout << endl;
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <string.h>
#define N 100010

char s[N], s1[N], s2[N];

int main() {
    scanf("%s %s", s1, s2);
    
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int len = len1 > len2 ? len1 : len2;
    
    int i = 0, j = len1 - 1;
    while(i < j) {        //把两个数组反过来，好进位
        char c = s1[i];   
        s1[i] = s1[j];
        s1[j] = c;
        i++, j--;
    }
    
    i = 0, j = len2 - 1;
    while(i < j) {
        char c = s2[i];
        s2[i] = s2[j];
        s2[j] = c;
        i++, j--;
    }
    
    i = 0;
    while(i < len) {           //根据你们人类的习惯，先从个位数开始加
        s[i] = (s[i] + s1[i] + s2[i]) % '0';   //数组中存储的是字符串，相加的是ASCLL码中所对应的数值；%48，'1'实际上是49
        if(s[i] > 9) {     //%48之后，s中存储的就是实际意义上的1，2，3了
            s[i + 1]++;
            s[i] %= 10;
        }
        i++;
    }
    
   if(!s[i]) i--;   //去掉多余的0，如4+5=9，i++，运算后i=1，s[1]=0,不能输出
    for (  ; i >= 0; i--)  printf("%d", s[i]);   //因为从低位开始加的，需要倒过来输出
    puts("");
    
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <stdio.h>
#include <string.h>
#define N 100010

char c[N], a[N], b[N];

void reverse(char c[],int len){

	int i = 0, j = len - 1;
    while(i < j) {        //把两个数组反过来，从低位开始相加 
        char k = c[i];   
        c[i] = c[j];
        c[j] = k;
        i++, j--;
    }
} 

void add(char c[], char a[], char b[], int len){
	int i = 0;
    while(i < len) {           //根据你们人类的习惯，先从个位数开始加
        c[i] = (c[i] + a[i] + b[i]) % '0';   //数组中存储的是字符串，相加的是ASCLL码中所对应的数值；%48，'1'实际上是49
		if(c[i] > 9) {     //%48之后，s中存储的就是实际意义上的1，2，3了
            c[i + 1]++;
            c[i] %= 10;
        }
        i++;
    }
    
   if(!c[i]) i--;   //去掉多余的0，如4+5=9，i++，运算后i=1，s[1]=0,不能输出
    for (  ; i >= 0; i--)  printf("%d", c[i]);   //因为从低位开始加的，需要倒过来输出
    puts("");
}

int main() {
    scanf("%s %s", &a, &b);
    
    int len1 = strlen(a);
    int len2 = strlen(b);
    int len = len1 > len2 ? len1 : len2;
    
    reverse(a,len1);
	reverse(b,len2); 
    
   	add(c,a,b,len);
    
    return 0;
}