1996年美国计算机程序设计选拔赛试题答案.doc

第一题: 给奶牛挤奶 (1 ) 解题思路本题要求出有人挤奶和空闲的最长时间段的长度。由于时间均为整数,且时间的最大值为32 000,所以我们用一个大小为32 000 的byte 型数组来记录每个时间是否有人挤奶。然后再找出最长的有人挤奶和空闲的时间段。注意题目中要求时间是从第一次挤奶时间开始至最后一次挤奶结束,而不是从 0 开始至 32 000。(2 ) 参考程序Var Time : Array0 . . 32000 Of Byte ; 记录每个时间是否有人挤奶 Milk : Ar ray 0 . . 1 Of Word; 有人挤奶和空闲的最长时间 n : Word ; 农夫人数 Procedure Init ; 读入数据并统计每个时间是否有人挤奶 Var f : Text ; s, e: Word; 挤奶的起始时间和结束时间 i : Word;BeginFillchar ( Time , Sizeof ( Time) , 0 ) ;Assign( f , input .c1 ) ; 0 3 1 Reset ( f ) ;Readln( f , n) ;For i = 1 To n Do Begin Readln( f , s, e) ; Fillchar ( Time s , e - s, 1) ; 从 e 到 s 时间内有人挤奶 End;Close ( f ) ;Fillchar (Milk, Sizeof ( Milk) , 0 ) ;End ;Procedure Calc; 计算有人挤奶和空闲的最长时间 Var First , Last : Word; 工作的起始时间和结束时间 i , j , State : Word; state存放此时间内是空闲 还是有人挤奶 BeginLast = 32000 ;First = 0 ;While Time Last = 0 Do Dec( Last ) ;Inc( Last ) ;While Time First = 0 Do Inc(First ) ;计算工作的起始和结束时间 State = 1 ;j = 0 ;For i = First To Last Do If Time i = State Then Inc ( j) Else Begin I f j MilkState Then MilkState = j; j 中存放此时间段的长度 State = 1 - State; j = 1 ; End;End ;Procedure Print ; 打印结果 BeginWriteln( Longest continuous time = , Milk1 ) ;Writeln( Longest idle time = , Milk 0 ) ;End ; 1 3 1 BeginInit ; 读入数据并初始化 Calc ; 计算两个最长时间段的长度 Print ; 打印结果 End .第二题: 谷仓迷宫 (1 ) 解题思路此题的关键是找出每个厩到其它厩的总距离。由于厩的总数不大于 2500,所以我们可以用宽度搜索来计算总距离:我们用数组 Stack 来记录宽度搜索的节点,用 Open 指向待扩展的节点,用 Top 记录数组中节点的数目。下面是宽度搜索的框架:总距离0 ;Open1 ;Top2 ;南京金鑫财税80/While Open Top Do Begin 找出从 Open 指向的厩能走到的厩; I f 此厩没有走过 Then Begin 将此厩加入数组; 总距离 + 此厩到起始厩的距离; End ; Open + 1 ; End;(2 ) 参考程序Type Code = Record Id, Step : Word; 厩的编号和到起始厩的距离 End;Var p : Word; 质数 p b, c : Array1 . . 4 Of Longint ; 对应的参数 Min : Real ; 最短平均距离 Which: Word; 中心厩的编号 Stack : Ar ray1 . . 2500 Of Code ; 宽度搜索用的数组 Open , Top : Word; 宽度搜索用的下标指针 Now : Longint ; 一个厩到其它厩的距离总和 2 3 1 Procedure Init ; 读入质数 p 和参数 b, c Var f : Text ; i : Word;BeginAssign( f , input .c2 ) ;Reset ( f ) ;Read( f , p) ;For i = 1 To 4 Do71/Close ( f ) ; 上海金水财税Min = 10000;End ;Procedure Judge; 判断是否出现重复 Var i : Word;BeginFor i = 1 To Top - 1 Do If Stack Top . Id = Stack i . Id Then Exit ;Stack Top .Step = StackOpen .Step + 1 ;Inc( Now, Stack Top . Step) ; 如果不重复则总距离加 Inc( Top) ; Step,并加入数组 End ;Procedure Find; 找出中心厩 Var i , j:Word;BeginFor i = 0 To p - 1 Do 计算每个厩到其它厩的距离总和 Begin Now = 0 ; Stack1 .Id = i; Stack1 .Step = 0 ; Open = 1 ; Top = 2; While Open Top Do 循环直至走遍所有厩 Begin For j = 1 To 4 Do 3 3 1 Begin Stack Top . Id = ( b j * StackOpen . Id + c j ) Mod p; Judge ; 判断新节点是否与原先节点重复 End; Inc(Open) ; End; I f Now/ (p - 1 ) 0 Do With Stack j Do Begin If f StackBack .What ,What cStackBack .What , What Then Inc ( f StackBack .What , What ) Else Dec( f What , StackBack .What ) ; j = Stack j .Back; End;End ;BeginFind = True ;Open = 1 ;Top = 1;Stack 1 .What = a ;Stack 1 .Back = 0;s = a ;While Open f What , i ) Or ( f i ,What 0) ) Then Begin Inc( Top) ; Stack Top .What = i ; Stack Top .Back = Open; Include( s, i) ; I f i = b Then Begin 如果找到则增流并退出 Increase ; Exit ; End; End; Inc (Open) ; End;Find = False ; 未找到增流路径 End ;Procedure Print ; 打印结果 7 3 1 Var i : Word;BeginInc(Which) ;Writeln( g - out , Network # , Which) ;Writeln( g - out , Num) ;For i = 1 To n Do If i In s - a, b Then Write( g - out , i, ) ;Writeln( g - out ) ;End ;Procedure Main; 主过程 BeginRepeat Readdata ; 读