求题:谁有最近五年的复赛题目 [复制链接]

谁有最近五年的复赛题目啊,麻烦发上来

老师从DRS抄的
Because 中间有一些错误 只有DRS上的有这些错误 并且错法一模一样！

但绝对不是临时抄的！！！
这是老师给的！！！

是吗？

从DRS抄的

OK，五年的都在！！

第六届分区联赛提高组复赛

第六届全国青少年信息学（计算机）奥林匹克分区联赛提高组复赛试题
2000年12月2日
提高组复赛试题（三小时完成）
题一 进制转换 (18分)
问题描述:
我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所
处位置的（值减1）为指数，以10为底数的幂之和的形式。例如，123可表示为1*10^2+2*10^1
+3*10^0这样的形式。
与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位
置的（值-1）为指数，以2为底数的幂之和的形式。一般说来，任何一个正整数R或一
个负整数-R都可以被选来作为一个数制系统的基数。如果是以R或-R为基数，则需要
用到的数码为0，1,....R-1。例如，当R=7时，所需用到的数码是0，1，2,
3，4，5和6，这与其是R或-R无关。如果作为基数的数绝对值超过10，则为了表
示这些数码，通常使用英文字母来表示那些大于9的数码。例如对16进制数来说，用A
表示10，用B表示11，用C表示12，用D表示13，用E表示14，用F表示15。
在负进制数中是用-R作为基数，例如-15（＋进制）相当于110001（-2进制），
并且它可以被表示为2的幂级数的和数：
110001=1*(-2)^5+1*(-2)^4+0*(-2)^3+0*(-2)^2+
0*(-2)^1+1*(-2)^0
问题求解:
设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负
进制下的数：-R∈{-2，-3，-4,....-20}
输入:
输入的每行有两个输入数据。
第一个是十进制数N（-32768<=N<=32767）; 第二个是负进制数的基数-R。
输出:
结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过10，
则参照16进制的方式处理。
样例:
输入
30000 -2
-20000 -7
28800 -16
-25000 -16
输出
30000=1101101010111000(base -2)
-20000=1111011000100000(base -2)
28800=19180(base -16)
-25000=7FB8(base -16)

题二 乘积最大 (22分)
问题描述:
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先
生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活
动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样
一道题目:
设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种
分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串: 312，当N=3，K=1时会有以下两种分法：

1）3*12=36
2）31*2=62
这时，符合题目要求的结果是： 31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入：
程序的输入共有两行:
第一行共有2个自然数N,K (6<=N<=40，1<=K<=6)
第二行是一个K度为N的数字串。
输出:
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
样例:
输入
4 2
1231
输出
62

题三 单词接龙 (27分)
问题描述：
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们己知一组单词，且
给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙" 中
出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果
接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间
不能相连。
输入:
输入的第一行为一个单独的整数n(n<=20）表示单词数，以下n行每行有一个单词，输
入的最后一行为一个单个字符，表来“龙”开头的字母。你可以假定以此字母开头的“龙"
一定存在。
输出:
只需输出以此字母开头的最长的“龙”的长度
样例:
输入
5
at
touch
cheat
choose
tact
a
输出
23 （连成的“龙”为atoucheatactactouchoose）

题四 方格取数 (33分)
问题描述:
设有N*N的方格图(N<=8)，我们将其中的某些方格中填入正整数，而其他的方格中则放
人数字0。如下图所示（见样例）：
某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B
点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入:
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个
表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出:
只需输出一个整数，表示2条路径上取得的最大的和。
样例:
输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出
67

2001年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组 竞赛用时：3小时）
题一 一元三次方程求解（20分）问题描述有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*(x2)<0，则在(x1，x2)之间一定有一个 根。样例输入：1   -5   -4   20输出：-2.00   2.00   5.00　
题二 数的划分(20分)问题描述将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。输入：n，k (6<n<=200，2<=k<=6)输出：一个整数，即不同的分法。样例输入： 7 3输出：4 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}
题三 统计单词个数(30分)问题描述给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。输入格式去部输入数据放在文本文件input3.dat中，其格式如下：第一行为一个正整数(0<n<=5)表示有n组测试数据每组的第一行有二个正整数(p，k)p表示字串的行数;
k表示分为k个部分。接下来的p行，每行均有20个字符。再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)接下来的s行，每行均有一个单词。输出格式结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。样例输入： 11 3thisisabookyouareaoh4isaoksab输出： //说明：(不必输出)7 // this/isabookyoua/reaoh题四 Car的旅行路线(30分) 问题描述又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图例      机场 高速铁路飞机航线　 注意：图中并没有标出所有的铁路与航线。
那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。任务找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。输入文件：键盘输入文件名输 出：到屏幕(输出最小费用，小数点后保留1位。)输入格式第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。每组的第一行有四个正整数s，t，A，B。S(0<S<=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，B<=S)。接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。输出格式共有n行，每行一个数据对应测试数据。 样例输入11 10 1 31 1 1 3 3 1 302 5 7 4 5 2 18 6 8 8 11 6 3输出：47.55　

