题目

原题地址 题目背景

WSR的学校有B个男生和G个女生都来到一个巨大的操场上扫地。

题目描述

操场可以看成是N 行M 列的方格矩阵，如下图(1)是一个4 行5 列的方格矩阵。每个男生负责打扫一些连续的行，每个女生负责打扫一些连续的列。比如有两个男生，第一个男生负责第1、2 两行、第二个男生负责第4 行，如图(2)的蓝色。打扫的区域可能重复，比如，又有两个女生，第一个女生负责打扫第3、4 两列，第二个女生负责打扫第4、5 两列，如图(3)的红色。从图(3)可以容易看出，有颜色覆盖的方格数为18，即这4 名学生总共打扫了18 个方格。 老师要WSR在学校给出打扫安排的数据后快速计算出这些学生总共打扫了多少方格？

输入输出格式

输入格式： 第一行4 个正整数：N,M,B,G，N 表示方阵行数，M 表示方阵列数，B 表示男生数，G 表示女生数。

接下来B 行，每行两个整数x y。表示相应某个男生负责打扫从第x 行到第y行（共y-x+1 行），保证1≤x≤y≤N。

再接下来G 行，每行两个整数x y。表示相应某个女生负责打扫从第x 列到第y 列（共y-x+1 列），保证1≤x≤y≤M。

输出格式： 一个整数，表示所打扫的面积。（即格子的总数）

输入输出样例

输入样例#1： 复制 4 5 2 2 1 2 4 4 3 4 4 5 输出样例#1： 复制 18 说明

不会可以自己画图。

数据范围：

8 个的数据：N,M,B,G 的范围都是[1…100]

2 个的数据：N,M,B,G 的范围都是[1…5,000]

题解

Try1

哦模拟啊，那我就设个全false的数组，跟刷子一样把打扫过的格子全换成true，最后一个一个数结果不就行了么？So Easy~ 结果：1~8AC，9、10TLE。（吐槽：尼玛不是模拟题么？？？模拟题会TLE我还是头一次见啊喂(╯‵□′)╯︵┻━┻）

Try2

好吧，既然会TLE那我试试能不能直接把答案算出来吧，先数数总共扫了多少行，用第二个数-第一个数+1，然后全部加起来，列数也这么算，然后被扫过的格子应该是row * M + line * (N-row)。So Easy~ 结果：全WA。妈蛋原来会重复扫的，样例里面女生就有一列重复扫了，结果导致答案被数多了。。。好吧好吧这是我眼瞎。换个方法吧OTL。。。

Try3

把俩个方法结合一下，只用数组的第一行和第一列（其实只是为了保持使用的方法一样方便待会通用。。。。），标记这行或者这列已经被扫过了，然后数一下有多少行和列被扫过了，再用上面那个公式算出来结果。 结果：1~8WA，9、10AC。这尼玛。。。。是因为数据过小导致WA了么？？？我怎么看不懂这啥情况？

Try4

既然第一次的方法能过前8个，第三次的方法能过后两个，那我就根据输入的数据用不同的方法算呗桀桀桀桀桀桀桀桀桀（淫笑）~于是就有了这么个逻辑：

if(N >= 100 && M >= 100 && B >= 100 && G >= 100) way3(); else way1();

结果：1~7、9、10AC，8WA。（我可去你的吧.jpg）虽然这种玄学的方法确实不应该对。。。但是为啥同样的方法一次对的一次错的呢。。。。明明不是这样的啊。。。明明是我先来的啊。。。为什么。。。事情会变成这样呢。。。（打死）

Try5

（我可去你的吧.jpg）爸爸重写还不行么，不用那个蹩脚的超大号数组了，用vector定义一个正好够大的好吧，结果重新算好吧~(╯‵□′)╯︵┻━┻ 结果：一遍AC了。。。。一遍AC了。。。AC了。。。了。。。。

代码

#include <bits/stdc++.h> using namespace std; int main(int argc, const char * argv[]) { int N = -1, M = -1, B = -1, G = -1; cin >> N >> M >> B >> G; vector<bool> row(N, false); vector<bool> line(M, false); for(int count = 0; count < B; count++){ int begin = -1, end = -1; cin >> begin >> end; begin--; end--; while(begin <= end){ row[begin] = true; begin++; } } for(int count = 0; count < G; count++){ int begin = -1, end = -1; cin >> begin >> end; begin--; end--; while(begin <= end){ line[begin] = true; begin++; } } int rowNumber = 0, lineNumber = 0; for(int count = 0; count < N; count++) if(row[count]) rowNumber++; for(int count = 0; count < M; count++) if(line[count]) lineNumber++; cout << rowNumber * M + lineNumber * (N-rowNumber) << endl; return 0; }

P.S.第三次尝试的时候之所以错了，是因为我把数结果的逻辑写成了

for(int count = 0; count < N; count++) if(floor[count][0]) row++; for(int count = 0; count < M; count++) if(floor[count][0]) line++;

这能对都有鬼了好伐。。。。 不过9、10还真对了。。。我估摸着应该是因为9、10的数据里面被扫过的行和列的数量是一样的，所以这样算出来也是对的。。。。。那么问题来了： 为什么会变成这样呢……第一次做了出来，又有了开心的感觉。两件快乐事情重合在一起。而这两份快乐，又给我带来更多的快乐。得到的，本该是像梦境一般幸福的时间……但是，为什么，会变成这样（被打死）呢…… （逃