当前位置:首页 >> 其它课程 >> NOIP2003提高组复赛试题

NOIP2003提高组复赛试题


第九届全国青少年信息学奥林匹克联赛(N0IP2003) 第九届全国青少年信息学奥林匹克联赛(N0IP2003)
2003 年 11 月 29 日 提高组试题 试题输入:苏州高斌 大榕树 http://drs.126.com 三小时完成

题一

神经网络

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

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

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

Ci =

( j,i )∈E

∑W C
ji

j

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 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

赞助商链接
更多相关文档:

Noip 2003 提高组 解题报告1

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

2003noip提高组

1999-2009NOIP提高组复赛试... 32页 免费 NOIP2003解题报告 10页 2财富值 NOIP...题四 传染病控制(Epidemic.pas/cpp) 传染病控制(Epidemic.pas/cpp) 1 秒 ...

NOIP2003提高组初赛答案

NoiP2003提高组复赛试题分... 14页 10财富值 noip2003提高组题目 暂无评价 5...NOIP2003提高组NOIP2003提高组隐藏>> 第九届分区提高组官方参考解答 一,单选 10...

NOIP提高组初赛试题汇编附答案

NOIP实用算法 33页 免费 NOIP+提高组复赛试题汇编(... 32页 免费 2007年及之...十进制数 2003 等值于二进制数( )。 A) 0100000111 B) 10000011 C) ...

历年NOIP(普及组提高组)试题难度列表

2003 2004 2005 2006 2007 2008 2009 考查内容 枚举 高精度运算 数学(进制...NOIP 提高组复赛考察点详细分析题目编号 NOIP-2000-A NOIP-2000-B NOIP-2000-...

NOIP2003第九届初赛提高组P

NoiP2003提高组复赛试题分... 14页 10财富值 noip2003提高组题目 暂无评价 5页 免费 NOIP2003)第九届全国青少年... 8页 5财富值 NOIP2003第九届普及组试题....

NOIP2002提高组初赛试题答案

NOIP2003提高组初赛答案 1页 免费 NOIP2005提高组初赛试题及... 7页 免费 NOIP...(提高组 PASCAL 语言 二小时完成) 审定:全国青少年信息学奥林匹克竞赛科学委员会...

noip2003

noip2003_建筑/土木_工程科技_专业资料。noip2003的试题,有提高组的,也有普及组的,欢迎大家下载!!NOIP2003 普及组复赛试题 题一、乒乓球(Table.pas) 【问题背景...

NOIP提高组初赛试题汇编(2002-2009)

NOIP+提高组复赛试题汇编(... 32页 免费 NOIP实用算法 33页 免费 NOIP复赛冲刺...Edsger Wybe Dijkstra 十进制数 2003 等值于二进制数( A) 0100000111 B) 1000...

NOIP提高组初赛试题汇编(2002-2011)(1)

NOIP提高组初赛试题汇编(2002-2011)(1)_IT认证_资格...(k - 1) + 2003 * g(k - 2)) mod 2005;...在下列各软件中,属于 NOIP竞赛(复赛)推荐使用的语言...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com