蓝桥杯省赛无忧 编程14 肖恩的投球游戏加强版

本文主要是介绍蓝桥杯省赛无忧 编程14 肖恩的投球游戏加强版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <stdio.h>
#define MAX_N 1003
int a[MAX_N][MAX_N], d[MAX_N][MAX_N];
// 差分数组的初始化
void init_diff(int n, int m) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];}}
}
// 对差分数组进行区间更新
void update_diff(int x1, int y1, int x2, int y2, int c) {d[x1][y1] += c;d[x1][y2+1] -= c;d[x2+1][y1] -= c;d[x2+1][y2+1] += c;
}
int main() {int n, m, q;scanf("%d %d %d", &n, &m, &q);// 输入初始的球筐矩阵for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {scanf("%d", &a[i][j]);}}// 初始化差分数组init_diff(n, m);// 处理每次操作while (q--) {int x1, y1, x2, y2, c;scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);update_diff(x1, y1, x2, y2, c);}// 通过差分数组还原最终的球筐矩阵for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {// 累加从(1,1)到(i,j)的差分和来还原a[i][j]d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];printf("%d ", d[i][j]);}printf("\n");}return 0;
}

1. 定义全局二维数组 a 和 d，其中 a 用于存储原始矩阵，d 用于存储差分矩阵。

2. init_diff 函数初始化差分数组 d。对于差分数组中的每个元素 d[i][j]，它存储了原始矩阵 a 中元素 a[i][j] 相对于其左上角元素 a[i-1][j-1] 的差值的累计。这是通过计算 a[i][j]、a[i-1][j]、a[i][j-1] 和 a[i-1][j-1] 之间的差值来完成的。

3. update_diff 函数实现了差分数组的区间更新。它接收左上角坐标 (x1,y1) 和右下角坐标 (x2,y2)，以及更新值 c。该函数通过在差分数组的特定点上增加 c 以及在需要减少的点上减少 c 来更新区间。

4. 主函数 main 首先读取矩阵大小 n x m 和操作数量 q。

5. 读取初始球筐矩阵，并利用 init_diff 函数初始化差分数组。

6. 读取并执行 q 次操作更新，每次更新都调用 update_diff 函数。

7. 更新完成后，使用差分数组 d 通过累加前缀和来还原最终的球筐矩阵 a。

8. 最后，输出最终更新后的球筐矩阵。

这段代码使用了一种称为“差分”的技术，可以在 O(q + n * m) 的时间复杂度内完成所有更新和最终的输出，这对于大规模更新来说非常高效。在更新操作过程中，并不直接修改原始矩阵，而是通过差分矩阵间接记录每个区间增量的变化，然后在最后一步通过累加差分矩阵来重构原始矩阵。这种方法避免了对每个元素逐一更新带来的高时间复杂度。

这篇关于蓝桥杯省赛无忧 编程14 肖恩的投球游戏加强版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---