1 条题解
-
0
题意分析:
本题给定 个矩形房间的坐标,统计每个房间内部所有不同尺寸的正方形个数,还要加上跨越相邻两个房间的正方形个数。房间内单个矩形中,边长为 的正方形数量等于对宽和高取交叉配对的总和;跨房间正方形则要考虑门洞宽度和相邻方向的尺寸关系。
解题思路:
-
房间内部正方形数 对于一个宽为 、高为 的矩形,所有大小的正方形总数可用公式
$$ \sum_{k=1}^{\min(n,m)} (n-k+1)(m-k+1) = \frac{m(m+1)(3n-m+1)}{6},\quad \text{其中假设 }n\ge m. $$将上式的结果设为
-
跨房间正方形数 对每对相邻房间,判断它们是否通过水平或垂直方向相邻且有门洞(共边长度 ,门洞宽度 )。设门洞宽度(可重叠的区间长度)为 ,另一方向由两房间跨越的总高度或宽度为 ,那么横跨两个房间的正方形数为
$$ \text{numSquares}(\ell, h) - \text{numSquares}(\ell, h_1) - \text{numSquares}(\ell, h_2), $$其中 、 分别是两个房间在该方向上的各自高度(或宽度),并用减法去除只在单个房间内已经统计的正方形。
本题代码
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; struct Rect { LL x1, y1, x2, y2; }; Rect rects[1005]; // 计算 n×m 矩形内所有正方形的总数(假设 n>=m) LL numSquares(LL n, LL m) { if (n < m) swap(n, m); return (3*n - m + 1) * m * (m + 1) / 6; } // 快速检查两个房间是否相邻 bool isAdjacent(int r1, int r2) { // 水平相邻 (左右相邻) if ((rects[r1].x2 == rects[r2].x1 || rects[r2].x2 == rects[r1].x1) && max(rects[r1].y1, rects[r2].y1) < min(rects[r1].y2, rects[r2].y2)) { return true; } // 垂直相邻 (上下相邻) if ((rects[r1].y2 == rects[r2].y1 || rects[r2].y2 == rects[r1].y1) && max(rects[r1].x1, rects[r2].x1) < min(rects[r1].x2, rects[r2].x2)) { return true; } return false; } // 判断区间 [a,b] 与 [c,d] 的重叠长度减去门两侧各 1 的开口宽度,返回是否可形成跨房间正方形 bool intersection(LL a, LL b, LL c, LL d, LL &len) { len = 0; if (c >= a && c <= b) len = min(b, d) - c; else if (a >= c && a <= d) len = min(b, d) - a; len -= 2; // 去除门洞两端的墙厚 return (len > 1); } // 计算两房间跨越正方形个数 LL crossSquares(int r1, int r2) { // 快速检查:如果两个房间不相邻,则返回0 if (!isAdjacent(r1, r2)) { return 0; } LL len; // 检查水平相邻 if (intersection(rects[r1].x1, rects[r1].x2, rects[r2].x1, rects[r2].x2, len)) { // 房间 1 在下,房间 2 在上 if (rects[r1].y2 == rects[r2].y1) { return numSquares(len, rects[r2].y2 - rects[r1].y1) - numSquares(len, rects[r2].y2 - rects[r2].y1) - numSquares(len, rects[r1].y2 - rects[r1].y1); } // 房间 2 在下,房间 1 在上 else if (rects[r2].y2 == rects[r1].y1) { return numSquares(len, rects[r1].y2 - rects[r2].y1) - numSquares(len, rects[r2].y2 - rects[r2].y1) - numSquares(len, rects[r1].y2 - rects[r1].y1); } } // 检查垂直相邻 else if (intersection(rects[r1].y1, rects[r1].y2, rects[r2].y1, rects[r2].y2, len)) { if (rects[r1].x2 == rects[r2].x1) { return numSquares(len, rects[r2].x2 - rects[r1].x1) - numSquares(len, rects[r2].x2 - rects[r2].x1) - numSquares(len, rects[r1].x2 - rects[r1].x1); } else if (rects[r2].x2 == rects[r1].x1) { return numSquares(len, rects[r1].x2 - rects[r2].x1) - numSquares(len, rects[r2].x2 - rects[r2].x1) - numSquares(len, rects[r1].x2 - rects[r1].x1); } } return 0; } int main() { int n, caseNum = 0; while (scanf("%d", &n) && n) { LL sum = 0; for (int i = 0; i < n; i++) { scanf("%lld %lld %lld %lld", &rects[i].x1, &rects[i].y1, &rects[i].x2, &rects[i].y2); if (rects[i].x1 > rects[i].x2) swap(rects[i].x1, rects[i].x2); if (rects[i].y1 > rects[i].y2) swap(rects[i].y1, rects[i].y2); sum += numSquares(rects[i].x2 - rects[i].x1, rects[i].y2 - rects[i].y1); } if (n > 1) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { sum += crossSquares(i, j); } } } printf("Case %d: %lld\n", ++caseNum, sum); } return 0; }
-
- 1
信息
- ID
- 1736
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者