奥赛精解(练习题).doc

一、棋盘类题目1.马拦过河卒 中学高级本（紫皮）P2、奥赛精解练习题P266页棋盘上A（0,0）点有一个过河卒，需要走到目标B（n，m）点。卒街的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在点及所有跳跃一步可达点称为马的控制点。因此称之为“马拦过河卒”。输入：一行四个数据，表示B点和C点马的坐标，n、m均为不超过15的整数。输出：一个数据，表示所有的路径数。【分析】遍历每个点的路径，A点所在行及列上点的路径均为1，马的9个控制点的路径均为0，其余每个点的路径为ax,y:=ax,y-1+ax-1,y。2.设有一个n*m方格的棋盘（1m,n100）。求出该棋盘中包含多少个正方形、多少个长方形（不包括正方形）。(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 输出：正方形的个数与长方形的个数如上例：输入：2 3 输出：8，10【分析】二、贪心算法 中学高级本（紫皮）P221.排队接水有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。输入：输入文件共2行，第一行为n；第二行为每个人的接水等待时间输出：文件为2行，第一行为排队顺序，第二行为平均等待时间。2.智力大冲浪智力大冲浪节目，奖励每个参赛者m元，首先比赛时间为n个时段(n=500),它又给出了很多小游戏，每个小游戏都必须在规定期限Ti前完成（1=Ti=n)。如果一个游戏没能在规定的期限前完成，则要从奖励费m元中扣去一部分钱Wi，Wi为自然数，不同的游戏扣去的钱是不一样的，当然，每个游戏本身都很简单，保证每个人都能在一个时段完成，而且都必须从整数段开始，主持人只是想考考参赛者如何安排组织自己做游戏的顺序，作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱，注意，比赛绝不让参赛者赔钱。问题输入 输入文件in.txt，共4行。 第1行为m，表示一开始奖励给每位参赛者的钱； 第2行为n，表示有n个小游戏； 第3行有n个数，分别表示游戏1到n的规定完成期限； 第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。 问题输出 输出文件out.txt，仅1行。表示小伟能赢取最多的钱。 输入样例 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 输出样例 9950 3.火柴棒题目：阿姆斯特朗数如果一个n位正整数等于其各位数字的n次方之和,则称该数为阿姆斯特朗数。例如13 + 53 + 33 = 153 当n3时，又称水仙花数，特指一种三位数，其各个数之立方和等于该数。水仙花数共有4个，分别为：153、370、371、407。题目：史密斯数。输出49999中的所有史密斯数。史密斯数是可以分解的整数，且所有数位上的数字和等于其全部素数因子的数字总和。例如：9975=355719 9+9+7+5=30 3+5+5+7+1+9=30贪心策略1.删数问题（最大整数）奥赛精解练习题P266页/奥赛经典金钥匙P58页文件输入一个高精度的正整数n（0 do Begin I:=1; While (ilength(n) and (ni1) and (n1=0) do delete(n,1,1)输出n;2.合并果子奥赛经典金钥匙P58页在一个果园里，所有果子已经打下来，分成不同数目的堆，多多决定把所有果子合并为一堆。每一次可以合并两堆，消耗体力等于两堆果子重量之和。经过n-1次合并后，就剩下一堆，还要再搬回家，所以要尽量的节省体力，设计出合并的方案，使消耗体力最少，并输出最小的体力耗费值。例如:有3种果子，数目依次为1，2，9。可以先1、2堆合并，新堆数目为3，耗费体力3，再将新堆与3堆合并，新堆数目为12，耗费体力为12，总共耗费体力=3+12=15。输入：两行，第一行整数n（1=n=10000）,表示果子的种类数。第二行包含n个整数，用空格分开，第i个整数ai(1=ai=20000)是第i种果子的数目。输出：一行，包含一个整数，最小耗费体力值。输入数据保证这个值231。3.混合牛奶奥赛经典金钥匙P53页帮助包装牛奶制造商，以可能最廉价的方式取得他们所需的牛奶。包装公司从一些农民那里购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同，一只母牛一天只能产生定量的奶，因此农民每天只有一定量的牛奶供应。每天，包装公司从每个农民那里购买一定量的牛奶（少于或等于农民所提供的最大值）。给出包装公司的牛奶需求，连同每个农民的提供牛奶数量及每加仑的价格，计算应当如何从农民那里购买一定量的牛奶，才能使包装公司付出的钱最少。注意：每天农民产的牛奶总量是足够的。输入：第1行，两个整数，n和m。0=n=2000000)是包装商一天需求量；m是农民的人数。第2行到m+1行，每行2个整数，pi和ai，0=pi=1000是农民i牛奶的价格；0=aib+a则abA: array1.10000 of string;X：integer;Readln(f,n);For i:=1 to n doBegin Read(f,x); str(x,ai); End;For i:=1 to n-1 do For j:=i+1 do n do If ai+ajaj+ai then 交换5取数游戏 奥赛精解练习题 P262页给出2n(n100)个自然数(数小于等于30000).游戏双方分别为A方(计算机方)和B方(对弈的人).只允许从数列两头取数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和最大为取胜方；若双方相等，属于A胜。试问A方可否有必胜策略？【输入格式】两行，第一行为n。第二行一共2n个自然数，中间以空格格开。【输出格式】共3n+2行，其中前3n行为游戏经过。每3行分别为A方所取的数和B方所取的数，B方取数前应给予适当的提示，让游戏者选择取哪一头的数（L/R表示左和右）。最后2行分别是A方取数的和与B方取数的和。60/1背包问题奥赛精解练习题 P263页有一容量为weight的背包。现在要从n件物品中选取若干装入背包，每件物品i的重量为wi，价值为pi。定义一种可行的背包装载为：背包中物品的总重量不能超过背包的容量，并且一个物品要么全取，要么不取，定义最佳装载是指所装入的物品价值最高，并且是可行的背包装载。样例输入：11 容量weight42 4 6 7 wi6 10 12 13 pi样例输出：0 1 0 1 23动态规划算法程序如下：var opt:array0.100,1.100 of integer; w,p:array1.100 of integer; wm,n,i,j,max:integer;begin readln(n,wm); for i:=1 to n do readln(wi,pi); for i:=1 to n do for j:=1 to wm do begin if j-wi0 then opti,j:=opti-1,j else if opti-1,j(opti-1,j-wi+pi) then opti,j:=opti-1,j-wi+pi else opti,j:=opti-1,j; end; write(optn,wm);end.7.独木舟 奥赛精解练习题 P264页计划组织独木舟旅行，租用的独木舟都是一样的，最多乘两人，而且载重有一个限度。现在要节约费用，所在要尽可能租用最少的舟。输入文件：第一行读入舟载重量w，80=w=200；第二行是整数n，1=n=30000；接下来的n行，每行是一个整数，每人的体重，范围5.w。输出文件：一行，最小的租用数目。三、排序1.直接插入排序 奥赛精解练习题 P163页假设待排序数据存放在数组A1.n中，则A1可看做是一个有序序列，让i从2开始，依次将Ai插入到有序序列A1.i-1中，An插入完毕则整个过程结束，A1.n成为有序序列。算法实现：可在数组中增加元素A0作为关键值存储器和循环控制开关。第i趟排序，即Ai的插入过程为：保存AiA0； j=i-1；如果AjAj+1，完成插入；否则，将Aj后移一个位置：Aj-Aj+1；j=j-1；继续执行；Procedure insertsort(n:integer);VAR i,j:integer;Begin For i:=2 to n do Begin a0:=ai; J:=i-1;While aja0 do begin aj+1:=aj; j:=j-1; end;aj+1:=a0;end;end;2.交换排序冒泡排序 奥赛精解练习题 P166页Program bubble(n:integer);Var temp,i,j:integer; Change:boolean;Begin For i:=1 to n-1 doBegin change:=false; For j:=n-1 downto i do If ajaj+1 then Begin change:=true; temp:=aj; aj:=aj+1; aj+1:=temp;end; if not(change) then exit;end;end;3.交换排序快速排序 奥赛精解练习题 P167页在a1.n中任取一个数据元素作为比较的“基准”（记为x）,将数据区划分为左右两个部分：a1.i-1和ai+1,n，且a1.i-1 xai+1.n(1in)，当a1.i-1和ai+1.n非空时，分别对它们进行上述的划分过程，直至所有数据元素均已排序为止。设要排序的数组是A0AN-1，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是： 1）设置两个变量I、J，排序开始的时候：I=0，J=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即 key=A0； 3）从J开始向前搜索，即由后开始向前搜索（J=J-1即J-），找到第一个小于key的值Aj，Aj与Ai交换； 4）从I开始向后搜索，即由前开始向后搜索（I=I+1即I+），找到第一个大于key的Ai，Ai与Aj交换； 5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。） 示例：待排序的数组A的值分别是：（初始关键数据：key=49） 注意关键key永远不变，永远是和key进行比较，无论在什么位置，最后的目的就是把key放在中间，小的放前面大的放后面。 A0A1A2A3A4A5A649386597761327进行第一次交换后：27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找，此时:J=6） 进行第二次交换后：27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找key的值，6549,两者交换，此时：I=2 ) 进行第三次交换后：27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后：27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大于key的值，9749，两者交换，此时：I=3,J=5 ) 此时再执行第三步的时候就发现I=J=3，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49的数全部在49的后面，所有小于key（49）的数全部在key（49）的前面。四、穷举法奥赛精解练习题 P180页例1完全数。因子的和等于它本身的数是完全数（自身因子除外）。例2在A、B两个城市之间设有N个路站（N100），城市与路站之间、路站与路站之间各有若干条路段（各路段数20，且每条路段上的距离均为一个整数）。A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段最后到达B。通路上路段距离之和称为通路距离（最大距离1000）。当所有的路段距离给出之后，求出所有不同距离的通路个数（相同距离仅记一次）。例如下图N=1时的情况： 5 6 A 7 S1 B 4 5从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路数为5。例3尺子刻度问题。一条29厘米长的尺子，只允许在上面刻七个刻度，要能用它量出129厘米的各种长度。尺子的刻度该如何选择。赛题：奥赛精解练习题 P187页1古纸残篇在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了，只留下曾经写过字的痕迹，依稀还可看出是一个乘法算式如图。这个算式上原来的数字是什么呢？夹着这张纸的书页上，标明“素数”，经研究发现这个算式中的每个数字都是素数，而且这样的算式是只唯一的，把这个算式写出来。奥赛精解练习题 P250页1.快速排序（非递减排序）2.循环比赛日程表设有有2 n（n=6）个球队进行单循环比赛，计划在2 n 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n 1天内每个队都与不同的对手比赛。例如n=2时的比赛安排： 队 1 23 4 比赛 1=23=4 一天 1=32=4 二天 1=4 2=3 三天3.小车问题甲乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。输入：一行，三个整数，分别表示AB两地的距离s米（ba.。输出：两人同时到达B地需要的最短时间，单位秒，保留2位小数。样例：car.in 120 5 25 Car.out 9.60Const zero=1e-4;Var s,a,b,c,c0,c1,t1,t2,t3,t4:realBegin Readln（s,a,b）;c0=0; c1:=s;repeat c:=(c0+c1)/2; t3:=c/b; t1:=t3+(s-c)/a;t4:=(c-t3*a)/(a+b);t2:=t3+t4+(s-(t3+t4)*a)/b;if t1t2 then c1:=c else c0:=c; until abs(t1-t2)zero; writeln(t1);end.4.取余运算输入b,p,k的值，求bp mod k的值。其中b,p,k*k为长整形数。样例：mod.in 2 10 9Mod.out 210 mod 9 =75.地毯填补问题棋盘覆盖问题相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择(如下图)： 并且每一方格只能用一层地毯，迷宫的大小为2的k次方见方的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1秒。 Input ：输入文件共2行。 第一行：k，即给定被填补迷宫的大小为2k（0第二行：x y，即给出公主所在方格的坐标（x为行坐标，y为列坐标），x和y之间有一个空格隔开。 Output ：将迷宫填补完整的方案：每一补（行）为 x y c (x，y为毯子拐角的行坐标和列坐标，c为使用毯子的形状，具体见上面的图1，毯子形状分别用1、2、3、4表示，x、y、c之间用一个空格隔开)。习题训练：1.美丽的大树 pascal 【问题描述】平江路是苏州最美丽的道路，路中间的绿化带上种了两列（边）漂亮的大树，这些大树分成了50行，每行两棵大树，一共100棵大树，这些大树被编上了号，编号方式如下：1 3 5 7 45 47 49 2 4 6 8 46 48 50 但是昨天晚上却发生了一件令人震惊的大事-可恶的破坏分子竟然偷去了这100棵大树中的一部分！公安部门马上出动，列出了被偷去了大树的编号。现在摆在我们面前的情况是