2002年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（提高组 竞赛用时：3 小时）
题一 均分纸牌（存盘名 NOIPG1）
[问题描述]
　　有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。
　　移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
　　现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

　　例如 N=4，4 堆纸牌数分别为：
　　①　9　②　8　③　17　④　6
　　移动3次可达到目的：
　　从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。
[输 入]：
　　键盘输入文件名。文件格式：
　　N（N 堆纸牌，1 <= N <= 100）
　　A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
[输 出]：
　　输出至屏幕。格式为：
　　所有堆均达到相等时的最少移动次数。‘
[输入输出样例]
a.in：
　4
　9 8 17 6

屏慕显示：
　3
题二 字串变换 （存盘名: NOIPG2）
[问题描述]:
　　已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
　　　　　A1$ -> B1$
　　　　　A2$ -> B2$
　　规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。
　　　　例如：A$＝'abcd'　B$＝'xyz'
　　变换规则为：
　　　　‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’

　　则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
　　　‘abcd’->‘xud’->‘xy’->‘xyz’

　　共进行了三次变换，使得 A$ 变换为B$。
[输入]:
　　键盘输人文件名。文件格式如下：
　　　A$ B$
　　　A1$ B1$ \
　　　A2$ B2$ |-> 变换规则
　　　... ... /
　　所有字符串长度的上限为 20。
[输出]:
　　输出至屏幕。格式如下：
　　若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出"NO ANSWER!"
[输入输出样例]
b.in:
　abcd wyz
　abc xu
　ud y
　y yz

屏幕显示：
　3
题三 自由落体（存盘名:NOIPG3）
[问题描述]:
　　在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，…．n-1。在地面上有一个小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d＝1/2*g*(t^2)，其中 g=10，t 为下落时间。地面上的小车以速度 V 前进。

　　如下图：


　　小车与所有小球同时开始运动，当小球距小车的距离 <= 0.00001 时，即认为小球被小车接受（小球落到地面后不能被接受）。

　　请你计算出小车能接受到多少个小球。
[输入]：
　　键盘输人：
　　H，S1，V，L，K，n （l<=H，S1，V，L，K，n <=100000）
[输出]：
　　屏幕输出：
　　小车能接受到的小球个数。
[输入输出样例]
　[输入]:
　　　5.0 9.0 5.0 2.5 1.8 5
　[输出]:
　　　1
题四 矩形覆盖（存盘名NOIPG4）
[问题描述]:
　　在平面上有 n 个点（n <= 50），每个点用一对整数坐标表示。例如：当 n＝4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7），见图一。


　　这些点可以用 k 个矩形（1<=k<=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。
[输入]:
　　键盘输人文件名。文件格式为
　　　n k
　　　xl y1
　　　x2 y2
　　　... ...
　　　xn yn （0<=xi,yi<=500)
[输出]:
　　输出至屏幕。格式为：
　　一个整数，即满足条件的最小的矩形面积之和。
[输入输出样例]
d.in :
　4 2
　1 1
　2 2
　3 6
　0 7

屏幕显示：
4

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

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

兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）


  公式中的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个人始终说假话，其余的人始终说真。
现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

【输入格式】
  输入由若干行组成，第一行有二个整数，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