算法练习——高精度、前缀和

AcWing算法基础课第一章的练习

一、 高精度

大整数A、B（位数为$10 ^ 6 $）, $a<=10000$

常考：

• A + B
• A - B
• A × a
• A ÷ a

1. 高精度加法

思想是，用一个数 t 表示进位，对于a, b中的第 i 位，当该位存在，就加到 t 里面去，然后将 t % 10 的余数放到 C 里面， 再将 t /= 10

#include<iostream>
#include<vector>
using namespace std;const int N = 1e6 + 10;vector<int> add(vector<int>& a, vector<int>& b) {  //&代表引用，不用新建数组空间 vector<int> c;int t = 0;  //代表进位 for(int i = 0; i < a.size() || i < b.size(); i ++ ) {if(i < a.size()) t += a[i];if(i < b.size()) t += b[i];c.push_back(t % 10);t /= 10;}if(t) c.push_back(1);return c;
}int main() {string a, b;vector<int> A, B;cin >> a >> b;   // a = "123456"for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); //[6, 5, 4, 3, 2, 1]for(int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');vector<int> C = add(A, B);for(int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);return 0;
}

2. 高精度减法

首先用一个函数 cmp 比较 A 和 B 的大小，判断是否有 A >= B，保证函数 sub (A, B) 的结果一定是个正数。

在函数 sub(A, B) 中，用 t 表示新的位上的数。对于 A 的每一位，让 t = A[i] - t。如果 B 还没减完，再让 t = t - B[i].

然后将 t 加入 C 中。如果 t 大于 0,直接加到 C 中；如果 t 小于 0, t + 10 之后再加到 C 中。可以将这一步简化为 (t + 10) % 10。

如果 t < 0，让 t = 1。（那么在下一轮就会将该借位减掉）

最后还需要去掉 C 中的

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

3. 高精度乘法

实现的是大整数乘以小一点的整数的情况。

同样，我们用 vector 来存储大整数。用 t 来表示进位。我们遍历 A 中的每一位，将 t += A[i] * b。然后把 t % 10的结果放在 C 后面，将 t 去掉最后一位（t /= 10）

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

4. 高精度除法

用来求大整数 A 除以小整数 b 的商和余数。

商是 C， 余数是 r。

从最高位开始遍历 A 的每一位，余数 r = r * 10 + A[i]. 然后将 r / b 的结果放入商中， 再将余数 r = r % b。（模拟数学计算中的过程）

最后得到的商的顺序是反的，记得重新倒过来。

去掉前缀0。

#include<iostream>
#include<vector>
#include<algorithm>
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 -- ) printf("%d", C[i]);cout << endl << r << endl;return 0;
} 

高精度例题

[NOIP1998 普及组] 阶乘之和

题目描述

用高精度计算出 $S=1!+2!+3!+\cdots +n!$（$n\le 50$）。

其中 ! 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如，$5!=5\times 4\times 3\times 2\times 1=120$。

输入格式

一个正整数 $n$。

输出格式

一个正整数 $S$，表示计算结果。

样例 #1

样例输入 #1

3

样例输出 #1

9

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n\le 50$。

【其他说明】

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 $n\le 20$，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

NOIP1998 普及组 第二题

代码

#include<iostream>
#include<vector>
using namespace std;//实现高精度加法
vector<int> add(vector<int> &a, vector<int> &b) {vector<int> C;int t = 0;for(int i = 0; i < a.size() || i < b.size(); i ++ ) {if(i < a.size()) t += a[i];if(i < b.size()) t += b[i];C.push_back(t % 10);t /= 10;}if(t) C.push_back(1);return C;
}//实现高精度乘法
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;}return C;
}int main() {vector<int> sum, tmp;sum.push_back(0);tmp.push_back(1);int n;cin >> n;for(int i = 1; i <= n; i ++ ) {// S = S + tmp * itmp = mul(tmp, i); sum = add(sum, tmp);}for(int i = sum.size() - 1; i >= 0; i -- ) {printf("%d", sum[i]);}return 0;
}

二、 前缀和

是一个思想，把所有数的值存在 a[N] 中，然后建立一个新的数组 S[N]， 让 S[i] = S[i - 1] + a[i]。那么当求区间[i,j]中的数时，只需要求 s[j] - s[i - 1]就可以了。

题目是输入n个数，进行m次询问，询问[i, j]区间的数的和。

#include<iostream>
using namespace std;const int N = 100010;int n, m;
int a[N], s[N];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 ++ ) s[i] = s[i - 1] + a[i];while(m -- ) {int l, r;scanf("%d%d", &l, &r);printf("%d\n", s[r] - s[l -  1]);}return 0;
}

P3131 [USACO16JAN] Subsequences Summing to Sevens S

