冲刺noip2010模拟试题与解析(三)

《冲刺noip2010模拟试题与解析(三)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、冲刺NOIP2010模拟试题与解析（三）题目题目帮助Bubu万圣节后的早晨魔鬼杀手染色的立方体文件名pl p2 p3 p4扩展名. pas/. c/, cpp. pas/. c/. cpp. pas/. c/. cpp . pas/. c/. cpp输入文件in. txt in. txt in. txt in, txt输出文件out. txt out. txt out. txt out. txt时间限制3s lOs Is 2s空间限制32768K 65536K 32768K 32768K满分1OO 100 100 100附加文件N/A N/A N/A N/A1

2、．帮助BubuBubu的书架乱成一团了！帮他一下吧！他的书架上一共有n本书。我们定义混乱值是连续相同高度书本的段数。例如，如果书的高度是30，30，31，31，32，那么混乱值为3，30，32，32，31的混乱度也是3，但31，32，31，32，31的混乱度是5-，这实在是太乱了。Bubu想尽可能地减少混乱度，但他有点累了，所以他决定最多取出k本书，再随意将它们放到书架上。你能帮助他吗？Input:最多会有20组测试数据。每组测试数据开头为两个整数n，k(l≤k≤n≤100)，表示总共有n本书，最多可以进行k次搬书操作。接下来一行有n个整数，表示每本书的高度，

3、从左到右。每本书的高度是25到32间的整数。最后一组数据后有一行n=k=0。Output:对于每一组数据，输出Case标号和最终最小的混乱度。在每组数据后打印一个空行。SampleInput:52252532322551252625262500SampleOutput:Case1:2Case2:32．万圣节后的早晨要求你写一个程序，在一个地图中，找到最小步数将每个鬼移动到他们指定的位置。地图包含一些小方格。每格要么是墙（鬼不能进入），要么是走廊（鬼能进入）。每一步里，你可以同时移动任意数量的鬼。每个鬼要么待在原地不动，要么移动到相邻的格子里（相邻的格子有公共边

4、），如果移动满足下列条件，则移动是可行的。1．没有一个以上的鬼在同一个格子里。2．没有一对鬼在一步里交换了位置。例如，假设鬼的位置是如右上图所示的，其中sharp(#)表示墙，空格表示走廊，a,b,c表示鬼：####ab##c######经过一步移动后，地图可以变成如下的样子：################ab#ab#acb#ab##c###c######c##################Input:输入包括最多10组数据，每组数据包含一幅地图。输入格式如下：第一行的w，h和n表示地图的宽度和高度，n表示鬼的数目，他们满足：4≤w≤16，4≤h≤16，1

5、≤n≤3接下来h行，每行w个字符：一个#表示墙。一个小写字母表示鬼的初始位置（该位置也是走廊）。一个大写字母表示鬼的目标位置（该位置也是走廊）。一个空格表示空的走廊。在每幅地图里，前n个小写字母和前n个大写字母表示鬼的初始位置及鬼的目标位置。我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。最后一组数据后一行有三个0。Output:对每组数据输出一行一个整数，表示最小的移动步数。3．魔鬼杀手你生活在一个怪兽世界里。你需要用魔法反抗这些怪兽。每个怪兽都有一定的hitpoints，表示他们的生命值。你可以靠施魔法，降低怪兽的hitpoints。每个魔法都会有

6、一定的damage，表示会减少被攻击者damage的hitpoint。一个怪兽被击败了当前仅当它的hitpoint≤0。另一方面，魔法是要消耗魔力的。因为你的魔力是有限的，你希望用最少的魔力击败所有的怪兽。写一个程序完成这个任务。Input:输入按如下的格式给出：N是怪兽的数量(1≤N≤100)，Hpi表示第i个怪兽的hitpoint(l≤HPi≤100000)，M表示可用的魔法数量(1<=M<=lOo)，Namej是第j种魔法的名字，最长会有30个大写或小写字母，MPj是这种魔法需要消耗的魔力(0$MPj≤99)，Targetj要么是”Single”，要么是

7、”All”，表示该魔法只攻击单个怪兽或对全体怪兽同时有效。Damagej表示对于所有玫击对象，可以减少攻击对象Damagej的hitpoint(0≤Damagej≤999999)。所有数字都是整数。最少有一种魔法的Damge是非零的。Output:输出一行，包含一个整数，表示最小需要消耗的魔力。4．染色的立方体小胖最近迷上了3D物体，尤其是立方体。他手里有很多个立方体，他想让所有的立方体全都长得一样，所以他决定给某些立方体的表面重涂颜色，使得所有的立方体完全相同。但是小胖是很懒的，他想知道最少涂多少次颜色，可以让所有立方体完全相同。Input.输入包含多组数据

8、，每组数据第一行n(l≤n≤4)，表示