冲刺NOIP2010模拟试题三.doc

冲刺NOIP2010模拟试题三题目题目帮助Bubu万圣节后的早餐魔鬼杀手染色的立方体文件名p1P2P3P4扩展名.pas/.c/.cpp.pas/.c/.cpp.pas/.c/.cpp.pas/.c/.cpp输入文件in.txtin.txtin.txtin.txt输出文件out.txtout.txt out.txtout.txt时间限制3s10s1s2s空间限制32768k65336k32768k32768k满分100100100100附加文件N/AN/A N/AN/A1.帮助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（1kn100），表示总共有n本书，最多可以进行k次搬书操作。接下来一行有n个整数，表示每本书的高度，从左到右。每本书的高度是25到32间的整数。最后一组数据后有一行n=k=0。Output：对于每一组数据，输出Case标号和最终最小的混乱度。在每组数据后打印一个空行。Sample Input：5 2 25 25 32 32 255 1 25 26 25 26 250 0 Sample Output：Case1:2Case2:32.万圣节后的早晨要求你写一个程序，在一个地图上中，找到最小步数将每个鬼移动到他们指定的位置。地图包含一些小方格。每格要么是墙（鬼不能进入），要么是走廊（鬼能进入）。每一步里，你可以同时移动任意数量的鬼。每格鬼要么待在原地不动，要么移动到相邻的格子里（相邻的格子有公共边），如果移动满足下列条件，则移动是可行的。1. 没有一个以上的鬼在同一个格子里。2. 没有一对鬼在一步里交换了位置。例如，假设鬼的位置是如右下图所示的，其中sharp（#）表示墙，空格表示走廊，a，b，c表示鬼：# # # #a b # c # # # # #经过一步移动后，地图可以变成如下的样子：# # # # # # # # # # # # #a b #a b # a c b # a b # c # # # c # # # # # # c # # # # # # # # # # # # # # # # #Input：输入包括最多10组数据，每组数据包含一幅地图。输入格式如下：w h nc11c12c1wc21c22c2wch1ch2chw第一行的w,h和n表示地图的宽度和高度，n表示鬼的数目，他们满足：4w16，4h16,1n3接下来h行，每行w个字符：一个# 表示墙。一个小写字母表示鬼的位置（该位置也是走廊）。一个大写字母表示鬼的目标位置（该位置也是走廊）。一个空格表示空的走廊。在每幅地图里，前n个小写字母和前n个大写字母表示鬼的初始位置及鬼的目标位置。我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。最后一组数据后一行有三个0。Output：对每组数据输出一行一个整数，表示最小的移动步数。Sample Input5 5 2 Output for the Sample Input736773.魔鬼杀手你生活在一个怪兽的世界里。你需要魔法反抗这些怪兽。每个怪兽都有一定的hit points，表示他们的生命值。你可以靠施魔法，降低怪兽的hit points。每一个怪兽都有一定的damage，表示会减少被攻击者damage的hit point。一个怪兽被击败了当前仅当它的hit point0。另一方面，魔法师消耗魔力的。因为你的魔力是有限的，你希望用最少的魔力击败所有的怪兽。写一个程序完成这个任务。Input：输入按如下格式给出：NHP1HP2HPNMName1 MP1 Target1 Damage1Name2 MP2 Target2 Damage2NameM MPM TargetM DamageMN是怪兽的数量（1N100），Hpi表示第i个怪兽的hit point（1Hpi100000），M表示可用的魔法数量（1M100），Namej是第j种魔法的名字，最长会有30个大写或小写字母，MPj是这种魔法需要消耗的魔力（0MPj99），Targetj要么是“Single”，要么是“AII”，表示该魔法只攻击单个怪兽或对全体怪兽同时有效。Damagej表示对于所有攻击对象，可以减少攻击对象Damagej的hit point（0Damagej999999）。所有数字都是整数。最少有一种魔法的Damage是非零的。Output：输出一行，包含一个整数，表示最小需要消耗的魔力。Sample Input and OutputInput#1 Output#1： 3 232 8000 15000 30000 3Flare 45 Single 8000Meteor 62 All 6000Ultimate 80 All 9999 4.染色立方体小胖最近迷上了3D物体，尤其是立方体。他手里有很多个立方体，他想让所有的立方体全部都长得一样，所以他决定给某些立方体的表面重涂颜色，使得多有的立方体完全相同。但是小胖是很懒的，他想知道最少涂多少次颜色，可以让所有的立方体完全相同。Input：输入包含多组数据，每组数据第一行n（1n4），表示立方体的数量，接下来n行，每行6个字符串，表示立方体6个面的颜色。Color1 Color2 Color3 Color4 Color5 Color653421Color3Color2Color1Color6Color5Color46Figure5：Numbering of faceFigure 6：Coloring两个立方体被视为相同，当且仅当它们可以在某种摆放方式下，每个面的颜色都对应相同。一种涂色的方案如下:magentagreengreenblueredmagentacyanyellowcyanblueyellowredFigure2：Identically colored cubescyanmagentablueyellowredgreenblueredyellowmagentagreencyanmagentapurpleredbluegreenyellowcyanredpinkRedSearletlemonyellowbluebluemagentacyangreencyanmagentayellowgreenFigure3：cubes that are not identically colored Figure4：An example of recoloringOutput：每组数据，输出一行一个整数，表示最少的涂色数。（涂一个面算一次涂色）Sample Input3scarlet green blue yellow magenta cyanblue pink green magenta cyan lemonpurple red blue yellow cyan green2red green blue yellow magenta cyancyan green blue yellow magenta red2red green gray gray magenta cyancyan green gray gray magenta red2red green blue yellow magenta cyanmagenta red blue yellow cyan green3red green blue yellow magenta cyancyan green blue yellow magenta redmagenta red blue yellow cyan green3blue green green green green bluegreen blue blue green green greengreen green green green green sea-green3red yellow red yellow red yellowred red yellow yellow red yellowred red red red red red4violet violet salmon salmon salmon salmonviolet salmon salmon salmon salmon violetviolet violet salmon salmon violet violetviolet violet violet violet salmon salmon1red green blue yellow magenta cyan4magenta pink red scarlet vermilion