高精度加法

就是手工模拟一次加法的过程

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
#include <iostream>
#include <vector>
using namespace std;

vector<int> add (vector<int> &A,vector<int> &B){
vector<int> C;
if(A.size()<B.size()) return add(B,A);//确保A是最大的数,能遍历所有的数
int t=0;//开始进位为0
for(int i=0;i<A.size();i++){
t+=A[i];
if(B.size()>i) t+=B[i];//B该位有数则加上
C.push_back(t%10);
t/=10;//进位变为1或者0
}
if(t) C.push_back(t);//算完之后t=1,则加上这个最高位 A-19 B-1 add(A,B)--》00--》001《--C
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');//Ascall码中字符0-9与数字0-9,相差48刚好一个字符0-'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--) 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<vector>
using namespace std;

//是否 A>=B
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;
}


//C=A-B
vector<int> sub(vector<int> &A,vector<int> &B){
vector<int>C;
int t=0;//借位
for(int i=0;i<A.size();i++){

t=A[i]-t;
if(B.size()>i) t-=B[i];
C.push_back((t+10)%10);
if(t<0) t=1;
else t=0;
}
//去掉前导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');


//判断A,B的大小 如果A-B,B>A则变成sub(B-A),输出时在前面加"-"
if(cmp(A,B)){
auto C=sub(A,B);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
}else{
auto C=sub(B,A);
printf("-");
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
}



return 0;



}

高精度乘低精度

大整数乘以一个小整数

就是一个大整数的每一位都乘以这个小整数,对结果求余(%10)就得到的最低位就是当前位数;对结果除以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
#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++){//进位未处理或者A未遍历完
if(A.size()>i) t+=A[i]*b;
C.push_back(t%10);
t/=10;
}

//处理前导0
while(C.size()>1&&C.back()==0) C.pop_back();


return C;

}

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

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

return C;
}



int main(){
int b;
string a;
vector<int>A;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
int r=0;
auto C=div(A,b,r);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);

cout<<endl<<r<<endl;
return 0;
}

一维前缀和

把S[0]=0,更方便,所以最好从i=1开始

1
2
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1] 时间复杂度 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
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

#include<iostream>
using namespace std;
const int N=1000+10;
int n,m,q,arr[N][N],s[N][N];

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",&arr[i][j]);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j];
}
}
int x1,x2,y1,y2;
while(q--){

scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int temp=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
printf("%d\n",temp);
}

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
给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,arr[N],b[N];
void b_insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
b_insert(i,i,arr[i]);

}
while(m--){
int l,r,c;
scanf("%d %d %d",&l,&r,&c);
b_insert(l,r,c);
}

for(int i=1;i<=n;i++){
b[i+1]+=b[i];
printf("%d ",b[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
给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c



#include<iostream>
using namespace std;
const int N=1000+10;
int n,m,q,arr[N][N],s[N][N];

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",&arr[i][j]);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j];
}
}
int x1,x2,y1,y2;
while(q--){

scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int temp=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
printf("%d\n",temp);
}

return 0;
}

双指针算法

核心思想:

1
2
3
4
5
6
7
8
9
10
//将朴素算法 O(n^2) 优化成O(n)
//朴素算法:
for(int i=0;i<n;i++)
for(int j<=i;j<n;j++){
}

//双指针:
for(int i=0,j=0;i<n;i++){
while(j<r&&check(i,j)) j++;
}

模板

1
2
3
4
5
6
7
8
9
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;

// 具体问题的逻辑
}
常见问题分类:
(1) 对于一个序列,用两个指针维护一段区间
(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

位运算

1
2
3
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n
= n & (~n+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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<algorithm>
#include<vector>
#include <iostream>
using namespace std;
const int N=3e5+10;
int a[N],s[N];
vector<pair<int,int>> queryVec,addVec;
vector<int> alls;

//用二分法找到映射坐标的数组下标
int find(int x){
int l=0;
int r=alls.size()-1;
while(l<r){
int mid=l+r>>1;
if(alls[mid]>=x) r=mid;
else l=mid+1;
}

return l+1;//注意为了方便前缀和,从1开始算 a[1]----s[1]

}



int main(){
int n,m;
scanf("%d%d",&n,&m);

//加入添加数据的坐标
while(n--){
int x,c;
scanf("%d%d",&x,&c);
alls.push_back(x);
addVec.push_back({x,c});
}

//加入询问的坐标
while(m--){
int l,r;
scanf("%d%d",&l,&r);
alls.push_back(l);
alls.push_back(r);
queryVec.push_back({l,r});
}

//排序去重
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

//处理添加
for(auto temp:addVec){
int x=find(temp.first);
a[x]+=temp.second;

}

//处理前缀和
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];

//处理查询
for(auto temp:queryVec){
int l=find(temp.first);
int r=find(temp.second);
printf("%d\n",s[r]-s[l-1]);
}


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
#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
vector<pair<int,int>> seg;

void merge(vector<pair<int,int>> &seg){

vector<pair<int,int>> res;
int l=-2e9,r=-2e9;

for(auto temp:seg){
if(temp.first>r){
//确保不是开始那个无限远的区间再加入
if(l!=-2e9) res.push_back({l,r});
//开始检测新区间
l=temp.first;
r=temp.second;
}else r=max(r,temp.second);



}
if(l!=-2e9) res.push_back({l,r});//加上最后一个区间
seg=res;

}

int main(){
int n;
scanf("%d",&n);
while(n--){
int l,r;
scanf("%d%d",&l,&r);
seg.push_back({l,r});
}

sort(seg.begin(),seg.end());

merge(seg);
printf("%d",seg.size());

return 0;
}