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

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

Money4
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    ll n, q;
    cin >> n >> q;
    while (q--) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ll m1, s1, mainLine, subLine;
        //主对角线
        m1 = x1 - y1;
        if (m1 < 0) {
            mainLine = min(x2 - x1 + 1 + m1, y2 - y1 + 1);
        }
        else if (m1 > 0) mainLine = min(y2 - y1 + 1 - m1, x2 - x1 + 1);
        else mainLine = min(x2 - x1 + 1, y2 - y1 + 1);
        if (mainLine < 0) mainLine = 0;
        //副对角线
        s1 = n - 1 - x1 - y2;
        if (s1 < 0) {
            subLine = min(y2 - y1 + 1 + s1, x2 - x1 + 1);
        }
        else if (s1 > 0) subLine = min(x2 - x1 + 1 - s1, y2 - y1 + 1);
        else subLine = min(x2 - x1 + 1, y2 - y1 + 1);
        if (subLine < 0) subLine = 0;
        ll ans = subLine + mainLine;
        //中心是否重复计算
        if ((n - 1) % 2 == 0 && x1 <= (n - 1) / 2 && x2 >= (n - 1) / 2 && y1 <= (n - 1) / 2 && y2 >= (n - 1) / 2) {
            if (ans == 0) ans = 0;
            else ans--;
            printf("%lld\n", ans);
        }
        else printf("%lld\n", ans);
    }
    return 0;
}
Twisted9

一维坐标上线段ac与bd重合长度问题

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