1 条题解

  • 0
    @ 2025-5-5 14:31:42

    题意分析:

    本题给定 nn 个矩形房间的坐标,统计每个房间内部所有不同尺寸的正方形个数,还要加上跨越相邻两个房间的正方形个数。房间内单个矩形中,边长为 kk 的正方形数量等于对宽和高取交叉配对的总和;跨房间正方形则要考虑门洞宽度和相邻方向的尺寸关系。

    解题思路:

    1. 房间内部正方形数 对于一个宽为 nn、高为 mm 的矩形,所有大小的正方形总数可用公式

      $$ \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. $$

      将上式的结果设为 numSquares(n,m)\text{numSquares}(n,m)

    2. 跨房间正方形数 对每对相邻房间,判断它们是否通过水平或垂直方向相邻且有门洞(共边长度 LL,门洞宽度 L2L-2)。设门洞宽度(可重叠的区间长度)为 \ell,另一方向由两房间跨越的总高度或宽度为 hh,那么横跨两个房间的正方形数为

      $$ \text{numSquares}(\ell, h) - \text{numSquares}(\ell, h_1) - \text{numSquares}(\ell, h_2), $$

      其中 h1h_1h2h_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
    上传者