解题思路
这个问题可以概括为输入一个大的整数闭区间，及一些可能互相重叠的在该大区间内的小的整数闭区间。在大的整数闭区间内去除这些小的整数闭区间，问之后剩下的可能不连续的整数区间内有多少个整数。这个题目给出的范围是大的区间在1~10000以内，要去除的小的区间的个数是100个以内。因为规模较小，所以可以考虑用空间换时间，用一个大数组来模拟这些区间，数组中的每个数表示区间上的一个数。例如，如果输入L的长度是500，则据题意可知最初有501棵树。我们就用一个501个元素的数组来模拟这501棵树，数组的下标分别代表从1到501棵树，数组元素的值代表这棵树是否被一走。最初这些树都没有被移走，所以所有数组元素的值都用true来表示。每当输入一个小区间，就将这个区间对应的树全部移走，即将这个区间对应的数组元素下标指示的元素的值置成false。如果有多个区间对应同一个数组元素，会导致多次将某个数组元素置成false。不过这并不影响结果的正确性。当所有小区间输入完成，我们可以数一下剩下的仍旧为true的元素的个数，就可以得到最后剩下的树的数目。当然如果最开始输入的区间不是500，则我们使用的数组大小就不是500。因为题目给出的上限是10000，所以我们可以定义一个大小是10001个元素的数组，这样对所有输入都是够用的。
思考题：
如果马路长度L的值极大，比如是40亿，以至于无法开设这么大的trees数组，本题该如何解决？
CS6：填词
（来源：poj.grids.cn 2801） 问题描述：
Alex 喜欢填词游戏。填词游戏是一个非常简单的游戏。填词游戏包括一个N *M 大小的矩形方格盘和P个单词。然后需要把每个方格中填上一个字母使得每个单词都能在方格盘上被找到。每个单词都能被找到要满足下面的条件：
每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的（可以由竖直转向水平，反之亦然）。 你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。
如果你还不了解规则，我们可以用一个例子来说明，比如在图1-2中寻找单词BEG和GEE。
E B G G E E E G E 正确
E B G G E E E G E 不正确，(2,2)中的字母E属于两个单词
E B G G E E E G E 不正确，(3,1)和(2,2)中的字母E不相邻
E B G G E E E G E 不正确，(2,2)中的字母E被用了两次
8
图1-2 填词游戏方格盘
输入：
输入的第一行包括三个整数N，M 和P (2 <= M, N <= 10, 0 <= P <=100) 。接下来的N 行，每行包括M个字符来表示方格盘。接下来P行给出需要在方格盘中找到的单词。
输入保证填词游戏至少有一组答案。输入中给出的字母都是大写字母。
输出要求
输出“神秘单词”，注意“神秘单词”中的字母要按照字典序给出。 输入样例
3 3 2 EBG GEE EGE BEG GEE 输出样例
EEG
解题思路
题目中给出的条件比较隐晦。输入中给出的字母都是大写字母——表明输出也只能是大写字母。输入保证填词游戏至少有一组答案——这说明我们不必寻找单词所在的位置，只要去掉这些单词所占用的字母就可以了。“神秘单词”中的字母要按照字典序给出——说明我们只要知道“神秘单词”中的字母组成就可以了，在字母组成确定的情况下，按字典序输出的方式只有一种。分析到这里我们发现这其实是个很简单的问题。给出一个字母的集合，从中去掉一些在给出单词中出现过的字母，将剩下的字母按字典序输出！
可以定义一个有26个元素的数组，分别记录在输入的矩形中，每个字母出现的次数，当读入单词时，将数组中对应到单词中的字母的元素值减一。处理完所有的单词后，将数组中的非0 的元素对应的字母依次输出，数组元素的值是几，就输出几次该字母。
CS7：装箱问题
（来源：poj.grids.cn 1017）
问题描述：
一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6. 这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。 输入：
输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用
9
空
格隔开，分别为1*1 至6*6 这六种产品的数量。输入文件将以6 个0 组成的一行结尾。 输出要求：
除了输入的最后一行6 个0 以外，输入文件里每一行对应着输出文件的一行，每一行输 出一个整数代表对应的订单所需的最小包裹数。 输入样例：
0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 输出样例：
2 1
解题思路：
这个问题描述得比较清楚，我们在这里只解释一下输入输出样例：共有两组有效输入，第一组表示有4个3*3的产品和一个6*6的产品，此时4个3*3的产品占用一个箱子，另外一个6*6的产品占用1个箱子，所以箱子数是2；第二组表示有7个1*1的产品，5个2*2的产品和1个3*3的产品，我们可以把他们统统放在一个箱子中，所以输出是1。
分析六个型号的产品占用箱子的具体情况如下：6*6的产品每个会占用一个完整的箱子，并且没有空余空间；5*5的产品每个占用一个新的箱子，并且留下11个可以盛放1*1的产品的空余空间；4*4的产品每个占用一个新的箱子，并且留下5个可以盛放2*2的产品的空余空间；3*3的产品情况比较复杂，首先3*3 的产品不能放在原来盛有5*5或者4*4的箱子中，那么必须为3*3的产品另开新的箱子，新开的箱子数目等于3*3的产品的数目除以4向上取整；同时我们需要讨论为3*3的产品新开箱子时，剩余的空间可以盛放多少2*2和1*1的产品（这里如果有空间可以盛放2*2的产品，我们就将它计入2*2的空余空间，等到2*2的产品全部装完，如果还有2*2的空间剩余，再将它们转换成1*1的剩余空间）。我们可以分情况讨论为3*3 的产品打开的新箱子中剩余的空位，共为四种情况：第一种，3*3的产品的数目正好是4 的倍数，所以没有空余空间；第二种，3*3的产品数目是4的倍数加1，这时还剩5个2*2的空位和7个1*1的空位；第三种，3*3的产品数目是4的倍数加2，这时还剩3个2*2的空位和6个1*1的空位；第四种，3*3的产品数目是4的倍数加3，这时还剩1个2*2的空位和5个1*1的空位；处理完3*3的产品，就可以比较一下剩余的2*2的空位和2*2产品的数目，如果产品数目多，就将2*2的空位全部填满，再为2* 的产品打开新箱子，同时计算新箱子中1*1 的空位，如果剩余空位多，就将2*2的产品全部填入2*2的空位，再将剩余的2*2的空位转换成1*1的空位；最后处理1*1的产品，比较一下1*1的空位与1*1的产品数目，如果空位多，将1*1的产品全部填入空位，否则，先将1*1的空位填满，然后再为1*1的产品打开新的箱子。
CS8：求平均年龄
（来源：poj.grids.cn 2714） 问题描述：
班上有学生若干名，给出每名学生的年龄（整数），求班上所有学生的平均年龄，保留到小数点后两位。
10
输入：
第一行有一个整数n（1<= n <= 100），表示学生的人数。其后n行每行有1个整数，取值为15到25。 输出：
输出一行，该行包含一个浮点数，为要求的平均年龄，保留到小数点后两位。 样例输入：
2 18 17
样例输出：
17.50
提示：
要输出浮点数、双精度数小数点后2位数字，可以用下面这种形式： printf(\
CS9：数字求和
（来源：poj.grids.cn 2796） 问题描述：
给定一个正整数a，以及另外的5个正整数，问题是：这5个整数中，小于a的整数的和是多少？ 输入：
输入一行，只包括6个小于100的正整数，其中第一个正整数就是a。 输出：
输出一行，给出一个正整数，是5个数中小于a的数的和。 样例输入：
10 1 2 3 4 11 样例输出：
10
CS10：两倍
（来源：poj.grids.cn 2807） 问题描述：
给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。
比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。
输入：
11
相关推荐：
loading