当前位置:首页 >> 互联网 >>

NOIP2003提高组


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

题一
【问题背景】

神经网络

人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算 系统,在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究 一直是当今的热门方向, 兰兰同学在自学了一本神经网络的入门书籍后, 提出了一个简化模 型,他希望你能帮助他用程序检验这个神经网络模型的实用性。 【问题描述】 在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经 元之间至多有一条边相连,下图是一个神经元的例子:

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

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

?W

ji

Cj ? Ui

公式中的 Wji(可能为负值)表示连接 j 号神经元和 i 号神经元的边的权值。当 Ci 大 于 0 时,该神经元处于兴奋状态,否则就处于平静状态。当神经元处于兴奋状态时,下一秒

它会向其他神经元传送信号,信号的强度为 Ci。 如此.在输入层神经元被激发之后,整个网络系统就在信息传输的推动下进行运作。 现在,给定一个神经网络,及当前输入层神经元的状态(Ci) ,要求你的程序运算出最后网 络输出层的状态。 【输入格式】 输入文件第一行是两个整数 n(1≤n≤20)和 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 0 1 1 1 1 3 1 4 1

1 5 1 2 3 1 2 4 1 2 5 1 【输出样例】 3 1 4 1 5 1

题二
【问题描述】

侦探推理

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

证词中出现的其他话,都不列入逻辑推理的内容。 明明所知道的是,他的同学中有 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

题三
【问题描述】

加分二叉树

设一个 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提高组.pdf
NOIP2003提高组_互联网_IT/计算机_专业资料。第九届全国青少年信息学奥
noip2003提高组题目.doc
noip2003提高组题目 - 第九届全国青少年信息学奥林匹克联赛(N0IP20
NOIP2003提高组初赛答案.doc
NOIP2003提高组NOIP2003提高组隐藏>> 第九届分区提高
NOIP2003第九届初赛提高组P.doc
NOIP2003第九届初赛提高组P_IT认证_资格考试/认证_教育专区。NOIP试题 2003 年第九届 NOIP 初赛试题(提高组) 第九届分区联赛提高组初赛试题●● (提高组 ...
NOIP2003第九届初赛提高组P.doc
NOIP2003第九届初赛提高组P_IT认证_资格考试/认证_教育专区。NOIP试题 2003 年第九届 NOIP 初赛试题(提高组) 第九届分区联赛提高组初赛试题(提高组 PASCAL 语言...
NOIP2002提高组初赛试题答案.doc
NOIP2003普及组初赛试题答... 10页 8财富值 NOIP2007年提高组(Pascal语... 10页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点...
NoiP2003提高组复赛试题分析_天津南开中学滕伟.doc
Noip 2003 提高组 解题报... 12页 免费 NOIP2003解题报告
2003年第九届noip初赛试题 提高组.doc
2003年第九届noip初赛试题 提高组_英语考试_外语学习_教育专区。2003 年第九届 NOIP 初赛试题(提高组)发布日期: 2006-01-22 访问总次数: 4240 第九届分区联赛...
历年NOIP(普及组提高组)试题分析_图文.doc
历年NOIP(普及组提高组)试题分析 - 历年 NOIP(普及组)难度分析 年份
NOIP提高组初赛试题汇编(2002-2009).doc
NOIP提高组初赛试题汇编(2002-2009)_其它考试_资格考试/认证_教育专区。收录02-...Edsger Wybe Dijkstra 十进制数 2003 等值于二进制数( A) 0100000111 B) 100000...
NOIP2003普及组乒乓球.txt
NOIP2003普及组乒乓球 - 背景 Background 国际乒联现在主
NOIP2000提高组初赛试题答案.doc
NOIP2003提高组初赛试题 8页 免费 NOIP2001普及组初赛试题和..
NOIP01提高组初赛试题附解答.doc
NOIP2003提高组初赛答案 1页 免费 第七届全国青少年信息学奥... 9页
NOIP2003普及组(复赛).doc
NOIP2003普及组(复赛) - NOIP2003 普及组复赛试题 题一、乒乓
历年NOIP(普及组提高组)试题难度列表.doc
历年NOIP(普及组提高组)试题难度列表_图片/文字技巧_PPT制作技巧_PPT专区。历年...2003 2004 2005 2006 2007 2008 2009 考查内容 枚举 高精度运算 数学(进制...
NOIP2003普及组复赛试题.doc
NOIP2003普及组复赛试题_初一数学_数学_初中教育_教育专区。NOIP2003普及组NOIP...NOIP1995普及组复赛数据 NOIP1995普及组复赛试题 NOIP1995提高组初赛试题 NOIP1995...
NOIP提高组复赛题目_图文.doc
NOIP提高组复赛题目 - 第一题题库 NOIP2007 1.统计数字 (cou
NOIP2003获奖名单.doc
NOIP2003获奖名单_IT认证_资格考试/认证_教育专区。NOIP2003获奖名单福建...NOIP2003提高组初赛答案 1页 免费 NOIP2003复赛普及组 5页 免费 noip2003讲稿 ...
NOIP 提高组 05年 11届.doc
NOIP 提高组 05年 11届_学科竞赛_高中教育_教育专区。NOIP 05 年提高组试题...(k - 1) + 2003 * g(k - 2)) mod 2005; end; begin read(n); ...
NOIP2003普及组复赛试题.doc
NOIP2003普及组复赛试题 - NOIP2003 普及组复赛试题 题一、乒乓
更多相关标签: