衢州市第十九届青少年信息学竞赛复赛试题.docVIP

衢州市第十九届青少年信息学竞赛复赛试题 (初中组 竞赛用时：3小时) 注意事项： 1、每个人按照号码顺序坐到相应的电脑前 2、每个人在自己的电脑的C盘建立一个目录2006，把自己所作的3道题分别命名为Testl.pas，Test2.pas，Test3.pas存放在该目录下，同时生成该程序对应的可执行代码文件，命名方式相3、为程序的主要函数写出注释 第一题 最长单调递增子序列(30分) 问题描述： 令A是由n个不同整数构成的序列，试设计一程序求A中最长的单调递增子序列。 输入： 第一行为n，表示有n个数 第2行为n个整数，整数之间用空格格开 输出： 最长单调递增子序列中整数的个数 输入样例： 9 输出样例： 5 （说明： 1 2 4 6 9） 参考程序： program li1; const maxn=100; var a,b,c:array[1..maxn] of integer; fname:string; f:text; n,i,j,max,p:integer; begin readln(n); for i:=1 to n do begin read(a[i]); b[n]:=1; c[n]:=0; end; for i:= n-1 downto 1 do begin max:=0;p:=0; for j:=i+1 to n do if (a[i]a[j]) and (b[j]max) then begin max:=b[j];p:=j end; if p0 then begin b[i]:=b[p]+1;c[i]:=p end end; max:=0;p:=0; for i:=1 to n do if b[i]max then begin max:=b[i];p:=i end; writeln(maxlong=,max); write(result is:); while p0 do begin writeln(a[p]:5);p:=c[p] end; readln end. 第二题最优乘车（30分） 问题描述： H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路，每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。 一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达S公园。 现在用整数1，2，…N给H城的所有的巴士站编号，假定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。 写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到s公园的过程中换车的次数最少。 输入： 每组数据第一行有两个数字M和N(1=M=100 1N=500)，表示开通了M条单程巴士线路，总共有N个车站。从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。 输出： 输出只有一行。如果无法乘巴士从饭店到达s公园，则；输出“NO”，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达。 输入样例： 4 l 5 2 11 1 3 4 5 9 3 6 11 7 8 10 11 12 13 15 输出样例： 2 第三题 百年校庆(40分) 为迎接百年校庆，某学校规划一项n天的庆祝计划，根据庆祝计划第I天需要Ni个礼仪生进行迎宾活动，为了提高礼仪生的积极性，学校为礼仪生提供了很多报务，其中一项服务就是要为每个礼仪生每天提供一块消毒毛巾，这种消毒毛巾用一天后必须再做消毒处理后才能使用。 消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（ba），A种消毒方式的费用为每块毛巾fA，B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f(新毛巾是已消毒的，当天可以使用)；而且ffAfB。学校管理人员正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，校长希望费用最低。 你的任务就是：为学校计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使学校在这项n天的庆祝活动中，提供毛巾服务的总费用最低。 输入： 第1行为n，a，b，f，fA，fB