社区讨论

救救孩子吧,写了一下午了,不知道错哪了,从6开始全部re,解答必关

P1884[USACO12FEB] Overplanting S参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mjlewd91
此快照首次捕获于
2025/12/25 20:21
2 个月前
此快照最后确认于
2025/12/27 17:25
2 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define endl '\n'

// 全局变量说明
ll n;                  // 矩形数量
ll a[4005][4005];     // 二维差分矩阵
ll all = 1;            // 离散化编号计数器,从1开始分配
ll no_to_num[4005];    // 编号→原始坐标的映射
ll num_to_no[4005];    // 原始坐标→编号的映射
ll ans;                // 最终答案(覆盖面积)

// 存储矩形的坐标信息
struct add {
    int x1, y1, x2, y2; // (x1,y2)是左下角,(x2,y1)是右上角(自定义坐标轴方向)
}q[2005];

unordered_map<ll, ll>p;                // 去重:记录坐标是否已加入堆
priority_queue<int, vector<int>, greater<int>>point; // 小根堆:用于坐标排序

void solve() {
    cin >> n;
    // 第一步:收集所有矩形的坐标,去重后加入小根堆
    for (int i = 0; i < n; i++) {
        cin >> q[i].x1 >> q[i].y1 >> q[i].x2 >> q[i].y2;
        // 检查x1是否已存在,不存在则加入堆和去重map
        if (!p.count(q[i].x1)) {
            p[q[i].x1] = 1;
            point.push(q[i].x1);
        }
        // 检查y1是否已存在
        if (!p.count(q[i].y1)) {
            p[q[i].y1] = 1;
            point.push(q[i].y1);
        }
        // 检查x2是否已存在
        if (!p.count(q[i].x2)) {
            p[q[i].x2] = 1;
            point.push(q[i].x2);
        }
        // 检查y2是否已存在
        if (!p.count(q[i].y2)) {
            p[q[i].y2] = 1;
            point.push(q[i].y2);
        }
    }

    // 第二步:离散化——从堆中取出排序后的坐标,分配编号
    while (!point.empty()) {
        ll val = point.top(); // 取出当前最小的坐标
        num_to_no[val] = all; // 原始坐标→编号
        no_to_num[all] = val; // 编号→原始坐标
        point.pop();
        all++; // 编号递增
    }

    // 第三步:二维差分——对每个矩形进行区域标记(自定义坐标轴方向)
    for (int i = 0; i < n; i++) {
        // 将原始坐标转换为离散化编号
        ll x1 = num_to_no[q[i].x1];
        ll y1 = num_to_no[q[i].y1];
        ll x2 = num_to_no[q[i].x2];
        ll y2 = num_to_no[q[i].y2];
        // 二维差分核心公式(针对自定义坐标轴的矩形区域)
        a[x1][y2]++;
        a[x2][y2]--;
        a[x1][y1]--;
        a[x2][y1]++;
    }

    // 第四步:二维前缀和——还原差分矩阵,得到每个小区域的覆盖次数
    // 第一重:按行累加(j从左到右)
    for (int i = 1; i < all; i++)
        for (int j = 1; j < all; j++)
            a[i][j] += a[i][j - 1];
    // 第二重:按列累加(i从上到下)
    for (int i = 1; i < all; i++)
        for (int j = 1; j < all; j++)
            a[j][i] += a[j - 1][i];

    // 第五步:计算覆盖面积——遍历所有离散化后的小区域
    for (int i = 1; i < all - 1; i++)
        for (int j = 1; j < all - 1; j++) {
            // 仅统计被覆盖的区域(覆盖次数≠0)
            if (a[i][j] != 0) {
                // 计算x方向长度:编号i→i+1对应的原始坐标差
                ll dx = no_to_num[i + 1] - no_to_num[i];
                // 计算y方向长度:编号j→j+1对应的原始坐标差
                ll dy = no_to_num[j + 1] - no_to_num[j];
                // 累加小区域的面积
                ans += dx * dy;
            }
        }
    cout << ans;
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...