第九届全国青少年信息学奥林匹克联赛（N0IP2003）
复赛提高组解题报告
题一源程序
题二源程序
题三源程序
题四源程序
题一
神经网络
【问题背景】
人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。
【问题描述】
在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经
元之间至多有一条边相连，下图是一个神经元的例子：
神经元〔编号为1）
图中，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，
Ui是阈值，可视为神经元的一个内在参数。
神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神
经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元
输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。
兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）
公式中的Wji（可能为负值）表示连接j号神经元和
i号神经元的边的权值。当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。
如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。
【输入格式】
输入文件第一行是两个整数n（1≤n≤200）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。
【输出格式】
输出文件包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！
若输出层的神经元最后状态均为 0，则输出
NULL。
【输入样例】
5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1
【输出样例】
3 1
4 1
5 1
[分析]本题是比较简单的，但要注意神经元的层数，只输出最大层（输出层）的状态非零的神经元的状态，在中间层中只有神经元处于兴奋状态时（Ci>0）才会向下一层传送信号。
[PASCAL源程序]
program NOIP2003_1_Network;
const
maxn=200;maxp=200;
var
i,j,n,p,maxlayer:integer;
w:array[0..maxp]of
longint;{存放边的权值}
start,terminal:array[0..maxp]of
byte;{存放边的起点与终点}
u,c:array[0..maxn]of
longint;{存放神经元的阀值与状态值}
layer:array[0..maxn]of
byte;{存放神经元的层数}
f1,f2:text;fn1,fn2,fileNo:string;
flag:boolean;
begin
write('Input
fileNo:');
readln(fileNo);
fn1:='network.in'+fileNo;
fn2:='network.ou'+fileNo;
assign(f1,fn1);reset(f1);
assign(f2,fn2);rewrite(f2);
readln(f1,n,p);
for
i:=1 to n do readln(f1,c[i],u[i]);
fillchar(layer,sizeof(layer),0);
for
i:=1 to p do begin
readln(f1,start[i],terminal[i],w[i]);{读入边的起点，终点，权}
layer[terminal[i]]:=layer[start[i]]+1;{计算终点的层数（比起点大1）}
end;
close(f1);
maxlayer:=layer[terminal[p]];{求最大层数，即输出层的层数}
for
i:=1 to n do{计算非输入层的节点i的状态值}
if layer[i]>0 then begin
for j:=1 to p do
if (terminal[j]=i) and (c[start[j]]>0){与目标节点i有边相连的节点j且其状态处于兴奋时（Cj>0）才向节点I传送信号}
then c[i]:=c[i]+w[j]*c[start[j]];
c[i]:=c[i]-u[i];
end;
{输出结果}
flag:=true;
for
i:=1 to n do
if (layer[i]=maxlayer) and (c[i]>0) then begin
writeln(f2,i,' ',c[i]);
flag:=false;
end;
if
flag then writeln(f2,'NULL');
close(f2);
end.
[点评]基本题。题目阅读起来有些费神，题中边的权值W,神经元的状态值C,阀值U，均未明确指出其取值范围，反映出命题不严谨。
题二
侦探推理
【问题描述】
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词中出现的其他话，都不列入逻辑推理的内容。
明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。
现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！
【输入格式】
输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。
【输出格式】
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出
Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出
Impossible。
【输入样例】
3 1 5
MIKE
CHARLES
KATE
MIKE:I am guilty.
MIKE:Today is
Sunday.
CHARLES:MIKE is
guilty．
KATE:I am guilty.
KATE:How are you??
【输出样例】
MIKE
[分析]基本思路有两种：一是可以穷举M个人中有N个人始终说假话的所有组合，据此出发，判断每句证词的真伪，再推断谁是罪犯，但这样做运算量大；二是可以穷举M个人中的任意一个是罪犯，由此再来判断每句证词的真伪，推断谁说真话谁说假话，这样做运算量小得多。这里采用后者。有几点必须注意：一，不能说找到某人是罪犯或可能是罪犯就完事了，还必须确保是否还有别人是罪犯或可能是罪犯；二，如何处理关于星期的证词呢？还是可以采用穷举；三，某人的证词可能前后矛盾，在给某人标记他是始终说真话还是始终说假话时，一定要考察他此前的诚信记录；因此，对某人的诚信记录要有4种不同的区分，可用0表示此人尚无有效记录（未说过真话也未说过假话），用1表示此人说真话，用2表示此人说假话，用3表示此人说的话与他前面的证词冲突；四，如何判断最初穷举时设定的前提（某人是罪犯）是否是本题的一个解呢？如果有人的诚信记录为3，则肯定不是本题的解；但是也不能强求诚信记录为2的人的总数一定要等于n，而是只要诚信记录为2的人不超过n且诚信记录为1的人不超过m-n即可，因为诚信记录为0的人可能说真话也可能说假话，他们只是没有说话，或只说了废话。五，由于证词要反复用于判断，可以先剔除其中的无效证词；为处理方便，将有效证词分为两部分：不含星期的和含星期的。
[PASCAL源程序]
program NOIP2003_2_Logic;
const
maxm=20;
dow:array[1..7]of
string=('Sunday.','Monday.','Tuesday.','Wednesday.',
'Thursday.','Friday.','Saturday.');
var
i,j,k,weekday,m,n,p,p1,p2,p3,index,resolution,total1,total2:byte;
name:array[1..maxm]of
string;{存放人名}
witness10,witness20:array[1..100]of
byte;{存放说话人的序号,分为两类,前者存放不含星期的证词的说话人的序号,后者存放只含星期的证词的说话人的序号}
witness1,witness2:array[1..100]of
string;{存放证词,分为两类,第一类是不含星期的证词,第二类是只含星期的证词}
name0,temp,temp0,temp1,temp2:string;
truth,truth0:array[1..maxm]of
byte; {存放诚信记录}
f1,f2:text;fn1,fn2,fileNo:string;
flag:boolean;
begin
write('Input
fileNo:');readln(fileNo);
fn1:='logic.in'+fileNo;fn2:='logic.ou'+fileNo;
assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2);
readln(f1,m,n,p);
for
i:=1 to m do readln(f1,name[i]);
total1:=0;total2:=0;
for
i:=1 to p do begin{对证词预处理}
readln(f1,temp);
index:=pos(': ',temp);
temp1:=copy(temp,1,index-1);{取得说话人姓名}
temp2:=copy(temp,index+2,length(temp)-index-1);{取得证词}
if
(temp2='I am guilty.') or (temp2='I am not guilty.') then
for j:=1 to m do
if
name[j]=temp1 then begin
inc(total1);{total1表示第一类证词的总数}
witness10[total1]:=j;{记下第一类第total1条证词的说话人的序号}
witness1[total1]:=temp2;{记下第一类第total1条证词}
break;
end;
if (pos(' is guilty.',temp2)>0) or (pos(' is not
guilty.',temp2)>0) then begin
temp0:=copy(temp2,1,pos(' is ',temp2)-1);{取得证词的叙述对象(主语)}
flag:=false;
for k:=1 to m do
if temp0=name[k] then begin
flag:=true;
break;
end;
if flag then{如果证词的叙述对象(主语)确实存在}
for j:=1 to m do
if name[j]=temp1 then begin{记入到第一类证词中}
inc(total1);
witness10[total1]:=j;
witness1[total1]:=temp2;
break;
end;
end;
flag:=false;
for j:=1 to 7 do
if temp2='Today is '+ dow[j] then begin
flag:=true;
break;
end;
if flag then{如果证词是关于星期的判断}
for j:=1 to m do
if name[j]=temp1 then begin{记入到第二类证词中}
inc(total2);{total2表示第二类证词的总数}
witness20[total2]:=j;{记下第二类第total2条证词的说话人的序号}
witness2[total2]:=temp2;{记下第二类第total2条证词}
break;
end;
end;
close(f1);
resolution:=0;{resolution表示解的个数
}
for
i:=1 to m do begin{穷举,第i个人为罪犯}
if
resolution>1 then break;{如果解的个数多于1个,则跳出循环}
fillchar(truth,sizeof(truth),0);{诚信记录赋初值为0,表示此人尚无有效证词}
for j:=1 to total1 do begin{逐条处理第一类证词}
if witness1[j]='I am guilty.' then begin{如果证词为I
am guilty.}
if i=witness10[j] then{如果说话人就是罪犯,则本证词为真}
case truth[i] of
0:truth[i]:=1;{如果此人的诚信记录为0,则此人说真话(记为1)}
2:truth[i]:=3;{如果此人的诚信记录为2(即以前说假话),则此人自相矛盾(记为3)}
end
else{如果说话人不是罪犯,则本证词为假}
case
truth[witness10[j]] of
0:truth[witness10[j]]:=2;{如果此人的诚信记录为0,则此人说假话(记为2)}
1:truth[witness10[j]]:=3;{如果此人的诚信记录为1(即以前说真话),则此人自相矛盾(记为3)}
end;
end;
if witness1[j]='I am not guilty.' then begin{如果证词为I
am not guilty.}
if i=witness10[j] then{如果说话人是罪犯,则本证词为假}
case truth[i] of
0:truth[i]:=2;
1:truth[i]:=3;
end
else{如果说话人不是罪犯,则本证词为真}
case truth[witness10[j]] of
0:truth[witness10[j]]:=1;
2:truth[witness10[j]]:=3;
end;
end;
if (pos(' is guilty.',witness1[j])>0) then
begin{如果证词含有is guilty. }
temp:=copy(witness1[j],1,pos(' is
guilty.',witness1[j])-1);{取得证词的主语}
if name[i]=temp then{如果证词的主语是罪犯,则本证词为真}
case truth[witness10[j]] of
0:truth[witness10[j]]:=1;
2:truth[witness10[j]]:=3;
end
else{如果证词的主语不是罪犯,则本证词为假}
case truth[witness10[j]] of
0:truth[witness10[j]]:=2;
1:truth[witness10[j]]:=3;
end;
end;
if (pos(' is not guilty.',witness1[j])>0) then
begin{如果证词含有is not guilty. }
temp:=copy(witness1[j],1,pos(' is not
guilty.',witness1[j])-1);{取得证词的主语}
if name[i]=temp then{如果证词的主语是罪犯,则本证词为假}
case truth[witness10[j]] of
0:truth[witness10[j]]:=2;
1:truth[witness10[j]]:=3;
end
else{如果证词的主语不是罪犯,则本证词为真}
case truth[witness10[j]] of
0:truth[witness10[j]]:=1;
2:truth[witness10[j]]:=3;
end;
end;
end;{第一类证词全部处理完毕}
if total2>0 then begin{如果有第二类证词存在,处理第二类证词}
for k:=1 to m do truth0[k]:=truth[k];{记下第一类证词全部处理完毕后的诚信记录}
for weekday:=1 to 7 do begin{穷举,今天是星期日,星期一直到星期六}
for k:=1 to m do truth[k]:=truth0[k];{诚信记录还原为第一类证词全部处理完毕后的诚信记录}
for j:=1 to total2 do{逐条处理第二类证词}
if pos(dow[weekday],witness2[j])>0 then{如果证词中含有当前穷举的星期值,则本证词为真}
case truth[witness20[j]] of
0:truth[witness20[j]]:=1;
2:truth[witness20[j]]:=3;
end
else{如果证词中不含有当前穷举的星期值,则本证词为假}
case truth[witness20[j]] of
0:truth[witness20[j]]:=2;
1:truth[witness20[j]]:=3;
end;
p1:=0;p2:=0;p3:=0;
for k:=1 to m do if truth[k]=1 then inc(p1);{p1表示始终说真话的人的总数}
for k:=1 to m do if truth[k]=2 then inc(p2);{p2表示始终说假话的人的总数}
for k:=1 to m do if truth[k]=3 then inc(p3);{p3表示说过自相矛盾的话的人的总数}
if (p1<=m-n) and (p2<=n) and (p3=0) then
begin{如果说真话的人的总数小于等于m-n且说假话的人的总数小于等于n且没有人说过自相矛盾的话,那么当前罪犯i就是本题的一个解}
name0:=name[i];{记下罪犯的姓名}
inc(resolution);{解的个数增1}
break;{退出星期的穷举}
end;
end;{星期的穷举完毕}
end;{第二类证词处理完毕}
p1:=0;p2:=0;p3:=0;
for k:=1 to m do if truth[k]=1 then inc(p1);
for k:=1 to m do if truth[k]=2 then inc(p2);
for k:=1 to m do if truth[k]=3 then inc(p3);
if (p1<=m-n) and (p2<=n) and (p3=0) and
(name0<>name[i]) then begin{为避免重复计解,此处多加了一个条件:
name0<>name[i]}
name0:=name[i];
inc(resolution);
end;
end;
if
resolution=1 then writeln(f2,name0);{如果只有一个解,则输出罪犯姓名}
if
resolution=0 then writeln(f2,'Impossible');{如果无解,则输出Impossible}
if
resolution>1 then writeln(f2,'Cannot Determine');{如果有多个可能解,则输出Cannot
Determine }
close(f2);
end.
[点评]基本题，比较复杂，重点考查参赛者的字符串运算和逻辑运算，逻辑推理能力。难点主要在于如何处理关于星期的证词，以及证词之间是否存在矛盾。
题三
加分二叉树
【问题描述】
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
【输入格式】
第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
【输出格式】
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2 4 5
[分析]很显然，本题适合用动态规划来解。如果用数组value[i,j]表示从节点i到节点j所组成的二叉树的最大加分，则动态方程可以表示如下：
value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j],
value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j],
value[j,j]+value[i,j-1]}
题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点，用数组root[i,j]表示
[PASCAL源程序]
{$N+}
program NOIP2003_3_Tree;
const
maxn=30;
var
i,j,n,d:byte;
a:array[1..maxn]of
byte;
value:array[1..maxn,1..maxn]of
comp;
root:array[1..maxn,1..maxn]of
byte;
s,temp:comp;
f1,f2:text;fn1,fn2,fileNo:string;
procedure
preorder(p1,p2:byte);{按前序遍历输出最大加分二叉树}
begin
if p2>=p1 then begin
write(f2,root[p1,p2],' ');
preorder(p1,root[p1,p2]-1);
preorder(root[p1,p2]+1,p2);
end;
end;
begin
write('Input
fileNo:');readln(fileNo);
fn1:='tree.in'+fileNo;fn2:='tree.ou'+fileNo;
assign(f1,fn1);reset(f1);
assign(f2,fn2);rewrite(f2);
readln(f1,n);
for
i:=1 to n do read(f1,a[i]);
close(f1);
fillchar(value,sizeof(value),0);
for
i:=1 to n do begin
value[i,i]:=a[i];{计算单个节点构成的二叉树的加分}
root[i,i]:=i;{记录单个节点构成的二叉树的根节点}
end;
for
i:=1 to n-1 do begin
value[i,i+1]:=a[i]+a[i+1];{计算相邻两个节点构成的二叉树的最大加分}
root[i,i+1]:=i;{记录相邻两个节点构成的二叉树的根节点；需要说明的是，两个节点构成的二叉树，其根节点可以是其中的任何一个；这里选编号小的为根节点，则编号大的为其右子树；若选编号大的为根节点，则编号小的为其左子树；因此，最后输出的前序遍历结果会有部分不同，但同样是正确的。如果最大加分二叉树的所有节点的度数都是0或2，则最后输出的前序遍历结果是唯一的。}
end;
for
d:=2 to n-1 do begin{依次计算间距为d的两个节点构成的二叉树的最大加分}
for i:=1 to n-d do begin
s:=value[i,i]+value[i+1,i+d];{计算以i为根节点，以i+1至i+d间所有节点为右子树的二叉树的最大加分}
root[i,i+d]:=i; {记录根节点i}
for j:=1 to d do begin
temp:=value[i+j,i+j]+value[i,i+j-1]*value[i+j+1,i+d];{计算以i+j为根节点，以i至i+j-1间所有节点为左子树，以i+j+1至i+d间所有节点为右子树的二叉树的最大加分}
if temp>s then begin{如果此值为最大}
s:=temp;root[i,i+d]:=i+j;{记下新的最大值和新的根节点}
end;
end;
temp:=value[i,i+d-1]+value[i+d,i+d];{计算以i+d为根节点，以i至i+d-1间所有节点为左子树的二叉树的最大加分}
if temp>s then begin
s:=temp;root[i,i+d]:=i+d+1;
end;
value[i,i+d]:=s;
end;
end;
writeln(f2,value[1,n]:0:0);{输出最大加分}
preorder(1,n);{输出最大加分二叉树的前序遍历序列}
close(f2);
end.
[点评]基本题。考查了二叉树的遍历和动态规划算法。难点在于要记录当前最大加分二叉树的根节点。疑点是最大加分二叉树的前序遍历序列可能不唯一。
题四
传染病控制
【问题背景】
近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国
大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完
全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，
蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过
WHO（世界卫
生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究
消楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。
【问题描述】
研究表明，这种传染病的传播具有两种很特殊的性质；
第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不
得病，或者是XY之间的传播途径被切断，则X就不会得病。
第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一
代患者，而不会再传播给下一代。
这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群
的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同
时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而
没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有
传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止
传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。
你的程序要针对给定的树，找出合适的切断顺序。
【输入格式】
输入格式的第一行是两个整数n（1≤n≤300）和p。接下来p行，每一行有两个整数i
和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。其中节点
1是已经被感染的患者。
【输出格式】
只有一行，输出总共被感染的人数。
【输入样例】
7
6
1
2
1
3
2
4
2
5
3
6
3
7
【输出样例】
3
[分析]本题关键是要找到切断传染途径的算法，这并不难。以测试数据Epidemic.in5为例说明如下：
在图1中，可以先切断1与2或者1与8或者1与16之间的任何一条途径，以先切断1与2为例，结果如下：
此时，1，8，16均已被感染，可将它们“合并”为一个新的节点，节点号取作8，如下图：
这样，它与图1十分相似，因此可用递归算法来做。
[PASCAL源程序]
program NOIP2003_4_Epidemic;
const