[P3131 USACO16JAN] Subsequences Summing to Sevens S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[USACO16JAN] Subsequences Summing to Sevens S

题目描述

Farmer John’s $N$ cows are standing in a row, as they have a tendency to do from time to time. Each cow is labeled with a distinct integer ID number so FJ can tell them apart. FJ would like to take a photo of a contiguous group of cows but, due to a traumatic childhood incident involving the numbers $1\dots 6$, he only wants to take a picture of a group of cows if their IDs add up to a multiple of 7.

Please help FJ determine the size of the largest group he can photograph.

给你n个数，分别是a[1],a[2],…,a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],…,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。

输入格式

The first line of input contains $N$ ($1\le N\le 50,000$). The next $N$

lines each contain the $N$ integer IDs of the cows (all are in the range

$0\dots 1,000,000$).

输出格式

Please output the number of cows in the largest consecutive group whose IDs sum

to a multiple of 7. If no such group exists, output 0.

样例 #1

样例输入 #1

7
3
5
1
6
2
14
10

样例输出 #1

5

提示

In this example, 5+1+6+2+14 = 28.

思路和代码

可以直接用前缀和来求，然后遍历区间得到两个端点 i, j。但是这样做时间复杂度会超。

我们使用两个数组 first[7], last[7]，分别表示 模7余i 的数中的最大、最小的数。注意到 i 是从小到达遍历的，所以每次遍历时都可以更新最大的数，但是最小的数只能更新一次。

同时注意到，当区间和 模7余1 时，last[i]存的就是区间的最大长度。所以让first[i] = 0。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;typedef long long LL;
const int N = 5e4 + 10, mod = 7;//first[i]表示%7余i的数中最小的数
//last[i]表示%7余i的数中最大的数
int first[7]{0, -1, -1, -1, -1, -1, -1}, last[7]; int main() {int n;cin >> n;int s = 0, a;for(int i = 1; i <= n; i ++ ) {scanf("%d", &a);s = (s + a) % mod;if(first[s] == -1) first[s] = i;last[s] = i;}int res = 0;for(int i = 0; i < 7; i ++ ) {if(first[i] != -1) {//表示存在数 % 7 = ires = max(last[i] - first[i], res);}}cout << res;return 0;}

P1387 最大正方形

用动态规划做的

P1387 最大正方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数 $n,m(1\le n,m\le 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

输出格式

一个整数，最大正方形的边长。

样例 #1

样例输入 #1

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

样例输出 #1

2

思路和代码

动态规划，状转方程：

if (a[i, j]==1) f[i, j]=min(min(f[i, j-1],f[i-1, j]),f[i-1, j-1])+1;

###说明：

f[i, j]表示以节点i,j为右下角，可构成的最大正方形的边长。

只有a[i, j]==1时，节点i,j才能作为正方形的右下角；

对于一个已经确定的f[i, j]=x，它表明包括节点i，j在内向上x个节点，向左x个节点扫过的正方形中所有a值都为1；

对于一个待确定的f[i, j]，我们已知f[i-1, j]，f[i, j-1]，f[i-1, j-1]的值，如下：

f数组:

? ? ? ?

? ? 2 1

? ? 3 ?

? ? ? ?

则说明原a数组：

1 1 1 0

1 1 1 1

1 1 1 1

? ? ? ?

由此得出状态转移方程：

if (a[i, j]==1) f[i, j]=min(min(f[i, j-1],f[i-1, j]),f[i-1, j-1])+1;

for example:

a[i, j]:

0 0 0 1

1 1 1 1

0 1 1 1

1 1 1 1

f[i, j]:

0 0 0 1

1 1 1 1

0 1 2 2

1 1 2 3

#include<iostream>
#include<algorithm>
using namespace std;const int N = 110;//a[i][j]表示图中该点的值
//f[i][j] = x, 表示以i, j为右下角的矩阵中的边长的最大值
//f[i][j] = min(min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1
int a[N][N], f[N][N];int main() {int n, m;cin >> n >> m;int res = 0;for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= m; j ++ ) {scanf("%d", &a[i][j]);if(a[i][j] == 1) f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;res = max(res, f[i][j]);}}cout << res;return 0;}

地毯

题目描述

在 $n\times n$ 的格子上有 $m$ 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 $n,m$。意义如题所述。

接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。

输出格式

输出 $n$ 行，每行 $n$ 个正整数。

第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。

样例 #1

样例输入 #1

5 3
2 2 3 3
3 3 5 5
1 2 1 4

样例输出 #1

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

提示

样例解释

覆盖第一个地毯后：

$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$0$	$0$	$0$	$0$
$0$	$0$	$0$	$0$	$0$

覆盖第一、二个地毯后：

$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$1$	$2$	$1$	$1$
$0$	$0$	$1$	$1$	$1$
$0$	$0$	$1$	$1$	$1$

覆盖所有地毯后：

$0$	$1$	$1$	$1$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$1$	$2$	$1$	$1$
$0$	$0$	$1$	$1$	$1$
$0$	$0$	$1$	$1$	$1$

---

数据范围

对于 $20\%$ 的数据，有 $n\le 50$，$m\le 100$。

对于 $100\%$ 的数据，有 $n,m\le 1000$。

思路和代码

利用了差分的思想：

考虑这个问题的一维版：一个序列，最开始全是 0 .每次区间加 1 ,最后输出每个数。

于是有一种叫做“差分”的奇技淫巧：

假设我们现在要给[2,5]这个区间加一。原来的序列是：

0 0 0 0 0 0 0 0

这时候我们在2上面打 +1 标记， 6 上面打 -1 标记。那么现在的序列是：

0 +1 0 0 0 -1 0

有什么用呢？从左往右扫描这个数组，记录当前经过的标签之和。这个和就是对应那个数的答案。

这样，对于每个区间加操作，只需要O(1) 的时间打上标记。

最后扫描输出即可。

现在把问题拓展到二维。假设我们要覆盖[(2,2),(5,5)] ，那么标记便可以这样打：

0 0 0 0 0 0
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0

最后代码如下：

请注意，每次我们需要遍历的位置为 1 ~ n + 1。并且用一个数来表示sum来表示当前位置上的地毯数目。如果我们遍历 1 ~ n，就会遗漏当地毯右边界为 n 的情况。

#include<iostream>
using namespace std;const int N = 1010;int a[N][N], s[N][N], flag[N][N];
int n, m;int main() {cin >> n >> m;int sum = 0;while(m -- ) {int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);for(int i = x1; i <= x2; i ++ ) {a[i][y1] ++;a[i][y2 + 1] --;}}for(int i = 1; i <= n + 1; i ++ ) {for(int j = 1; j <= n + 1; j ++ ) {sum += a[i][j];flag[i][j] = sum;}}for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= n; j ++ ) {printf("%d ", flag[i][j]);}cout << endl;}return 0;
}

