2 条题解

  • 0
    @ 2025-3-19 16:07:18
    /*
    思路
        思路一:
            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
      @ 2024-4-9 18:53:02
      #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
      上传者