NOIP2003提高组

《NOIP2003提高组》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九届全国青少年信息学奥林匹克联赛（N0IP2003）2003年11月29日提高组试题三小时完成题一神经网络【问题背景】人工神经网络（ArtificialNeuralNetwork）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。【问题描述】在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：神经元〔编号为1）图中

2、，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）CiWjiCjUi(j,i)E公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态

3、时，下一秒它会向其他神经元传送信号，信号的强度为Ci。如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。【输入格式】输入文件第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。【输出格式】输出文件包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格

4、分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！若输出层的神经元最后状态均为0，则输出NULL。【输入样例】561010010101131141151231241251【输出样例】314151题二侦探推理【问题描述】明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有N个人始终说假话，其余

5、的人始终说真。现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！【输入格式】输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。【输出格式】如果你的程序能确定谁是罪犯，则输出他的名

6、字；如果程序判断出不止一个人可能是罪犯，则输出CannotDetermine；如果程序判断出没有人可能成为罪犯，则输出Impossible。【输入样例】315MIKECHARLESKATEMIKE:Iamguilty.MIKE:TodayisSunday.CHARLES:MIKEisguilty．KATE:Iamguilty.KATE:Howareyou??【输出样例】MIKE题三加分二叉树【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每

7、个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree的前序遍历【输入格式】第1行：一个整数n（n＜30），为节点个数。第2行：n个用空格隔开的整数，为每