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


Noip 2003 提高组 解题报告1

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

NOIP2002提高组初赛试题答案

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

NOIP2000提高组初赛试题答案

NOIP2003提高组初赛试题 8页 免费 NOIP2001普及组初赛试题和... 7页 免费 NOIP2000普及组初赛试题 8页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能...

NOIP2005提高组初赛试题答案

NOIP2005提高组初赛试题及... 7页 免费 NOIP2003普及组初赛试题答... 10页 8财富值 NOIP2007普及组初赛试题答... 9页 8财富值如要投诉违规内容,请到百度文库...

NOIP2002-2005解题报告

noip2005普及组解题报告 10页 免费 NOIP2005提高组解题报告 4页 免费 noip2005...二、NOIP2003 题一:神经网络(Network) 【问题描述】人工神经网络(Artificial ...

蓝桥杯部分练习代码文档

试题名称 矩阵翻硬币 兰顿蚂蚁 分糖果 小朋友排队 波动数列 斐波那契 地宫取宝 ...NOIP2003 提高组搜索 简单计算 语言 指针 语言 指针 算法 普通计算 算法 枚举 ...

组合数学例题推荐

noip 2003 ——PZY 1.容斥原理 ural 1091 Tmutarakan 简单利用容斥原理基本公式...母函数 例题: 1. 整数的拆分(Noip2001 提高组第二题) 二.排列组合 1. ...

加分二叉树解题报告

2014.8.19 加分二叉树【NOIP2003 提高组】 Description 设一个 n 个节点的...应届生求职季宝典 英文个人简历模板 创意简历模板汇集 推理型题分析与总结文档...

4种常见的动态规划模型

区间模型的动态规划, 在历届的信息学竞赛, 应用非常广泛, noi95 的石子合并问题, 如 noip2003 普及组的数字游戏,noip2006 提高组第 1 题等。 (四)树型动态...

信息学奥赛——树型动态规划的实例分析

{$N+} program NOIP2003_3_Tree; const maxn=30; var i,j,n,d:byte; ...学奥林匹克联赛(N0IP2003)复赛提高组解题报告. Ural 1018 二*苹果树 题目 有...