codeforces round#524 C. Masha and two friends /// 矩形切割
阅读原文时间:2023年07月16日阅读:2

题目大意:

给定n行m列的黑白棋盘如下

给定矩形的左下点x1 y1和右上点x2 y2将这个区域都涂成白色

再给定矩形的左下点x3 y3和右上点x4 y4将这个区域都涂成黑色

求最后棋盘内有分别多少个白格和黑格

本来不怎么想发CF赛时AC的题 但是这题比较特别就想发一下~

为什么特别呢? 因为去年寒假集训的时候 有一道求多个矩形并的面积大小的题oj21547overplanting

当时学了一个矩形切割的方法 后来再也没有遇到什么类似的题

而今天 没错就是今天 终于撞上了hhh (虽然因为不熟悉 赛时小心翼翼地码 用了不少时间

好了说正题

首先因为是黑白相间的棋盘格 那么对于一个已知长宽的矩形 (长宽可由左下和右上的位置得到)

格数偶数则黑白格各半 若为奇数则多出的一个的颜色必为左下角那一格的颜色

那么怎么知道左下角的一格(设其位置为(i,j))是什么颜色呢

因为黑白相间的特性 只要判断一下 (i+j)%2 就行 为1黑色 为0则是白色

此时我们可以得到初始的棋盘有 W 个白格 和 B 个黑格

而涂色时 由于黑色是后涂的 所以我们可以直接计算被涂为黑色的格数

因为给定了涂色的左下和右上位置 我们可以用上面的方法求出这个矩形的黑格个数b和白格个数w

此时将这个矩形涂为黑色 对 W 和 B 的影响 就是 B+=w , W-=w ; ( 即把白格涂为黑色就够了 )

(那么将一个矩形涂为白色也同理  B+=b , W-=b ; )

而白色可能会被黑色覆盖 就是说白色的部分会被黑色所切割

那么我们只要把多出的部分割出来涂为白色就可以了 我们来画个图

骗人的~ 不放图了 看代码把很好懂

#include
#define LL long long
using namespace std;

LL n,m,B,W;
LL X1,Y1,X2,Y2,X3,Y3,X4,Y4;
void col(LL lx,LL ly,LL rx,LL ry,bool flag) {
LL N=ry-ly+1LL, M=rx-lx+1LL, b, w;

if((lx+ly)%2LL) // 最左下一格为黑色  
    w=N\*M/2LL, b=w+(N\*M%2LL);  
else // 否则为白色  
    b=N\*M/2LL, w=b+(N\*M%2LL);

if(flag) W+=b, B-=b; // 涂白  
else B+=w, W-=w; // 涂黑  

}
void cut(LL lx,LL ly,LL rx,LL ry) {
if(lx>rx || ly>ry) return; // 矩形不合法
if(rxX4 || ly>Y4) {
col(lx,ly,rx,ry,); return;
} // 当前矩形不会被黑色部分切割到 直接涂为白色
if(lxX4) cut(X4+1LL,ly,rx,ry), rx=X4;
if(lyY4) cut(lx,Y4+1LL,rx,ry), ry=Y4;
}
int main()
{
int t; scanf("%d",&t);
while(t--) {
scanf("%I64d%I64d",&n,&m);
B=n*m/2LL, W=B+(n*m%2LL);
scanf("%I64d%I64d%I64d%I64d",&X1,&Y1,&X2,&Y2);
scanf("%I64d%I64d%I64d%I64d",&X3,&Y3,&X4,&Y4);
cut(X1,Y1,X2,Y2);
col(X3,Y3,X4,Y4,);
printf("%I64d %I64d\n",W,B);
}

return ;  

}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章