冲刺NOIP2010模拟试题与解析(三).doc

冲刺NOIP2010模拟试题与解析（三）题目题目帮助Bubu万圣节后的早晨魔鬼杀手染色的立方体文件名plp2p3p4扩展名.pas/.c/,cpp.pas/.c/.cpp.pas/.c/.cpp.pas/.c/.cpp输入文件in.txtin.txtin.txtin,txt输出文件out.txtout.txtout.txtout.txt时间限制3slOsIs2s空间限制32768K65536K32768K32768K满分1OO100100100附加文件N/AN/AN/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(lkn100)，表示总共有n本书，最多可以进行k次搬书操作。接下来一行有n个整数，表示每本书的高度，从左到右。每本书的高度是25到32间的整数。最后一组数据后有一行n=k=0。Output: 对于每一组数据，输出Case标号和最终最小的混乱度。在每组数据后打印一个空行。Sample Input: 5 2 25 25 32 32 25 5 1 25 26 25 26 25 0 0 Sample Output: Case 1:2 Case 2:3 2万圣节后的早晨要求你写一个程序，在一个地图中，找到最小步数将每个鬼移动到他们指定的位置。地图包含一些小方格。每格要么是墙（鬼不能进入），要么是走廊（鬼能进入）。每一步里，你可以同时移动任意数量的鬼。每个鬼要么待在原地不动，要么移动到相邻的格子里（相邻的格子有公共边），如果移动满足下列条件，则移动是可行的。 1没有一个以上的鬼在同一个格子里。 2没有一对鬼在一步里交换了位置。例如，假设鬼的位置是如右上图所示的，其中sharp(#)表示墙，空格表示走廊，a,b,c表示鬼：# ab#c#经过一步移动后，地图可以变成如下的样子：# # # # ab# a b# acb# ab #c# #c# # # #c# # # # #Input:输入包括最多10组数据，每组数据包含一幅地图。输入格式如下：第一行的w，h和n表示地图的宽度和高度，n表示鬼的数目，他们满足： 4w16，4h16，1n3接下来h行，每行w个字符：一个#表示墙。 一个小写字母表示鬼的初始位置（该位置也是走廊）。 一个大写字母表示鬼的目标位置（该位置也是走廊）。 一个空格表示空的走廊。在每幅地图里，前n个小写字母和前n个大写字母表示鬼的初始位置及鬼的目标位置。我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。最后一组数据后一行有三个0。Output:对每组数据输出一行一个整数，表示最小的移动步数。3魔鬼杀手你生活在一个怪兽世界里。你需要用魔法反抗这些怪兽。每个怪兽都有一定的hit points，表示他们的生命值。你可以靠施魔法，降低怪兽的hit points。每个魔法都会有一定的damage，表示会减少被攻击者damage的hit point。一个怪兽被击败了当前仅当它的hitpoint0。另一方面，魔法是要消耗魔力的。因为你的魔力是有限的，你希望用最少的魔力击败所有的怪兽。写一个程序完成这个任务。 Input: 输入按如下的格式给出：N是怪兽的数量(1N100)，Hpi表示第i个怪兽的hit point(lHPi100000)，M表示可用的魔法数量(1=M=lOo)，Namej是第j种魔法的名字，最长会有30个大写或小写字母，MPj是这种魔法需要消耗的魔力(0 $MPj99)，Targetj要么是”Single”，要么是”All”，表示该魔法只攻击单个怪兽或对全体怪兽同时有效。Damagej表示对于所有玫击对象，可以减少攻击对象Damagej的hit point(0Damagej999999)。所有数字都是整数。最少有一种魔法的Damge是非零的。Output:输出一行，包含一个整数，表示最小需要消耗的魔力。4染色的立方体小胖最近迷上了3D物体，尤其是立方体。他手里有很多个立方体，他想让所有的立方体全都长得一样，所以他决定给某些立方体的表面重涂颜色，使得所有的立方体完全相同。但是小胖是很懒的，他想知道最少涂多少次颜色，可以让所有立方体完全相同。Input.输入包含多组数据，每组数据第一行n(ln4)，表示立方体的数量，接下来n行，每行6个字符串，表示立方体6个面的颜色。Color l Color 2 Color 3 Color4 Color 5 Color 6其中，面的标号如下：两个立方体被视为相同，当且仅当它们可以在某种摆放方式下，每个面的颜色都对应相同。一种涂色的方案如下： Output:每组数据，输出一行一个整数，表示最少的涂色数。（涂一个面算一次涂色）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 hlue yellow magenta redmagenta red blue yellow cyan green3hlue green green green green bluegreen blue blue Teen green greengreen green green green green sea-green3red yellow red yellow red yellowred red yellow yellow re,d yeUow red red red red red red4 violet violet salmon salmon salmon salmon violet salmon salmon salmon salmon violet violet violet salmon salmon violet violet violet violet violet violet salmon salmon 1 red green hlue yellow magenta cyan4 magenta pink red scarlet vermilion wine-redaquamarine blue cyan indigo sky-blueturciuoise-blue blond cream chrome-yellow lemon olive yellow chrome-green emerald-green r;reen olive vilidiansky-blue 0 Output for the Sample Input 4 2 0 0 2 3 4 4 o 16试题分析 1帮助Bubu解析：我们不妨将连续一段颜色相同的合并，那么我们顺序考虑每一段，如果这一段的某一个要被拿走，那么这一段一定会被一起拿走，否则答案不会更优。那么我们考虑每次是拿走这一段，迹是留下这一段。最后考虑对于同一种颜色，如果为这种颜色的所有段都被拿走了，那么我们一定会把他们放到一起，然后An s+l。考虑到颜色数=8，我们可以用一个二进制状态来表示每种颜色是不是被全部取走了。因此可以这样描述状态：fijkl表示在前i段已经考虑完了，每种颜色是否被全部拿走的状态为j，还剩k次取走的操作，上次剩下的一段的颜色为1的情况下最少能组成的mess Value。转移的复杂度是O (1)的。这个DP的时间复杂度是O(N*K*28*8)的。PS: LTC在pku的bbs上说了一个O(N*K*28)的算法，大家可以去看看。参考程序：2.万圣节后的早晨解析：这是一道很明显的状态最短路问题，我采用的是双向BFS，用2563描述状态，53进行转移（当然，单向BFS+优化或A。应该也是可以在时限内出解的）。出于测试的时间问题，我没有采用多组数据进行测试。有兴趣的话，大家可以到PKU和valla上提交，看看程序的快慢。在PKU上这题的id是3523。cii-judge上的id是3888。参考程序：3魔鬼杀手解析：不妨分两步进行考虑，我们一定是用All这种魔法将所有monster的HP降低到某个level以下，然后再对每个monster单独使用Si