「Codeforces 1080C」Masha and two friends

发表于 | | 阅读次数:
字数统计: 503 字

Description

题目链接：Codeforces 1080C

在一个 $n\times m$ 的国际象棋棋盘内，其中 $(1,1)$ 的格子为白色，首先将一个子矩形全都染成白色，再将一个子矩形全都染成黑色（两次染色有先后顺序）。求最后有多少个白色格子和黑色格子。

本题 $T$ 组数据。

数据范围：$1\le T\le 10^3$，$1\le n,m\le 10^9$

Solution

因为只有两次染色，所以我们只需要分类讨论就行了！

首先我们记 $B(x_1,y_1,x_2,y_2)$ 和 $W(x_1,y_1,x_2,y_2)$ 分别为矩形 $(x_1,y_1),(x_2,y_2)$ 内的黑色和白色格子数量。经过推算我们可以得到，白色格子的增量为：$B(x_1,y_1,x_2,y_2)-B((x_1,y_1,x_2,y_2)\cap(x_3,y_3,x_4,y_4))-W(x3,y3,x4,y4)$。其中第二项括号内的 $\cap$ 表示两个矩形的交集（如果没有交集，则第二项的值为 $0$）。

对于如何求 $B$ 和 $W$，直接分类讨论或者拆成 $4$ 个矩形容斥均可！

时间复杂度：$O(T)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include <cstdio>
#include <algorithm>

long long getblack(int x1,int y1,int x2,int y2) {
    bool opt=(x1+y1)&1;
    int n=x2-x1+1,m=y2-y1+1;
    if(opt) return 1LL*n*(m/2)+((m&1)?(n/2)+(n&1):0);
    else return 1LL*n*(m/2)+((m&1)?(n/2):0);
}
long long getwhite(int x1,int y1,int x2,int y2) {
    return 1LL*(x2-x1+1)*(y2-y1+1)-getblack(x1,y1,x2,y2);
}
int main() {
    int T;
    for(scanf("%d",&T);T--;) {
        int n,m,x1,y1,x2,y2,x3,y3,x4,y4;
        scanf("%d%d",&n,&m),n^=m^=n^=m;
        long long s1=getwhite(1,1,n,m);
        scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
        int u=std::max(x1,x3),d=std::min(x2,x4);
        int l=std::max(y1,y3),r=std::min(y2,y4);
        if(u<=d&&l<=r) {
            s1+=getblack(x1,y1,x2,y2)-getblack(u,l,d,r)-getwhite(x3,y3,x4,y4);
        } else {
            s1+=getblack(x1,y1,x2,y2)-getwhite(x3,y3,x4,y4);
        }
        printf("%I64d %I64d\n",s1,1LL*n*m-s1);
    }
    return 0;
}
0%