t + 10) % 10);
t = t < 0 ? 1 : 0;
}
// ^ 去掉前导0
while (C.size() > 1 && C.back() == 0) {
C.pop_back();
}
return C;
}
// 判断 A>=B
bool cmp(vector<int>& A, vector<int>& B) {
if (A.size() > B.size())
return true;
else if (A.size() < B.size())
return false;
else
for (int i = A.size() - 1; i >= 0; i--) {
if (A[i] != B[i]) return A[i] > B[i];
}
return true;
}
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');
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);
cout << '-';
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
}
return 0;
}
A * b
793. 高精度乘法 - AcWing题库
把 b 看成一个整体去和 A 一位一位乘；记得处理b为0时的特殊情况、还有高位进位
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> A, int b) {
if (b == 0) return vector<int>{0};
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;
}
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--) cout << C[i];
return 0;
}
A / b
794. 高精度除法 - AcWing题库
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
// A / b 商 C 余 r
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;
int b;
cin >> a >> b;
vector<int> A;
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;
}
一维前缀和
前缀和、差分是一对逆运算。前缀和下标从 1 开始，\(Si = a_1 + a_2 + ... + a_i\)，\(S_0 = 0\)
\(S[i] = S[i-1] + a_i\) ，预处理 O(n)
重要应用
算 [L,R] 区间内元素和，循环遍历需要 O(n) 复杂度。而使用前缀和 \(S_r - S_{l-1}\) 复杂度为 O(1)
下标从1开始
下标从1开始方便处理边界，求 [1,10] 等于 \(S_{10}-S_{0}\)
若下标从0开始\(S_9 - S_{-1}\)，需要判断后一项不存在的情况
795
795. 前缀和 - AcWing题库
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int s[N];
int main() {
int n, m;
cin >> n >> m;
int a;
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
s[i] = a + s[i - 1];
}
while (m--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
二维前缀和
计算各个S
\(S_{x,y} = a_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1}\)
计算子矩阵
\(S_{(x_1,y_1),(x_2,y_2)} = S_{x_2,y_2} - S_{x_2,y_1-1} - S_{x_1-1,y_2} + S_{x_1-1,y_1-1}\)
796
796. 子矩阵的和 - AcWing题库
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int S[N][N];
int main() {
int n, m, q;
cin >> n >> m >> q;
int a;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a);
S[i][j] = a + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
}
w