1 条题解

  • 0
    @ 2024-9-14 15:46:04

    注意子矩阵中,x1,y1,x2,y2x_1,y_1,x_2,y_2 的坐标是在线上,那么实际单行或单列方格数量会少1,又因为数据取值可以取到0,可以考虑 x1++,y1++x_1++, y_1++

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1005, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
    int n = 1000, k, st[N][N], ans;
    void solve1() {
        cin >> k;
        int x1, y1, x2, y2;
        while (k--) {
            cin >> x1 >> y1 >> x2 >> y2;
            x1++, y1++;
            for (int i = x1; i <= x2; i++)
                for (int j = y1; j <= y2; j++)
                    st[i][j] = 1;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                ans += st[i][j];
                // cout << st[i][j] << " \n"[j == n];
            }
        cout << ans << endl;
    }
    int solve2() {
        cin >> k;
        int x1, y1, x2, y2;
        while (k--) {
            cin >> x1 >> y1 >> x2 >> y2;
            x1++, y1++;
            st[x1][y1]++;
            st[x1][y2 + 1]--;
            st[x2 + 1][y1]--;
            st[x2 + 1][y2 + 1]++;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                st[i][j] += st[i - 1][j] + st[i][j - 1] - st[i - 1][j - 1];
                if (st[i][j] > 0)
                    ans++;
            }
        cout << ans << endl;
        return 0;
    }
    int main() {
        solve2();
    }
    
    • 1

    信息

    ID
    327
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    120
    已通过
    64
    上传者