🏝️专栏： 【蓝桥杯备篇】
🌅主页： f狐o狸x
“OJ超时不是终点，是算法在提醒你该优化时间复杂度了！”
目录
3.25 差分数组
一、一维差分
题目链接：
题目描述：
解题思路：
解题代码：
二、海底高铁
题目链接：
题目描述：
解题思路：
解题代码：
三、二维差分
题目链接：
题目描述：
解题思路：
解题代码：
四、地毯
题目链接：
题目描述：
解题思路：
解题代码：
3.25 差分数组
我们直接用一道题来了解差分数组吧
一、一维差分
题目链接：
【模板】差分
题目描述：
解题思路：
还是可以用暴力枚举来搞定，我们把整个数组遍历一遍，再把对应位置加上x就行了，但是这样绝对是会超时长滴，不然我干嘛用这个例题？
对于类似的题，我们就可以用差分算法，和前缀和数组类似，我们需要预处理一个差分数组出来
这个数组的好处就是当你要在 l ~ r 的区间加上 x 的时候（图中用2~5）来表示，就只需要在差分数组中的 l 位置加上 x ，r + 1 位置减去 x ，再还原为原数组就行
也就是：a[ l ] += x; a[ r + 1 ] -= x;
此时还有人要问：煮波煮波，那怎么还原数组呢？其实把差分数组做一个前缀和运算即可还原 证明如下：
解题代码：
#include <iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];int n, m;int main()
{cin >> n >> m;// 利用差分的性质预处理差分数组for(int i = 1; i <= n; i++){LL x;cin >> x;a[i] += x;a[i + 1] -= x;}// m次操作while(m--){LL l, r, x; cin >> l >> r >> x;a[l] += x;a[r + 1] -= x;}// 利用前缀和还原数组for(int i = 1; i <= n; i++){a[i] = a[i - 1] + a[i];cout << a[i] << " ";}return 0;
}二、海底高铁
题目链接：
P3406 海底高铁
题目描述：
解题思路：
这里我们只需要知道这个人每段铁路一共坐了几次，再判断是直接买票划算还是买卡划算，最后累加输出即可
解题代码：
#include <iostream>using namespace std;const int N = 1e5 + 10;typedef long long LL;LL f[N];int n, m;int main()
{cin >> n >> m;int l, r; cin >> l;// 利用差分记录每段铁路经过的次数for (int i = 2; i <= m; i++){cin >> r;if (l <= r) f[l] += 1, f[r] -= 1;else f[r] += 1, f[l] -= 1;l = r;}// 还原数组for (int i = 1; i <= n; i++){f[i] = f[i - 1] + f[i];}LL ret = 0;for(int i = 1; i < n; i++){LL a, b, c; cin >> a >> b >> c;ret += min(a * f[i], c + b * f[i]);}cout << ret << endl;return 0;
}三、二维差分
题目链接：
【模板】二维差分
题目描述：
解题思路：
如图所示我们需要对以下结果数组进行操作：
f[x1][y1] + k
f[x2 + 1][y1] - k
f[x1][y2 + 1] - k
f[x2 + 1][y2 + 1] - k
这样我们累加起来以后就可以得到二维数组中区间+k的操作
解题代码：
#include <iostream>using namespace std;typedef long long LL;const int N = 1010;LL f[N][N];int n, m, q;void insert(int x1, int y1, int x2, int y2, int x)
{f[x1][y1] += x;f[x2 + 1][y1] -= x;f[x1][y2 + 1] -= x;f[x2 + 1][y2 + 1] += x;
}int main()
{cin >> n >> m >> q;// 预处理二维齐差分数组for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){LL a; cin >> a;insert(i, j, i , j ,a);} }while(q--){LL x1, y1, x2, y2, a; cin >> x1 >> y1 >> x2 >> y2 >>a;insert(x1, y1, x2, y2, a);}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];cout << f[i][j] << " ";}cout << endl;}return 0;
}四、地毯
题目链接：
P3397 地毯
题目描述：
解题思路：
这题其实就是把地毯对应的区域全加上一，最后再输出数组即可解决
解题代码：
#include <iostream>using namespace std;const int N = 1010;int f[N][N];int n, m;void insert(int x1, int y1, int x2, int y2, int a)
{f[x1][y1] += a;f[x2 + 1][y1] -= a;f[x1][y2 + 1] -= a;f[x2 + 1][y2 + 1] += a;
}int main()
{cin >> n >> m;while (m--){int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;insert(x1, y1, x2, y2, 1);}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];cout << f[i][j] << " ";}cout << endl;}return 0;
}今天就到这里吧，下一期我们将讲解二分算法~886~
蓝桥杯选手日常：
睡醒→看题→看不懂→搜题解→抄代码→被卡常→怒删重写→提交→WA
