2001年信息学奥赛NOIP普及组
初赛
更早
2022-11-16 09:41:18
88次
一、单选题
二、简答题
在 A，B 两个城市之间设有 N 个路站(如下图中的 S1，且 N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20，且每条路段上的距离均为一个整数)。
A，B 的一条通路是指：从 A 出发，可经过任一路段到达 S1，再从 S1 出发经过任一路段，…最后到达 B。通路上路段距离之和称为通路距离(最大距离≤ 1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。
例如：下图所示是当 N=1 时的情况：
从 A 到 B 的通路条数为 6，但因其中通路 5+5=4+6，所以满足条件的不同距离的通路条数为 5。
算法说明：本题采用穷举算法。
数据结构：N：记录 A，B 间路站的个数
数组 D[I，0]记录第 I-1 到第 I 路站间路段的个数D[I，1]，D[I，2]，…记录每个路段距离
数组 G 记录可取到的距离
程 序 清 单 ：
【知识点】 信息学NOIP普及组
PRGORAM CHU7_4；
VAR N，K，I：INTEGER； A：ARRAY[1..40]OF INTEGER；
PROCEDURE FIND(X：INTEGER)； VAR S，I1，J1：INTEGER；
P：BOOLEAN；
BEGIN
I1:=0； P:=TRUE； WHILE P DO
BEGIN
I1:=I1+1； S:=0；
FOR J1:=1 TO N DO
IF A[J1]>A[I1]THEN S:=S+1； IF(S=X-1)THEN
BEGIN
WRITELN(A[I1])； P:=FALSE
END； END
END；
BEGIN
READLN(N，K)； FOR I:=1 TO N DO
READ(A[I])； FIND(K)； FIND(N-K)；
END.
输入：10 4
12 34 5 65 67 87 7 90 120 13
输出：
【知识点】 信息学NOIP普及组
