奥赛精解(练习题)

《奥赛精解(练习题)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、棋盘类题目1.马拦过河卒中学高级本（紫皮）P2、《奥赛精解练习题》P266页棋盘上A（0,0）点有一个过河卒，需要走到目标B（n，m）点。卒街的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在点及所有跳跃一步可达点称为马的控制点。因此称之为“马拦过河卒”。输入：一行四个数据，表示B点和C点马的坐标，n、m均为不超过15的整数。输出：一个数据，表示所有的路径数。【分析】遍历每个点的路径，A点所在行及列上点的路径均为1，马的9个控制点的路径均为0，其余每个点的路径为a[x,y]:=a[x,y-1]+a[x-1,y]。2.设有一个n*m方格的棋盘（1≤m,n≤100）。求出该棋

2、盘中包含多少个正方形、多少个长方形（不包括正方形）。(Noip97-1)例如：当n=2，m=3时，正方形的个数有8个；即边长为1的正方形有6个；边长为2的正方形有2个。长方形的个数有10个；即2*1的长方形有4个；1*2的长方形有3个；3*1的长方形有2个；3*2的长方形有1个。程序要求：输入：n和m输出：正方形的个数与长方形的个数如上例：输入：23输出：8，10【分析】二、贪心算法中学高级本（紫皮）P221.排队接水有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。输入：输入文件共2行，第一行为n；第二行为每个人的接水

3、等待时间输出：文件为2行，第一行为排队顺序，第二行为平均等待时间。2.智力大冲浪智力大冲浪节目，奖励每个参赛者m元，首先比赛时间为n个时段(n<=500),它又给出了很多小游戏，每个小游戏都必须在规定期限Ti前完成（1=

4、共4行。第1行为m，表示一开始奖励给每位参赛者的钱；第2行为n，表示有n个小游戏；第3行有n个数，分别表示游戏1到n的规定完成期限；第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。[问题输出]输出文件out.txt，仅1行。表示小伟能赢取最多的钱。[输入样例]100007424314670605040302010[输出样例]99503.火柴棒题目：阿姆斯特朗数如果一个n位正整数等于其各位数字的n次方之和,则称该数为阿姆斯特朗数。例如1^3+5^3+3^3=153当n＝3时，又称水仙花数，特指一种三位数，其各个数之立方和等于该数。水仙花数共有4个，分别为：153、370、371、

5、407。题目：史密斯数。输出4—9999中的所有史密斯数。史密斯数是可以分解的整数，且所有数位上的数字和等于其全部素数因子的数字总和。例如：9975=3×5×5×7×199+9+7+5=303+5+5+7+1+9=30贪心策略1.删数问题（最大整数）《奥赛精解练习题》P266页/《奥赛经典金钥匙》P58页文件输入一个高精度的正整数n（<=240位），去掉其中任意s个数字后剩下的数字按左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。分析：按高位到低位搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。如何寻找递减区间首字符，需要

6、注意可能会出现串首有若干个0的情况。输入n,sWhiles>0doBeginI:=1;While(i1)and(n[1]=’0’)dodelete(n,1,1)输出n;2.合并果子《奥赛经典金钥匙》P58页在一个果园里，所有果子已经打下来，分成不同数目的堆，多多决定把所有果子合并为一堆。每一次可以合并两堆，消耗体力等于两堆果子重量之和。经过n-1次合并后，就剩下一堆，还要再搬回家，所以要尽量的节省体力，设计出合并的方案，使消耗体力最少，并输出

7、最小的体力耗费值。例如:有3种果子，数目依次为1，2，9。可以先1、2堆合并，新堆数目为3，耗费体力3，再将新堆与3堆合并，新堆数目为12，耗费体力为12，总共耗费体力=3+12=15。输入：两行，第一行整数n（1<=n<=10000）,表示果子的种类数。第二行包含n个整数，用空格分开，第i个整数a[i](1<=a[i]<=20000)是第i种果子的数目。输出：一行，包含一个整数，最小耗费体力值。