当前位置:首页 >> 其它课程 >> 2012全国信息学奥林匹克联赛提高组第二天试题

2012全国信息学奥林匹克联赛提高组第二天试题


全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

NOIP2012复赛提高组第二天试题
(请选手务必仔细阅读本页内容) 一.题目概况
中文题目 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型
同余方程

r />
借教室 classroom classroom classroom.in classroom.out 1秒 20 5 有 传统

疫情控制 blockade blockade blockade.in blockade.out 2秒 20 10 有 传统

mod mod mod.in mod.out 1秒 10 10 有 传统

全文比较(过滤行末空格及文末回车)

二、提交源程序文件名
对于C++语言 对于 C 语言 对于pascal语言 mod.cpp mod.c mod.pas classroom.cpp classroom.c classroom.pas blockade.cpp blockade.c blockade r.pas

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

g++ -o classroom gcc -o classroom classroom .c -lm
fpc classroom.pas

g++ -o blockade gcc -o blockade blockade.c -lm
fpc blockade.pas

classroom.cpp -lm blockade .cpp -lm

四.运行内存限制 注意事项:

128M

128M

128M

1、 文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU Intel Core2 Quad Q8200 2.33GHz,内存 2G, 上述时限以此配置为准。 4、特别提醒:评测在 NOI Linux 下进行。
第 1 页 共 5 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

1. 同余方程
(mod.cpp/c/pas)

【问题描述】
求关于x的同余方程ax≡ 1 (mod b)的最小正整数解。

【输

入】

输入文件名为 mod.in。 输入只有一行,包含一个正整数a,b,用一个空格隔开。

【输

出】

输出文件名为 mod.out。 输出只有一行,包含一个正整数X0,即最小正整数解。输入数据保证一定有解。

【样

例】
mod.in mod.out 3 10 7

【数据说明】
对于40%的数据,2 ≤b≤1,000; 对于60%的数据,2 ≤b≤50,000,000; 对于100%的数据,2 ≤a, b≤2,000,000,000。

2.借教室
(classroom.cpp/c/pas)

【问题描述】
在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要 向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。 面对海量租借教室的信息,我们自然希望编程解决这个问题。 我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份订 单,每份订单用三个正整数描述,分别为dj,sj,tj,表示某租借者需要从第sj天到第tj天租借 教室(包括第sj天和第tj天) ,每天需要租借dj个教室。 我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提
第 2 页 共 5 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。 借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教 室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申 请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。 现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改 订单。

【输

入】

输入文件为 classroom.in。 第一行包含两个整数n,m,表示天数和订单的数量。 第二行包含n个正整数,其中个正整数,其中第i个数为ri,表示第i天可用于租借的教室 数量。 接下来有m行,每行包含三个正整数dj,sj,tj,表示租借的数量,租借开始、结束分别在 第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

【输

出】

输出文件名为 classroom.out。 如果所有订单均可满足,则输出只有一行,包含一个整数0。否则(订单无法完全满足) 输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。

【样

例】
classroom.in classroom.out
43 2543 213 324 424 -1 2

【样例说明】
第1份订单满足后,4天剩余的教室数分别为0,3,2,3。第2份订单要求第2天到第4天每 天提供3个教室,而第3天剩余的教室数为2,因此无法满足。分配停止,通知第2个申请人修 改订单。

【数据范围】
对于10%的数据,有1≤ n,m≤ 10; 对于30%的数据,有1≤ n,m≤1000;
第 3 页 共 5 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题
5

对于70%的数据,有1≤ n,m≤ 10 ; 对于100%的数据,有1≤n,m≤10 ,0≤ri,dj≤10 ,1≤sj≤tj≤n。
6 9

3.疫情控制 (blockade.cpp/c/pas)
【问题描述】
H国有n个城市,这n个城市用n-1条双向道路相互连通构成一棵树,1号城市是首都,也是 树中的根节点。 H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城 市(叶子节点所表示的城市) ,决定动用军队在一些城市建立检查点,使得从首都到边境城市 的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首 都是不能建立检查点的。 现在,在H国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可 以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个 城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道 路的长度(单位:小时) 。 请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。

【输

入】

输入文件blockade.in。 第一行一个整数n,表示城市个数。 接下来的n-1行,每行3个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u到城市v有一条长为w的道路。数据保证输入的是一棵树,且根节点编号为1。 接下来一行一个整数m,表示军队个数。 接下来一行m个整数,每两个整数之间用一个空格隔开,分别表示这m个军队所驻扎的城 市的编号。

【输

出】

输出文件名为blockade.out。 共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

【样

例】
blockade.in 4 121 132
第 4 页 共 5 页

blockade.out 3

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

343 2 22

【样例说明】
第一支军队在2号点设立检查点,第二支军队从2号点移动到3号点设立检查点,所需时间 为3个小时。

【数据范围】
保证军队不会驻扎在首都。 对于20%的数据,2≤n≤10; 对于40%的数据,2 ≤n≤50,0<w <10 ; 对于60%的数据,2 ≤n≤1000,0<w <10 ; 对于80%的数据,2 ≤n≤10,000; 对于100%的数据,2≤m≤n≤50,000,0<w <10 。
9 6 5

第 5 页

共 5 页


更多相关文档:

2012全国信息学奥林匹克联赛提高第一天试题

接下来n行,每行包含两个整数a和b,之间用一个空格隔开,分别表示每个大臣左手和右第 3 页共 7 页 全国信息学奥林匹克联赛(NOIP2012) 提高组第一天试题 手上...

...年第二十一届全国青少年信息学奥林匹克联赛提高组初...

2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C++)_学科竞赛_高中教育_教育专区。2015 年第二十一届全国青少年信息学 奥林匹克竞赛初赛 提高组一...

NOIP2015提高组复赛试题Day1

NOIP2015提高组复赛试题Day1_学科竞赛_高中教育_教育专区。NOIP2015提高组复赛试题Day1 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林...

NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛...

NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言试题_学科竞赛_高中教育_教育专区。NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言...

NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL)

NOIP2013信息学奥林匹克联赛初赛试题(提高组PASCAL)_学科竞赛_高中教育_教育专区。NOIP2013信息学奥赛全国联赛提高组Pascal第十九届全国青少年信息学奥林匹克联赛初赛提高...

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++...

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_...专题推荐 第十七届2011提高组初赛... 第十八届2012全国青少年......

NOIP2012提高组复赛试题_图文

第 1 页共 10 页 全国信息学奥林匹克联赛(NOIP2012)复赛 第二行包含 n 个正整数,其中第 i 个数为 ri,表示第 i 天可用于租借的教室数量。 提高组 day1...

CCF全国信息学奥林匹克联赛(NOIP2015)复赛普及组

【数据说明】第3页 共 7 页。 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 ...NOIP2015普及组复赛试题 5页 免费 NOIP2015提高组复赛试题... 6页 免费 NOIP...

2016第22届全国信息学奥林匹克联赛提高组复试二试真题_...

2016第22届全国信息学奥林匹克联赛提高组复试二试真题_IT认证_资格考试/认证_教育专区。2016 第 22 届全国信息学奥林匹克联赛提高组复试二试真题 2016 第 22 ...

第十五届信息学奥林匹克初赛试题详解

第十五届信息学奥林匹克初赛试题详解_学科竞赛_高中教育_教育专区。竞赛必看,...| 第十五届全国青少年信息学奥林匹克联赛初赛试题( 提高组 Pascal 语言 二小时...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com