2 条题解
-
0
/* 思路 思路一: 1.二维数组+循环操作+双变量 2.循环操作: x1 ,y1 ==》 x2 , y2 [1,2] ==>[2,4] y1--y2 x1--x2 思路二: 1.两个数组 原数组 差分数组 2.循环操作---输入数据 3.循环操作---得到差分数组 4.循环操作---处理差分数组a-c --- (b+1)-c 5.循环操作---处理后的原数组(前缀和数组) 6.循环操作---输出处理后的原数组 */ /* #include <bits/stdc++.h> using namespace std; int main() { int n,m,q; cin >> n >> m >> q; //二维数组定义接收数据 vector<vector<int>> arr(n , vector<int>(m)); for ( int i = 0; i < n; i++ ) { for ( int j = 0; j < m; j++ ) { cin >> arr[i][j]; } } //循环操作 for ( int i = 0; i < q; i++ ) { int x1,y1,x2,y2,c; cin >> x1 >> y1 >> x2 >> y2 >> c; for ( int j = x1-1; j <= x2-1; j++ ) { for ( int k = y1-1; k <= y2-1; k++ ){ arr[j][k] = arr[j][k] + c; } } } //输出 for ( int i = 0; i < n; i++ ) { for ( int j = 0; j < m; j++ ) { cout << arr[i][j] << " "; } cout << endl; } return 0; } */ #include <bits/stdc++.h> using namespace std; int main() { int m, n, q; cin >> m >> n >> q; // 定义原数组和差分数组,大小为 (m+2)×(n+2),多留一圈边界 vector<vector<int>> arr(m + 2, vector<int>(n + 2, 0)); vector<vector<int>> diff(m + 2, vector<int>(n + 2, 0)); // 接收原数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> arr[i][j]; } } // 初始化差分数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { diff[i][j] = arr[i][j]; if (i > 1) diff[i][j] -= arr[i - 1][j]; if (j > 1) diff[i][j] -= arr[i][j - 1]; if (i > 1 && j > 1) diff[i][j] += arr[i - 1][j - 1]; } } // 处理差分数组 for (int i = 1; i <= q; i++) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; diff[x1][y1] += c; diff[x1][y2 + 1] -= c; diff[x2 + 1][y1] -= c; diff[x2 + 1][y2 + 1] += c; } // 恢复原数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 累加差分数组 diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]; // 更新原数组 arr[i][j] = diff[i][j]; } } // 输出结果数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cout << arr[i][j] << " "; } cout << endl; } return 0; }
-
0
#include <bits/stdc++.h> using namespace std; const int N = 1010; int mp[N][N]; int b[N][N]; int res[N][N]; int n,m,q; void compute (int x1,int y1,int x2,int y2,int c) { b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main(){ scanf("%d %d %d",&n,&m,&q); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d",&mp[i][j]); compute(i,j,i,j,mp[i][j]); } } while (q--) { int x1,y1,x2,y2,c; scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&c); compute(x1,y1,x2,y2,c); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + b[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { printf("%d ",res[i][j]); } printf("\n"); } return 0; }
- 1
信息
- ID
- 90
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 227
- 已通过
- 89
- 上传者