当前位置:首页 >> 学科竞赛 >>

NOIP2013冲刺训练(第十四组)


2013 年 NOIP 冲刺模拟试题

提高组

全国信息学奥林匹克联赛(NOIP2013)复赛模拟

提高组第二试
2013 年 10 月 20 日 8:30-12:00
(要求每道题建立子文件夹并把程序放入子文件夹中)
一、题目概况 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 题目类型 二、提交源程序文件名 对于 pascal 语言 对于 C 语言 对于 C++语言 dragons.pas dragons.c dragons.cpp rect.pas rect.c rect.cpp gcd.pas gcd.c gcd.cpp 剑与魔法 dragons dragons dragons.in dragons.out 1秒 10 10 有 传统 矩形 rect rect rect.in rect.out 1秒 20 5 有 传统 数列的 GCD gcd gcd gcd.in gcd.out 1秒 10 10 有 传统

三、编译命令(不包含任何优化开关) 对于 pascal 语言 对于 C 语言 fpc dragons.pas gcc –o dragons dragons.c -lm g++ -o dragons dragons.cpp -lm fpc rect.pas gcc –o rect rect.c -lm g++ -o rect rect.cpp -lm fpc gcd.pas gcc –o gcd gcd.c -lm g++ -o gcd gcd.cpp -lm

对于 C++语言

四、运行内存限制 内存上限 128M 128M 128M

五、注意事项 1、 文件名(程序名和输入输出文件名)必须使用小写。 2、 C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、 全国统一评测时采用的机器配置为:CPU 1.9GHz,内存 1G,上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。

第 1页

2013 年 NOIP 冲刺模拟试题

提高组

1.剑与魔法
(dragons.pas/c/cpp)
【问题描述】 万老师听说某大国很流行穿越,于是他就想写一个关于穿越的剧本。 闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般,所以老师从维娜 艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类:战役 事件(CASE) 、穿越回去事件(END) 。战役事件可以选择是否参加,参加了之后会获得一定 的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是,END事件如果满足 要求就会强制发生。老师希望在大陆玩个够,所以他要求只有最后一个END事件会发生。老 师希望获得最多的金钱,所以求助于你。 【输入】 第一行一个数N,表示输入文件有多少行。 接下来每一行用空格隔开一个字符和一个整数。字符为“c”表示战役事件,接下来的 整数表示这次涨RP顺带有多少钱;字符为“e”表示穿越回去事件,接下来的整数代表至少 要涨多少RP。最后一个事件保证是END事件。 【输出】 第一行一个整数,最多金钱数目。 若不可能则输出-1。 【输入输出样例】 dragons.in 5 c 10 c 12 e 2 c 1 e 2 【数据说明】 30%的数据满足 N<=20 60%的数据满足 N<=1,000 100%的数据满足 N<=200,000 每次涨RP事件赏金不超过10,000 穿越事件的要求不超过200,000 dragons.out 13

第 2页

2013 年 NOIP 冲刺模拟试题

提高组

2.矩形
(rect.pas/c/cpp)
【问题描述】 因为对polo忍无可忍, dzf使用圣剑在地上划出了许多纵横交错的沟壑来泄愤。 这些沟 壑都严格与X轴平行或垂直。 polo嘲笑了dzf无聊的行为, 然后做了一件更加无聊的事。 他蹲下来数这些沟壑的条数。 数着数着,polo意识到一个问题,那就是因为圣剑的威力太大,划出的沟壑太多,地面就会 塌陷。 而如果两条水平的沟壑和两条垂直的沟壑相交组成了一个矩形, 那么塌陷的危险就会 进一步增加。现在polo已经数了n条沟壑,他想知道这些沟壑组成了多少个矩形。 【输入】 第一行一个数n,接下来每行4个数x1,y1,x2,y2,表示沟壑的两个端点(x1,y1),(x2,y2)

【输出】
一个数,组成的矩形个数。 【输入输出样例1】 rect.in 4 0 0 1 1 0 0 1 1 1 0 1 0 0 1 -1 1 rect.out 6 0 1 0 2 3 3 1 2 4 0 2 0 0 3 2 3 3 -1 4 3 -1 1 -1 2 rect.out 1

【输入输出样例2】 rect.in 8 1 2 0 2 3 0 4 3

【数据说明】 对于30%的数据,1<=n<=100 对于60%的数据,1<=n<=600 对于100%的数据, 1<=n<=2000,坐标绝对值小于10^9, 任意两条与X轴水平的沟壑之间没 有交点,任意两条与X轴垂直的沟壑没有交点。

第 3页