[HNOI2003] 激光炸弹

[P2280 HNOI2003] 激光炸弹 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

一种新型的激光炸弹，可以摧毁一个边长为 $m$ 的正方形内的所有目标。现在地图上有 $n$ 个目标，用整数 $x_i$ , $y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $v_i$。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 $m$ 的边必须与 $x$ 轴，$y$ 轴平行。若目标位于爆破正方形的边上，该目标不会被摧毁。

现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。

可能存在多个目标在同一位置上的情况。

输入格式

输入的第一行为整数 $n$ 和整数 $m$；

接下来的 $n$ 行，每行有 $3$ 个整数 $x,y,v$，表示一个目标的坐标与价值。

输出格式

输出仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过 $32767$ ）。

样例 #1

样例输入 #1

2 1
0 0 1
1 1 1

样例输出 #1

1

提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1\le n\le 10^4$，$0\le x_i,y_i\le 5\times 10^3$，$1\le m\le 5\times 10^3$，$1\le v_i<100$​。

思路和代码

也是前缀和。注意内存紧张，最后循环的时候要少循环几次

#include<iostream>
#include<algorithm>
using namespace std;const int N = 5010;int s[N][N];int main() {int n, m;cin >> n >> m;for(int i = 0; i < n; i ++ ){int x, y, v;scanf("%d%d%d", &x, &y, &v);s[x + 1][y + 1] += v;}for(int i = 1; i <= N - 9; i ++ ) {for(int j = 1; j <= N - 9; j ++ ) {s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j] ;}}int res = 0;for(int i = m; i <= N - 9; i ++ ) {for(int j = m; j <= N - 9; j ++ ) {res = max(res, s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m]);}}cout << res << endl;return 0;
}

[Poetize6] IncDec Sequence

题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,\cdots ,a_n$，每次可以选择一个区间$[l,r]$，使这个区间内的数都加 $1$ 或者都减 $1$。

请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

输入格式

第一行一个正整数 $n$
接下来 $n$ 行,每行一个整数,第 $i+1 $行的整数表示 $a_i$。

输出格式

第一行输出最少操作次数
第二行输出最终能得到多少种结果

样例 #1

样例输入 #1

4
1
1
2
2

样例输出 #1

1
2

提示

对于 $100\%$ 的数据，$n\le 100000,0\le a_i\le 2^{31}$。

思路和代码

[P4552 Poetize6] IncDec Sequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题也是同样不会。。。

【下面来自题解】

（本篇题解我们的数组的下标从1开始）差分的概念是b[1]=a[1]，b[i]=a[i]-a[i-1]，

