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

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

1、冲刺NOIP2010模拟试题与解析（十）普及组复赛题目名称手机数字积木家族书本整理程序名称mobile.pas/c/cppbrick.pas/c/cppfamdy.pas/c/cppbook.pas/c/cpp输入文件mobile.inbrick.infamily.inbook.in输出文件mobile.outbrick.outfamily.outbook.out时间限制1秒1秒1秒1秒一、手机(mobile.pas/c/cpp)【问题描述】一般的手机的键盘是这样的：1 2 abc 3 def 4 ghi 5 jkl  6 mno 7 pqrs

2、 8 tuv 9 wxyz*0  #  要按出英文字母就必须要按数字键多下。例如要按出x就得按9两下，第一下会出w，而第二下会把w变成x。0键按一下会出一个空格。  你的任务是读取若干句只包含英文小写字母和空格的句子，求出要在手机上打出这个句子至少需要按多少下键盘。【问题输入】 一行一个句子，只包含英文小写字母和空格，且不超过200个字符。【问题输出】一行一个整数，表示按键盘的总次数。【样例输入】  i have a dream【样例输出】  23【数据范围】  如题目所示  二、数字积木(brick.pas/c/cpp)【问题描述】  小明有

3、一款新式积木，每个积木上都有一个数，一天小明突发奇想，要是把所有的积木排成一排，所形成的数目最大是多少呢？  你的任务就是读入n个数字积木，求出所能形成的最大数。【问题输入】第一行是一个整数n(n≤1000)，接下来n行每行是一个正整数。【问题输出】  所能形成的最大整数【样例输入】313131343【样例输出】34313131【数据范围】30%的数据，n≤l0，每个数<103。50%的数据，n≤l00。100%的数据，n≤1000，每个数<10200。三、家族(family.pas/c/cpp)【问题描述】在一个与世隔绝的岛屿上，有一个有趣的

4、现象：同一个家族的人家总是相邻的（这里的相邻是指东南西北四个方向），不同的家族之间总会有河流或是山丘隔绝，但同一个家族的人不一定有相同姓氏。现在给你岛上的地图，求出岛上有多少个不同的家族。岛上的地图有n行，每行有若干列，每个格子中要么是“”，表示大海，要么是“*”，表示河流或山丘，要么是小写字母，表示一户人家的姓氏。【问题输入】第一行是个数字N，表示下面信息的行数。接下来是N行字符，每行由小写字母和*号组成，有些行的最前面也可能包含若干连续的空格，表示这些区域是大海，每一行最多不超过200个字符。【问题输出】一个数字，表示家族数。【样例输入】4

5、*zlw**pxhl*zlwk*hx*w*tyy**yyyzzl【样例输出】3【数据范围】 10%的数据，n≤1。 30%的数据，n≤10。 100%的数据，n≤100每一行最多不超过200个字符。四、书本整理(book.pas/c/cpp)【问题描述】    小明的书架上放了许多书，为了使书架变得整洁，小明决定整理书架，他将所有书按高度大小排列，这样排了之后虽然整齐了许多，但小明发现，书本的宽度不同，导致书架看上去还是有些凌乱。小明把这个凌乱值定义为相邻两本书的宽度差的绝对值的和。    例如有4本书：1×25×32×43×1那么小明将其排列

6、整齐后的顺序是：l×22×43×15×3凌乱值就是2+3+2=7。    于是小明决定拿掉其中的k本书，使凌乱值最小，你能帮他求出这个最小值吗？已知每本书的高度都不一样。【问题输入】    第一行两个数字n和k，代表书总共有n本，要求从中去掉k本。(1≤n≤100,1≤k

7、le.pas/c/cpp)算法分析：本题是简单的计数问题，只要注意：(1)7键和9键可表示4个字母；(2)不要忘了空格0，就行了。参考程序：二、数字积木(brick.pas/c/cpp)算法分析：本题每个数都比较大，所以用字符串操作。朴素算法是求出所有排列，求出其中能拼成的最大值，这样能拿30分左右。一种贪心策略是单纯地比较字符串间的大小，把大的放在前面。但很快就能发现反例，例如：“131”>“13”，但“13113”<“13131”。那我们再考虑一下拼接后的情况，在操作时，将单纯地比较字符串大小变成比较“拼接”后的字符串大小就可以了。例如：比

8、较131和13，因为“13113”<“13131”，所以13应该比131大，应排在131前面。所以只有用一个排序算法，把两个字符串的大小比较改为“拼接