社区讨论
救救孩子吧,写了一下午了,不知道错哪了,从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 条回复,欢迎继续交流。
正在加载回复...