基础算法2

基础算法2

高精度

大数用vector存储。小下标存储低位数字，便于处理进位，当需要进位时，只需vector数组末尾加上一位，vector有各种方法，便于进行其他处理：size pop等…因此在输入输出时，都需要考虑下标和数字位数的逆序关系。

加

两个大正整数相加

思路：这些四则运算都是用代码模拟人类的四则运算过程。加法：从低位到高位依次相加，并且考虑是否有进位，有进位则再加1，不然就加0，因此Ci=Ai+Bi+t。t不必每一位都设置一个，只需要一个变量表示即可。t初始为0，t/10为进位。

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
#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);

    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()
{
    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];
    cout << endl;

    return 0;
}

减

两个大正整数相减

思路：考虑最终的结果为正还是负，因此要先比较A，B的大小，始终用大的数减去小的数，然后根据实际情况考虑是否要加上负号。减法：从低位到高位依次相减，并且考虑是否有借位，当Ai-Bi<0时，则有借位，此时的结果应该为：Ai-Bi+10，同时标记借位为1，因此最终每位的计算公式是 ：Ci=Ai-Bi-t。t只需用一个变量表示即可。

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
50
51
#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();

    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];

    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    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');

    vector<int> C;

    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    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
#include <iostream>
#include <vector>

using namespace std;


vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}


int main()
{
    string a;
    int b;

    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);

    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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    vector<int> A;

    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    int r;
    auto C = div(A, B, r);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl << r << endl;

    return 0;
}

前缀和

长度为N的数组，前缀和数组：S1=a1，S2=a1+a2，Si=a1+a2+…+ai. Si=Si-1+ai；S0=0

作用：便于计算某一段区间的数的和 如下标[A,B]区间的数的和，则结果为：Sb-Sa-1

二维前缀和Si,j=(i,j)和(0,0)所围矩形区域的所有元素的和：Si,j = Si-1,j + Si,j-1  - Si-1,j-1 + ai,j

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stdio.h>
using namespace std;

const int N=100010;
int a[N],b[N];	//原数组 和 其对应的前缀和数组 
int n,m;	//n个数的序列 m个询问 

int main(){
	scanf("%d%d",&n,&m);	
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];	//构造前缀和数组
 
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",b[r]-b[l-1]);
	}
	
	return 0;
}

输入一个 n 行 m列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

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
#include <iostream>
#include <stdio.h>
using namespace std;

const int N=1010;
int a[N][N],b[N][N];	//原矩阵 和 其对应的前缀和矩阵 
int n,m,q;				//n行m列矩阵的 q次询问 

int main(){
	scanf("%d%d%d",&n,&m,&q);	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]); 
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]; //构造二维前缀和矩阵 
 
	while(q--){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%d\n",b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1]);
	}
	
	return 0;
}

差分

给定数组a 构造数组b 使得a数组为b数组的前缀和数组 即求前缀和数组的逆运算：由前缀和数组 求出 对应的 原数组。b数组称为a数组的差分数组
作用：假定要对a数组中的某段元素（n个）进行统一操作，若直接在a数组中操作需要O(n)的时间复杂度，如果有a的差分数组，则只需要进行两次操作即可，即时间复杂度为O(1). 比如现在要对某数组A中[L,R]区间的元素统一加上c，若是遍历并加上c，则需要O(n)的时间复杂度，若是由这个数组的差分数组B进行操作，则只需要在B数组中的B[L]+c，此时B数组对应的前缀和数组的L后的每一项，都将加上c，但是此时只要求[L,R]区间的数加c，后续的数都没有加c，只需要再令B[R
+1]-c即可。

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
#include <iostream>
#include <stdio.h>
using namespace std;

const int N = 100010;
int n,m;
int a[N],b[N];

void getDiff(int l,int r,int e){
	b[l]+=e;
	b[r+1]-=e;
}

int main(){
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);	//原数组初始化 
	
	for(int i=1;i<=n;i++) getDiff(i,i,a[i]);	//构造差分数组 
	
	//由构造出的差分数组进行操作 
	while(m--){
		int l,r,c;
		scanf("%d%d%d",&l,&r,&c);
		getDiff(l,r,c);
	} 
	
	//由处理后的差分数组 求出其前缀和数组 并输出
	for(int i=1;i<=n;i++) b[i]+=b[i-1];
	for(int i=1;i<=n;i++) printf("%d ",b[i]);
	
	return 0;
}

构造：bi=ai-ai-1 构造差分数组并非重点，主要在于如何 更新 差分数组并再由更新后的差分数组 得出其原数组（前缀和数组）的新结果。

二维差分：为二维数组中的某个矩阵区域进行操作，若由该二维数组直接操作，则需要O(n*m)的时间复杂度,用对应的差分矩阵则只需要4次操作即O(1)的时间复杂度。

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 <iostream>
#include <stdio.h>
using namespace std;

const int N=1010;
int n,m,q; //n行 m列 q个操作 
int a[N][N],b[N][N];

//***
void getDiff(int x1,int y1,int x2,int y2,int c){
	b[x1][y1]+=c;
	b[x2+1][y2+1]+=c;
	b[x1][y2+1]-=c;
	b[x2+1][y1]-=c;
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	//初始化二维矩阵 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
			
	//构造二维矩阵对应的差分矩阵 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			getDiff(i,j,i,j,a[i][j]);
		
	//对差分矩阵进行操作
	while(q--){
		int x1,y1,x2,y2,c;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
		getDiff(x1,y1,x2,y2,c);
	}
	
	//由操作后的差分矩阵 反推 操作后的 原矩阵	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1];	//***
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",b[i][j]);
		printf("\n");
	}
	
	return  0;			
}
算法 > acwing算法基础
#算法基础 #高精度 #前缀和 #差分
基础算法2
http://springbeara.top/2024/01/17/算法/acwing_basic/基础算法2/
作者
zyq
发布于
2024年1月17日
许可协议