- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
NOIP2012提高组复赛试题选编
CCF全国信息学奥林匹克联赛(NmP2012)复赛提高组day2
2. 1 ·同余方程
〖问题描述〗
求关于的同余方程三1 (mod句的最小正整数解。
输入〗
输入文件为mod.ino
输入只有一行,包含两个正整数用一个空格隔开
输出〗
输出文件为mod.outo
输出只有一行,包含一个正整数№即最小正整数解。输入数据保证一定有解。
〖输入输出样例〗
mod. in
mod.out
3 10
7
〖数据范围〗
对于40%的数据,2 L000:对于60%的数据,2 50,000,000:
对于100%的数据,2,2,000,000,000。
2 ·借教室 (classroom. cpp/c/pas)
问题描述〗
在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。
面对海量租借教室的信息,我们自然希望编程解决这个问题。
我们需要处理接下来n天的借教室信息,其中第i天学校有个教室可供租借。共有m份订单,每份订单用三个正整数描述,分别为d],斗t},表示某租借者需要从第丬天到第t]天租借教室(包括第丬天和第t)天),每天需要租借dj个教室。
我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供d]个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。
借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第丬天到第t)天中有至少一天剩余的教室数量不足d)个。现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改
输入〗
输入文件为classroom.in
第一行包含两个正整数n,m,表示天数和订单的数量。
第二行包含n个正整数,其中第i个数为ri,表示第i天可用于租借的教室数量。
接下来有m行,每行包含三个正整数dJ,s],t],表示租借的数量,租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。
〖输出〗
输出文件为classroom.outo
如果所有订单均可满足,则输出只有一行,包含一个整数0。否则(订单无法完全满足)输出两行,第一行输出一个负整数一1 ,第二行输出需要修改订单的申请人编号。
〖输入输出样例〗
01 ssroom.in
classroom. 00t
2 5 4 3
2 1 3
3 2 4
4 2 4
2
输入输出样例说明〗
第1份订单满足后,4天剩余的教室数分别为0,3,2,3。第2份订单要求第2天到第4天每天提供3个教室,而第3天剩余的教室数为2,因此无法满足。分配停止,通知第
2个申请人修改订单。
〖数据范围〗
对于10%的数据,有1孓n,m孓10;对于30%的数据,有1孓n,m孓1000;对于70%的数据,有1孓n,m孓105;
对于100%的数据,有1孓n,m孓106,0孓ri,dj孓109,1 sj tj no
3 ·疫情控制 (blockade.cpp/c/pas
〖问题描述〗
H国有n个城市,这n个城市用n-l条双向道路相互连通构成一棵树,1号城市是首都,也是树中的根节点。
H国的首都爆发了一种危害性极高的传染病。当局为了控制疫清,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。
现在,在H国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军
队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。
请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。
〖输入〗
输入文件名为blockade . ino 第一行一个整数n,表示城市个数。
接下来的n.1行,每行3个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市u到城市v有一条长为w的道路。数据保证输入的是一棵树,且根节点编号为1。
接下来一行一个整数m,表示军队个数。
接下来一行m个整数,每两个整数之间用一个空格隔开,分别表示这m个军队所驻扎的城市的编号。
〖输出〗
输出文件为b工ockade.outo
共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出.1。
〖输入输出样例〗
b工o c kade.i n
blockade . out
4
1 2 1
1 3
您可能关注的文档
- New_concept_Book1_005-008选编.ppt
- NC63全产品培训课件-协同平台表单、权限、门户选编.pptx
- NetArtistGNIC全网智能中心解决方案选编.pptx
- newsreport每日个人演讲选编.pptx
- NC63全产品培训-项目物资、预算控制、项目合同选编.pptx
- NICU护理安全管理选编.ppt
- nexus6p解锁教程选编.docx
- new11.计量与投药设备选编.ppt
- NEW2012Money,BankingandFinancialMarkets-1选编.ppt
- NFV技术研究_NFV产业链动态选编.pptx
- 中国国家标准 GB/T 22517.2-2024体育场地使用要求及检验方法 第2部分:游泳场地.pdf
- GB/T 22517.2-2024体育场地使用要求及检验方法 第2部分:游泳场地.pdf
- 《GB/T 22517.2-2024体育场地使用要求及检验方法 第2部分:游泳场地》.pdf
- 苏教版(2017秋)科学三年级下册1.《种子发芽了》 教案(含课堂练习和反思).docx
- 2024-2025学年小学数学六年级上册冀教版(2024)教学设计合集.docx
- 地理商务星球版七年级上册4.5形成气候的主要因素 同步教案.docx
- 2024-2025学年中职中职专业课金融类73 财经商贸大类教学设计合集.docx
- 2024-2025学年初中地理七年级上册(2024)仁爱科普版(2024)教学设计合集.docx
- 2024-2025学年小学英语二年级上册外研版(一起)教学设计合集.docx
- 2024-2025学年高中数学选择性必修 第二册北师大版(2019)教学设计合集.docx
文档评论(0)