题目大意：
给定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 <bits/stdc++.h> #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(rx<X3 || ry<Y3 || lx>X4 || ly>Y4) { col(lx,ly,rx,ry,1); return; } // 当前矩形不会被黑色部分切割到 直接涂为白色 if(lx<X3) cut(lx,ly,X3-1LL,ry), lx=X3; if(rx>X4) cut(X4+1LL,ly,rx,ry), rx=X4; if(ly<Y3) cut(lx,ly,rx,Y3-1LL), ly=Y3; if(ry>Y4) 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,0); printf("%I64d %I64d\n",W,B); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/10013995.html
相关资源：JAVA上百实例源码以及开源项目