![NOIP2014复赛提高组模拟试题](https://img.doczj.com/img78/03m1ugangq9k0r7gm55a-81.webp)
NOIP2014复赛提高组模拟试题
- 格式:doc
- 大小:174.50 KB
- 文档页数:5
![NOIP2014复赛提高组模拟试题](https://img.doczj.com/img78/03m1ugangq9k0r7gm55a-81.webp)
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛
提高组 day1
(请选手务必仔细阅读本页内容)
一、题目概况
二、提交源程序文件名
三、编译命令(不包含优化开关)
注意事项:
1、文件名(程序名和输入输出文件名)必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+, 2.71GHz,内存 2G,上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、特别提醒:评测在 NOI Linux 下进行。
6、为了方便评测请以自己名字的拼音为文件夹名,而且将原程序直接保存在文件夹内,不用再新建子文件夹。
1.斐波那契
(pf.pas/c/cpp)
【问题描述】
是个斐波那契数迷。他是如此的酷爱这个数列,因此他想知道很多关于
这个数列的东西,比方说第个斐波那契数是多少啊、前项的和是多少啊如何用若干个斐波那契数的和表示一个自然数啊之类之类的。今天他希望知道的是:第个斐波那契数的末尾一位是多少?
记表示第个斐波那契数,
。
【输入】
输入文件名为pf.in,共行。
输入只有一个数。
【输出】
输出文件名为pf.out,仅一行,即第个数的最后一位。
【输入输出样例】
【数据说明】
对于3的数据满足,;
对于的数据满足,。
(toy.pas/c/cpp)
【问题描述】
一天小D去超市买回来了一个玩具,这个玩具是由n个球和一些支架组成,每一个支架连接着两个不同的球,通过支架每两个球之间的简单路径有且只有一条,如果某一个支架的两端的球全被拿走,那么这个玩具就会垮掉。小D无聊的时候开始拿走球,问,他有多少中拿球方案,使玩具不垮。
【输入】
输入文件名为toy.in。
第一行一个数n 表示球的个数
接下来若干行每行两个数a,b表示有一个支架连接着球a和球b
【输出】
输出文件名为toy.out.
一行一个数ans 表示DRJ拿球的方案数mod 109+7(可以一个球也不拿)
【输入输出样例】
【数据说明】
30%的数据满足n<=20;
50%的数据满足n<=1000
100%的数据满足 n<=500000;
(running.cpp/c/pas)
【问题描述】
某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。
为了让同学们更好地监督自己,学校推行了刷卡机制。
学校中有n个地点,用1到n的整数表示,每个地点设有若干个刷卡机,且两个地点之间有跑道相连接。
进行了一次长跑。问一个同学从A出发,最后到达B最多可以刷卡多少次。具体的要求如下:
当同学到达一个地点时,他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次,即使多次到达同一地点也不能多次刷卡。
为了安全起见,每条跑道都需要设定一个方向(每次询问相互独立),这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向,按照任意路径从A地点到B地点能刷卡的最多次数。
【输入格式】
输入文件名为running.in
第一行两个整数n,m,q表示n个地点和m条跑道有q组询问。
第二行n个数分别表示n个地点的刷卡机个数
然后m行每行两个数a b表示a b两地点之间有一条跑道
然后q行每行两个数A B表示询问从A到B的最多刷卡次数
【输出格式】
输出文件名为running.out
Q行,每行一个数表示最多刷卡次数
【输入输出样例】
【样例解释】
将图的边按如图所示的方法就可以走过所有的点【数据说明】
30%的数据满足n,m,q<=13
另20%的数据满足m=n-1, n,m,q<=10^5 100%的数据满足n,q<=10^5 m<=5*10^5
100%的数据满足图联通