nbhkdz.com冰点文库

noip2003提高组题目


第九届全国青少年信息学奥林匹克联赛(N0IP2003)
2003 年 11 月 29 日 提高组试题 三小时完成

题一

神经网络

【问题背景】 人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算 系统,在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应

用。对神经网络的研究 一直是当今的热门方向, 兰兰同学在自学了一本神经网络的入门书籍后, 提出了一个简化模 型,他希望你能帮助他用程序检验这个神经网络模型的实用性。 【问题描述】 在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经 元之间至多有一条边相连,下图是一个神经元的例子:

神经元〔编号为 1) 图中,X1—X3 是信息输入渠道,Y1-Y2 是信息输出渠道,C1 表示神经元目前的状态, Ui 是阈值,可视为神经元的一个内在参数。 神经元按一定的顺序排列,构成整个神经网络。在兰兰的模型之中,神经网络中的神 经无分为几层;称为输入层、输出层,和若干个中间层。每层神经元只向下一层的神经元 输出信息,只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定,Ci 服从公式: (其中 n 是网络中所有神经元的数目)

Ci ?

?

W ji C j ? U i

( j , i )? E

公式中的 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

题二

侦探推理

【问题描述】 明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学 玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明 明不知情的情况下) ,明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被

询问者可能会说:

证词中出现的其他话,都不列入逻辑推理的内容。 明明所知道的是,他的同学中有 N 个人始终说假话,其余的人始终说真。 现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一 个! 【输入格式】 输入由若干行组成, 第一行有二个整数,(1≤M≤20) N M 、(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

题三
【问题描述】

加分二叉树

设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n) ,其中数字 1,2,3,…,n 为 节点编号。每个节点都有一个分数(均为正整数) ,记第 j 个节点的分数为 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

题四

传染病控制

【问题背景】 近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国 大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完 全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是, 蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 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


NOIP2003 提高组试题

NOIP2003 提高组试题_其它考试_资格考试/认证_教育专区。历届NOIP试题第九届全国青少年信息学奥林匹克联赛( 第九届全国青少年信息学奥林匹克联赛( N0IP2003 ) 2003...

NoiP2003提高组复赛试题分析

NoiP2003提高组复赛试题分析_IT/计算机_专业资料。NoiP2003提高组复赛试题分析第一题:神经网络 第一题:【试题分析】 试题分析】 一、题意分析 1、任务描述:从输入...

NOIP2003提高组初赛试题

NOIP2003提高组初赛试题_其它考试_资格考试/认证_教育专区。NOIP2003提高组第九届分区联赛提高组初赛试题 (提高组 PASCAL 语言 二小时完成) ●● 全部答案均要写在...

Noip 2003 提高组 解题报告1

Noip 2003 提高组 解题报告1_IT/计算机_专业资料。03Noip 2003 提高组 解题报告题一 分析: 这一题有很多种方法,数据也较弱。我考虑到其中的层次关系,用类似于...

NOIP2003提高组初赛答案

NOIP2003提高组NOIP2003提高组隐藏>> 第九届分区提高组官方参考解答 一,单选 10 题 每题 1.5 分 B B D A B B C E C B 二,不定项选择 10 题 每题...

NOIP2003第九届初赛提高组P

2003 年第九届 NOIP 初赛试题(提高组) 第九届分区联赛提高组初赛试题●● (提高组 PASCAL 语言 二小时完成) 全部答案均要写在答案卷子上,写在试卷纸上一律...

NOIP2002 提高组试题

NOIP2002 提高组试题_其它考试_资格考试/认证_教育专区。历届NOIP试题2002...NOIP2002 普及组试题 NOIP2003 提高组试题 NOIP2003 普及组试题 NOIP2004 提高组...

NOIP2004提高组解题报告

NOIP2004提高组解题报告_其它课程_高中教育_教育专区。Noip2004 解题报告 一、津...2003提高组,解题报告 15页 免费 NOIP2004提高组复赛试题 6页 免费喜欢...

NOIP2002提高组初赛试题答案

NOIP2003普及组初赛试题答... 10页 8财富值 NOIP2007年提高组(Pascal语... 10页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点...

NOIP提高组复赛题目

NOIP提高组复赛题目_学科竞赛_高中教育_教育专区。第一题题库 NOIP2007 1.统计...NOIP 2003 题三 加分二叉树 【问题描述】 设一个 n 个节点的二叉树 tree ...