做完AB之后被C卡到最后,,,从来没做过坐标平面上两个矩形的面积和,,,因为存在相交的可能,,,所以要单独的处理矩形面积交,,然后自己就写懵了,,,当时写了几十行的if判断,,,,到最后都没弄完,,QAQ
题意与分析 题意这道题的题意就是给你一个n * m大的方格板子,,类似国际象棋那样,,黑白相间,,然后再给你两个矩形,,第一个矩形内的所有格子涂为白色,,第二个涂为黑色,,,问你最后白格子和黑格子的数量,,棋盘的大小可能是1e9 * 1e9的,,,
思路 我的思路一开始我的思路是算出所有的白格子,黑格子的数量(wsum ,bsum),,,然后wsum加上第一个矩形里的所有黑格子数量,,之后wsum减去第二个矩形里白格子的数量,,,最后再考虑是有面积的相交,,,有的话再计算相交矩形内的,,但是中间的一些细节,,,比如说如何计算不同左下角坐标的矩形内格子数,,如何判是否有相交的矩形,,如何计算相交的矩形内的格子数量以及怎么调整等等,,,以前从来没写过没考虑过,,,只能硬头皮的去一路if下去,,,到最后自己的写懵了,,,
中途想着直接模拟算了,,,维护一个大矩阵,,1表示白色0表示黑色,,然后对相应的矩形全部置一置零,,,最后求01的数量,,,然后发现根本开不了那么大的数组,,,,QAQ
最后今天看了出题人的题解,,, 矩形(1 , 1 , x , y)内白格子的数量的计算\(设函数w(x , y)返回值为左下角(1 , 1)与(x , y)的矩形内的白格子的数量\)
矩形内白格子数量的计算:\(任意一个矩形(x_1 , y_1 , x_2 , y_2)内的白格子数量=矩形(1 , 1 , x_2 , y_2)内白格子的数量-矩形(1 , 1 , x_1 , y_2)内白格子的数量-矩形(1 , 1 , x_2 , y_1)内白格子的数量+矩形(1 , 1 , x_1 - 1 , y_1 - 1)内白格子的数量,所以:\)
\[W(x_1 , y_1 , x_2 , y_2) = w(x_1 , y_1) - w(x_1 - 1 , y_2) - w(x_2 , y_1 - 1) + w(x_1 - 1 , y_1 - 1)\]
矩形内黑格子数量的计算\[B(x_1 , y_1 , x_2 , y_2) = (x_2 - x_1 + 1) * (y_2 - y_1 + 1) - W(x_1 , y_1 , x_2 , y_2)\]
相交部分的判断和处理出题人说显然(我(/‵Д′)/~ ╧╧)如果不存在相交矩形,,那么一定满足
\[max(x_1 , x_3)>min(x_2 , x_4) \ \ or\ \ max(y_1,y_3)>min(y_2,y_4)\]
所以反命题就是如果存在相交举证即使上面那个判断取反,,同时相交矩形的坐标是
\[(max(x_1 , x_3) \ , \ max(y_1 , y_3)\ ,\ min(x_2,x_4)\ ,\ min(y2 , y_4))\]
有了这些,,我们就可以算出相交矩形内原来的白色、黑色的格子了(就是不考虑第一个第二个矩形影响时的数量),,
因为在第一个矩形里将相交矩形内的黑格子变成了白色,,现在又要变成黑色,,所以wsum(白色格子的数量)要减去黑色的数量(白色的数量已经在计算第二个矩形时减去了,,所以对于wsum是减去了相交矩形的所有格子数量),,同时黑色格子的数量bsum要加上黑色的数量,,而计算第二个矩形时相交矩形里的白色已经加上了,,,相当于加上了整个相交矩形的格子数量,,(拿笔画一下这个步骤就更清楚了)
w(x , y)的实现首先我们定义这样排列的黑白格子为类型1
而这样的是类型2
行数n为偶数时,类型1类型2的数量是对半的,即\(\frac n2\),
行数n为奇数时,类型1的数量是\(\lfloor{\frac n2}\rfloor\) (向下取整,直接除就行),,类型2的数量是\(\lceil{\frac n2}\rceil\)(向上取整,有余数时加一个)
因为行数n为偶数时类型1的数量和类型2数量相等,也就是说\(\lfloor{\frac n2}\rfloor\)=\(\lceil{\frac n2}\rceil\),,所以,,我们就不管行数是不是偶数奇数了,,,直接类型1数量=\(\lfloor{\frac n2}\rfloor\),类型2数量=\(\lceil{\frac n2}\rceil\),,,(数学真好玩.jpg,,,想想我当时为了判断行数的奇偶分情况讨论,,写吐ed,,(#`Д´)ノ)
按照这个思路,,,同样列数m也就可以这样计算了,,,
即类型1的数量=\(\lfloor{\frac m2}\rfloor\),,类型2的数量=\(\lceil{\frac m2}\rceil\)..