简单来说就是两个数的差。b[1]一定是等于a[1]的，因为b[1]=a[1]-a[0]，而

a[0]=0,所以b[1]=a[1]。

了解了概念，我们看一下差分和原序列之间有什么关系

把序列a的区间[l,r]+d（或者说a[l]+d,a[l+1]+d,a[l+2]+d+…+a[r]+d的

话，那么这个序列a的差分序列b的变化就为b[l]+d,b[r+1]-d。为什么呢？举个例子

原序列a：1 3 4 2 1，其差分序列b:1 2 1 -2 -1

把区间[2,4]+2，得到的序列a应该是1 5 6 4 1

再看差分序列b，根据我们上面说的公式，a[2,4]+2应该等于b[2]+2,b[5]-2;

差分序列b变为：1 4 1 -2 -3

到底是不是这样呢？我们根据差分的概念倒推回去看看

由于b[1]=a[1]，且b[1]=1，所以a[1]=1;

b[2]=4，则a[2]-a[1]=b[2]=4;由于a[1]=1，得出a[2]=5;

b[3]=1，则a[3]-a[2]=1，由于a[2]=5，得出a[3]=6;

b[4]=-2,则a[4]-a[3]=-2，由于a[3]=6，得出a[4]=4;

b[5]=-3,则a[5]-a[4]=-3，由于a[4]=4，得出a[5]=1;

由差分序列倒推回来得到的原序列是1 5 6 4 1，完全符合我们之前得到的，说明这

个公式是正确的。

直观点说，原序列1 3 4 2 1，把区间[2,4]+2，得到的序列a是1 5 6 4 1

可以发现，a[2,4]中的差是不变的，因为他们同时加了一个数，变化的是a[l-1]和

a[l]之间的差以及a[r]和a[r+1]之间的差，这样一来，就很好推出这个差分序列公式

下面是这个公式的延伸

如果a[l,r]+1，则b[l]+1，b[r+1]-1;

如果a[l,r]-1，则b[l]-1，b[r+1]+1;

如果a[l,n]+1(l <= n - 1)，则b[l]+1，其余不变，因为b[n+1]已越界无意义

如果a[l,n]-1(l <= n - 1),则b[l]-1，其余不变，因为b[n+1]已越界无意义

下面看一下这个题该怎么做

要使得序列的数全部相等，其实就是让他们之间的差全为0，也就是差分序列的除了第

一项每一项都是0，为什么除了第一项呢，因为b[1]=a[1]-a[0]，而a[1]是开头的数

我们把问题转化成了让差分序列除第一项全等于0之后，继续思考

由于题目要求最少的步骤，我们可以考虑，如果差分序列里有一个正数和一个负数

（出现的顺序无所谓），那么我们优先对这个正数和负数进行操作，为什么呢？因为

我们有以下两个公式

如果a[l,r]+1，则b[l]+1，b[r+1]-1

如果a[l,r]-1，则b[l]-1，b[r+1]+1

正数-1，负数+1，这样相当于一步里作用了两步，比让正数一个个-1和让负数一个个

+1快多了

那么我们可以进行多少种这样的操作呢？

我们可以令差分序列里正数绝对值的总和为p，负数绝对值总和为q

可以进行这样一步顶两步的操作就是min（p，q），因为这种操作正数负数是一一配

对的，当少的那个先用完了，剩下的没有可以配对的了，只能一步步减或一步步加。

所以我们总共要进行的操作就为min（p，q）+abs（p-q），也就是max（p，q）

第一问完成，看第二问

保证最少次数的前提下，最终得到的数列有多少种？

得到的数列有多少种，其实就是问的b[1]可以有多少种

我们上述所有操作是与b[1]无关的，因为我们的目标是让除了b[1]以外的项变0，所

以我们上述的操作没有考虑到b[1]，b[1]怎么变，与我们求出的最小步骤无关

那么，我们怎么知道b[1]有几种呢？很简单，其实就是看看有几种一步步减或一步步

加的操作数，因为我们一步步加的时候（假设我们现在的操作对象下标为i），

可以这样操作，b[1]-1,b[i]+1

一步步减的时候可以这样操作，b[1]+1,b[i]-1

（注意，一个差分序列里一步步操作的时候只可能一步步加或一步步减，不可能一步

步加和一步步减同时存在）

所以说，有几步一步步的操作就有几种情况+1，为什么+1呢，因为这个b[1]本身就有

一个值啊！就算你不对他进行任何操作，它自己也有一种情况。

一加一减（也就是我们所说的一步顶两步的操作）操作数为min（p，q）

那么一步步的操作数就为max（p，q）-min（p，q）=abs（p，q）

完结撒花