2013 年 NOIP 冲刺模拟试题

提高组

3.数列的 GCD
(gcd.pas/c/cpp)
【问题描述】 给出一个长度为N的数列{a[n]},1<=a[i]<=M(1<=i<=N)。 现在问题是,对于1到M的每个整数d,有多少个不同的数列b[1], b[2], ..., b[N], 满 足: (1)1<=b[i]<=M(1<=i<=N); (2)gcd(b[1], b[2], ..., b[N])=d; (3)恰好有K个位置i使得a[i]<>b[i](1<=i<=N) 注:gcd(x1,x2,...,xn)为x1, x2, ..., xn的最大公约数。 输出答案对1,000,000,007取模的值。 【输入】 第一行包含3个整数,N,M,K。 第二行包含N个整数:a[1], a[2], ..., a[N]。 【输出】 输出 M 个整数到一行,第 i 个整数为当 d=i 时满足条件的不同数列{b[n]}的数目 mod 1,000,000,007 的值。 【输入输出样例 1】 gcd.in 3 3 3 3 3 3 【输入输出样例 2】 gcd.in 3 5 3 1 2 3 gcd.out 59 3 0 1 1 gcd.out 7 1 0

【样例 1 解释】 当 d=1,{b[n]}可以为:(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1)。 当 d=2,{b[n]}可以为:(2, 2, 2)。 当 d=3,因为{b[n]}必须要有 k 个数与{a[n]}不同,所以{b[n]}不能为(3, 3, 3),满 足条件的一个都没有。 【数据说明】 对于 30%的数据,1<=N<=20, 1<=M<=2。 对于 50%的数据,1<=N,M<=1000。 对于 70%的数据,1<=N,M<=10000。 对于 100%的数据,1<=N,M<=300000, 1<=K<=N, 1<=a[i]<=M。

第 4页


相关文章:
2009年5月初三数学第十四周教研活动综述
(天河中学) 一、 会议概况 距离中考只剩下 30 多天,如何在最后冲刺时刻中做...进行以下变式图形的训练; D 第 23 题组题组长钟杏钰(东圃中学)从学生的解答...
2009年5月初三数学第十四周教研活动综述
(天河中学) 一、 会议概况 距离中考只剩下 30 多天,如何在最后冲刺时刻中做...进行以下变式图形的训练; D 第 23 题组题组长钟杏钰(东圃中学)从学生的解答...
高中历史清华北大实验班冲刺训练2
高中历史清华北大实验班冲刺训练2_政史地_高中教育_...法国国王路易十四发出这样的感叹: “中国科举制度是...西周时期出现了我国第一次城市建设高潮,并确立了...
2013历史高考冲刺押题小题训练(选择题)8
2013 历史高考冲刺押题小题训练(选择题)8 1. 《史记·平准书》记载: “杜周...第二个峰值是在 1990 年至 1993 年出现,在 1992 年召开了中共十四大,提出了...
【广东省某重点中学2013届高三数学理高考冲刺之基础训...
月收入情况调查后画出的样本频率分布直方 图,已知图甲中从左向右第一组的频数...求 a 的值 2 2013 届高三冲刺复习 基础训练六暨十四周一数学小测 2013-5-...
中国现代史近代史专题训练(教师版) 2
冲刺2013中考历史二轮复... 35页 1下载券 中国近代...沿海十四个港口城市的开放 【答案】 :D 【解析】 ...参与人类基因组图谱绘制 ( ) 解析:A 本题考查“...
九年级物理练习(7)
九年级物理第十四练习 8页 免费九​年​级​...24嫦娥三号于2013年12月2日凌晨1时30分从西昌卫星...同 米/秒;乙同学最后冲刺的平均速度为 九年级物理...
4单元训练题曲线运动、万有引力定律(四)
14单元训练题光学(十四) 15单元训练题原子和原子核...艺考生文化课百日冲刺 英语... 22页 免费 2012艺术...则根据下列哪一组数据可以估算 出该黑洞的质量(万...
大腿积极前摆技术在短跑中的重要作用及训练
例如,一定角度的扶墙后蹬跑 15 秒一组、 90%~...跳绳、跨步过栏、上坡冲刺 等来进行强化力量练习。 ...文档贡献者 xiaolaoh2012 贡献于2013-12-06 ...
2014年物理中考复习方案_2014.2.14
2014年物理中考复习方案_2014.2.14_中考_初中教育_...加强对学生实验能力的培养,加强实验思想和方法的训练...第四轮中考模拟冲刺阶段(6.3---6.17) 第四轮复习的...
更多相关标签: