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

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页


相关文章:
NOIP2013冲刺训练(第十五组)
NOIP2013冲刺训练(第十五组)NOIP2013冲刺训练(第十五组)隐藏>> [NOIP2013&NOI2014 省选]冲刺训练·提高组 2013 年 10 月 27 日 [NOIP2013&NOI2014 省选]冲...
NOIP2015冲刺训练(第三组)
[NOIP2015&NOI2016 省选]冲刺训练·提高组 2015 年 X 月 XX 日 [NOIP2015&NOI2016 省选]冲刺训练 [第三组] 测试时间:3.5 小时 【题目一览】 题号 题目...
第十四组实验一
第十四组实验一_教育学_高等教育_教育专区。实验成绩 批阅教师 日期 2016-6-...实验报告课程名称 专业班级 学 嵌入式系统 信息工程 2013 级 号 20121155018、...
第十四组实验六
第十四组实验六_其它课程_小学教育_教育专区。实验成绩 批阅教师 日期 2016-6-...实验报告课程名称嵌入式系统 专业班级信息工程 2013 级 学号 20121155018、...
第十四组实践
第十四组实践_实习总结_总结/汇报_实用文档。实验成绩 批阅教师 日期 2016-6-...2013 级 学号 20121155018、20121155017、20121155033 学生姓名钱思名闵金星杨磊 ...
NOIP2013普及组初赛模拟试题1(含答案)
NOIP2013普及组初赛模拟试题1(含答案)_财会/金融...传送能量 14、下列描述计算机病毒的特性中, ( )不...第 2 题第 3 空不算分) 1、输入正整数 n(n...
第十四组实验二
第十四组实验二_教学案例/设计_教学研究_教育专区。实验成绩 批阅教师 日期 ...2013 级 号 20121155018、20121155017、20121155033 钱思名 闵金星 苗晟 杨磊 ...
第十四组案例
第十四组案例第十四组案例隐藏>> 第十四组案例马新宇 ( 2005 年 06 月 05 日) 商标权案例 案例二十九:侵犯“十佳”商标权案 申请再审人(原审原告、被上诉...
NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案
NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案_学科竞赛_高中教育_...1 2 3 4 5 6 7 8 A A B D A B D B 9 10 11 12 13 14 15 D...
更多相关标签:
noip冲刺 | noip 训练方案 | 斗鸡十四种训练法视频 | 间歇性冲刺训练 | 冲刺跑训练 | 四级冲刺训练营 | 冲刺训练 | noip2016 |