P8648 [蓝桥杯 2017 省 A] 油漆面积【查分+枚举】

P8648 [蓝桥杯 2017 省 A] 油漆面积题目描述X 星球的一批考古机器人正在一片废墟上考古。该区域的地面坚硬如石、平整如镜。管理人员为方便建立了标准的直角坐标系。每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。经过各种测量每个机器人都会报告一个或多个矩形区域作为优先考古的区域。矩形的表示格式为( x 1 , y 1 , x 2 , y 2 ) (x_1,y_1,x_2,y_2)(x1​,y1​,x2​,y2​)代表矩形的两个对角点坐标。为了醒目总部要求对所有机器人选中的矩形区域涂黄色油漆。小明并不需要当油漆工只是他需要计算一下一共要耗费多少油漆。其实这也不难只要算出所有矩形覆盖的区域一共有多大面积就可以了。注意各个矩形间可能重叠。本题的输入为若干矩形要求输出其覆盖的总面积。输入格式第一行一个整数n nn表示有多少个矩形( 1 ≤ n 10000 ) (1 \le n10000)(1≤n10000)。接下来的n nn行每行有4 44个整数x 1 x_1x1​y 1 y_1y1​x 2 x_2x2​y 2 y_2y2​空格分开表示矩形的两个对角顶点坐标。( 0 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10000 ) (0 \le x_1,y_1,x_2,y_2 \le 10000)(0≤x1​,y1​,x2​,y2​≤10000)。输出格式一行一个整数表示矩形覆盖的总面积。输入输出样例 #1输入 #13 1 5 10 10 3 1 20 20 2 7 15 17输出 #1340输入输出样例 #2输入 #23 5 2 10 6 2 7 12 10 8 1 15 15输出 #2128说明/提示蓝桥杯 2022 省赛 A 组 J 题。问题链接P8648 [蓝桥杯 2017 省 A] 油漆面积问题分析第一种解法是枚举法根据输入的矩形标记一下然后数一下标记的数量就可以了。这种解法在蓝桥杯官网是可以通过的蓝桥杯的数据都比较宽松但是在洛谷有一个样例会TLE。第二种解法是使用二维差分或二维前缀和来解决。参考链接略题记略AC的C语言程序二维差分如下/* P8648 [蓝桥杯 2017 省 A] 油漆面积 */#includeiostream#includecstringusingnamespacestd;constintN10000;intpre[N1][N1];intmain(){intn,x1,y1,x2,y2;memset(pre,0,sizeofpre);cinn;for(inti1;in;i){cinx1y1x2y2;pre[x1][y1];pre[x1][y2]--;pre[x2][y1]--;pre[x2][y2];}intcnt0;for(inti0;iN;i){for(intj0;jN;j){if(i1j1)pre[i][j]-pre[i-1][j-1];if(i1)pre[i][j]pre[i-1][j];if(j1)pre[i][j]pre[i][j-1];if(pre[i][j])cnt;}}coutcnt;return0;}TLE的C语言程序如下/* LQ0139 油漆面积 */#includeiostream#includecstringusingnamespacestd;constintN100001;boolvis[N][N];intmain(){memset(vis,false,sizeofvis);intn,x1,y1,x2,y2,cnt0;cinn;for(intk1;kn;k){cinx1y1x2y2;if(x1x2)swap(x1,x2);if(y1y2)swap(y1,y2);for(intix1;ix2;i)for(intjy1;jy2;j)if(!vis[i][j])cnt,vis[i][j]true;}coutcntendl;return0;}