3724. 求和公式

shwei
#include <iostream>
using namespace std;

typedef long long LL;
LL n, q, x1, y1, x2, y2, sum;

int main() {
    cin >> n >> q;
    for (int i = 1; i <= q ; i++) {
        sum = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        x1++, y1++, x2++, y2++;

        // 统计对角线
        if (x1 <= y1) {
            if (x1 != y1) {
                if (x2 - y1 >= 0) sum += min(x2, y2) - y1 + 1;
            }
            if (x1 == y1) {
                sum += min(x2, y2) - y1 + 1;
            }
        } else {
            if (min(x2, y2) - x1 >= 0) sum += min(x2, y2) - max(x1, y1) + 1;
        }

        // 统计反对角线
        LL tmp = y1;
        y1 = n + 1 - y2;
        y2 = n + 1 - tmp;

        if (x1 <= y1) {
            if (x1 != y1) {
                if (x2 - y1 >= 0) sum += min(x2, y2) - y1 + 1;
            }
            if (x1 == y1) {
                sum += min(x2, y2) - y1 + 1;
            }
        } else {
            if (min(x2, y2) - x1 >= 0) sum += min(x2, y2) - max(x1, y1) + 1;
        }

        // 处理中心点是否被重复计算
        LL mid = n / 2 + 1;
        if (n & 1 == 1 && (mid >= x1 && mid <= x2 && mid >= n + 1 - y2 && mid <= n + 1 - y1)) sum--;

        cout << sum << endl;
    }

    return 0;
}
YXBLOVEWY

厉害厉害,学到了~ 比我写的简单多了

zhanyue

有木有老哥给个方法,test12一直过不了。

YXBLOVEWY

我也是,就是过不了
https://bbs.csdn.net/topics/392963885 老哥,看看这个会不会有思路

10175101103-STARK

分别判定两条对角线和子矩形的交点坐标就能求出,不要用循环。

10175101159

室友问的题
注意判断正方形中心点在不在询问矩形中(重复算了两次)时
使用(n / 2 - a) * (n / 2 - c) <= 0 && (n / 2 - b) * (n / 2 - d) <= 0会爆long long

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q;
ll a,b,c,d;
ll ans;
int main()
{
    cin>>n>>q;
    while(q--){
        cin>>a>>b>>c>>d;
        ans=max(0LL,min(c,d) - max(a,b) + 1) + max(0LL,min(c,n - 1 - b) - max(a,n - 1 - d) + 1);
        if(n % 2 && n / 2 >= a && n / 2 <= c && n / 2 >= b && n / 2 <= d)--ans;
        cout<<ans<<endl;
    }
    return 0;
}
YXBLOVEWY

这道题直接用暴力 写两重循环会超时

你当前正在回复 博客/题目
存在问题!