《算法竞赛从入门到国奖》算法基础:入门篇-差分

💡Yupureki:个人主页

✨个人专栏:《C++》 《算法》

🌸Yupureki🌸的简介:

目录

前言

1. 一维差分

算法原理

实操代码

2. 海底高铁

算法原理

实操代码

3. 二位差分

算法原理

实操代码

4. 地毯

算法原理

实操代码

前言

前缀和和差分的本质是预处理，可在暴力枚举的过程中，快速得到答案，是空间换时间的做法。另外，前缀和和差分是一对互逆的运算

1. 一维差分

题目链接:

【模板】差分

算法原理

我们引入差分数组的概念:

我们有一个整型数组a，定义差分数组f[n] = a[n] - a[n-1]

因此差分数组就是数组中一个数与前一个数的差值，

现在我把原数组下标为[L,R]的范围内统一增加一个数字c

那么差分数组如何改变?由于是一个数减去前一个数，那么[L + 1,R]这个范围的值就不会改变

因为统一增加c，相当于(f[i] + c) - (f[i-1] + c) = f[i] - f[i-1]等于原来的值

但是如果是f[L]和f[R+1]就要变了，因为a[L]+c,a[R]+c

那么f[L] = a[L] + c - a[L-1]，f[R+1] = a[R+1] - a[R] - c；

因此f[L]相比原来增加了c，f[R+1]相比原来减少了c

这这就是差分数组的性质。我们发现，如果我们统一对一段区间加上或减去一个相同的数，在原数组中需要挨个遍历，但差分数组只需要更改两个值即可。因此差分适用于统一对一段区间加上或减去一个相同的数这个操作

另外，对差分数组求前缀和就可以得到原数组

实操代码

#include <iostream> #include <vector> using namespace std; int main() { int a,b;cin>>a>>b; vector<long long> v(a+1,0);//原数组 vector<long long> del(a+1,0);//差分数组 for(int i = 1;i<=a;i++) { long long num;cin>>num; v[i] = num; } for(int i = 1;i<=a;i++) del[i] = v[i] - v[i-1];//初始化差分数组 while(b--) { int i,j,k;cin>>i>>j>>k; del[i] += k; del[j+1] -= k; } long long num = 0; for(int i = 1;i<=a;i++) { num += del[i];//差分数组求前缀和得到原数组 cout<<num<<" "; } return 0; }

2. 海底高铁

题目链接:

P3406 海底高铁 - 洛谷

算法原理

先考虑如何让花费最小，要想直到最小的花费，就必须得知道一段地铁坐了多少次，记f[n]，随后算出买票的花费和买卡的花费之间的最小值

买票花费:a[i] * f[i]

买卡花费:b[i] * f[i] + c[i]

接下来考虑一段地铁坐了多少次，由于从i城市 到 j城市需要坐[i,j-1]之间的所有地铁，因此这实际上就是对一段区间统一加上一个数的操作，我们使用差分数组f[i]，表示一段地铁坐了i次

实操代码

#include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> v; vector<int> a(n); vector<int> b(n); vector<int> c(n); vector<int> del(n + 1);//差分数组 for (int i = 0; i < m; i++) { int num; cin >> num; v.push_back(num); } for (int i = 1; i < n; i++) { int A, B, C; cin >> A >> B >> C; a[i] = A; b[i] = B; c[i] = C; } for (int i = 0; i < v.size() - 1; i++) { int l = v[i]; int r = v[i + 1]; if (l > r) { int tmp = r; r = l; l = tmp; } del[l]++; del[r]--; } long long ret = 0; long long k = 0; for (int i = 1; i < n; i++) { k += del[i]; long long cost1 = a[i] * k; long long cost2 = c[i] + b[i] * k; ret += cost1 > cost2 ? cost2 : cost1;//加上一段地铁的最小花费 } cout << ret; return 0; }

3. 二位差分

题目链接:

【模板】二维差分

算法原理

同样的对一段区间统一加值，不过现在是二维矩阵，我们需要推导出二维差分数组

我们利用前缀和的思想思考，假设我们对原数组左上角(x1,y1)，右下角(x2,y2)的矩阵统一加上k

由于求差分数组的前缀和就可以得到原数组，那么在差分数组中，就相当于是(x1,y1)这个位置加k，这样(x1,y1)到(x2,y2)求前缀和就都能加上一个k

但是不仅是紫色这一部分，黄色，绿色和粉色求前缀和都能加上一个k，而原数组并没有对这些部分加k

因此我们需要对(x2+1,y1) (x1,y2+1)减去一个k来抵消

但是这样粉色部分又多减一个k，因此再在(x2 + 1,y2 + 1)加k

如何初始化二维差分数组?

我们这样思考。假设原数组全是0，读取一个数据k，就是某个方格加上k，也可以看做是(x1,y1)到(x2,y2)这个矩阵加k，不过这个矩阵很小只有一个方格，那么x2 = x1 ,y2 = y1

实操代码

#include <iostream> #include <vector> using namespace std; const int N = 1010; void insert(long long x1, long long y1, long long x2, long long y2, long long value, vector<vector<long long>>& v) { v[x1][y1] += value; v[x1][y2 + 1] -= value; v[x2 + 1][y1] -= value; v[x2 + 1][y2 + 1] += value; } int main() { int n, m, k; cin >> n >> m >> k; static vector<vector<long long>> v(N, vector<long long>(N, 0));//二维差分数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { long long value; cin >> value; insert(i, j, i, j, value, v);//初始化二维差分数组,x1 = x2,y1 = y2 } } for(int i = 0;i<k;i++) { long long x1, y1, x2, y2, value; cin >> x1 >> y1 >> x2 >> y2 >> value; insert(x1, y1, x2, y2, value, v);//某一个矩阵统一加上value } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];//差分数组求前缀和得到原数组 cout << v[i][j] << " "; } cout << endl; } return 0; }

4. 地毯

题目链接:

P3397 地毯 - 洛谷

算法原理

铺一个地毯可以同时覆盖一个矩阵的点

我们直接套用二维差分数组即可

实操代码

#include <iostream> #include <vector> using namespace std; const int N = 1010; void insert(long long x1, long long y1, long long x2, long long y2, long long value, vector<vector<long long>>& v) { v[x1][y1] += value; v[x1][y2 + 1] -= value; v[x2 + 1][y1] -= value; v[x2 + 1][y2 + 1] += value; } int main() { int n, m; cin >> n >> m; static vector<vector<long long>> v(N, vector<long long>(N, 0)); for (int i = 0; i < m; i++) { long long x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; insert(x1, y1, x2, y2, 1, v); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1]; cout << v[i][j] << " "; } cout << endl; } return 0; }