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

温州中学noip二试模拟


温州中学 NOIP2011 模拟赛 DAY2
题目 题目名称 输入文件 输出文件 时间限制 空间限制 每个测试点分值 基因光线 light light.in light.out 1s 64MB 10 好朋友 friends friends.in friends.out 1s 64MB 10 砍树 cut cut.in cut.out 3s 64MB 10

r />代码长度限制:50KB 评测机配置为Celeron(R) CPU2.66GHz,1G的内存(古董机,速度你懂的)。 为了评测及整理方便起见, 文件夹名请使用"学校名-选手名"的格式, 里面需要使用子文件。

基因光线
【题目描述】
黑大帅统治古古怪界后,一直在玩一种很奇葩的游戏。在一个二维平面上,他先复制了 n 个小 A,把他们放在不同的位置,然后射出一条 ax+by+c=0 的基因光线,宽度为 d,即离 这条直线的距离不大于 d 的小 A 会被射中。当然,某些悲剧的小 A 就会被射中,并变成黑 小 A。当然,这不是重点。玩了很久后,黑大帅猛然发现,自己竟然一次都没有射中小 A。 黑大帅怒了, 于是他开启了作弊模式, c 改成自己想要的任意数值。 将 现在, 黑大帅想知道, 在开启了作弊模式后,他射出一道基因光线最多能击中几个小 A。

【输入说明】
第一行五个数字 a,b,d,n,接下来 n 行每行两个数字 x,y 表示这个小 A 的坐标。

【输出说明】
一行一个数字表示最多能击中几个小 A。

【样例输入】
1 -1 0.707106782 5 00 10 01 20 21

【样例输出】
4

【样例说明】
将 c 值改为 0 或-1 可以击中 4 个小 A,可以证明不可能同时击中 5 个小 A。

【数据范围】
50%的数据满足 a=0; 100%的数据满足 n<=100000,其余所有数值均为绝对值不大于 1000 的实数。

好朋友
【题目描述】
noip2011 就要来了,W 校的同学们不仅看重这次比赛,更看重 noip2011 和谁住在同一 个房间。同学之间的关系好坏可以用一个亲密值表示,亲密值越大,两个同学关系越好。小 A 作为 W 校信息组的组长,自然想要让同学们在比赛前能好好休息,放松心情,让同学们 在赛场上能够超常发挥。 他现在知道自己预订的房间都是双人间, 且知道这 n 个同学之间的 关系。n 个同学的关系可以用一个 n 条双向边的连通图来描述,即某个同学只愿意和与他有 边相连的同学住同一个房间,边权即为两个同学的亲密值。数据保证没有重边、自环。现在 小 A 想知道在让所有同学的要求满足的情况下,亲密值最低的一对同学亲密值最高是多少。

【输入说明】
第一行一个正整数 n,下面 n 行每行三个数 u,v,w,表示 u 到 v 有一条边权为 w 的双 向边。

【输出说明】
假如无论如何都无法满足所有同学的要求, 输出”no answer”, 否则输出亲密值最低的一 对同学的最高亲密值。

【样例输入】
4 123 2 3 10 343 141

【样例输出】
3

【样例解释】
有两种选择。一种选择是<1,2>、<3,4>,最低亲密值为 3;另一种选择是<1,4>、<2,3>, 最低亲密值为 1。所以最高的最低亲密值为 3。

【数据范围】
50%的数据满足 n<=20; 80%的数据满足 n<=1000; 100%的数据满足 n<=100000,-10^9<=w<=10^9

砍树
【题目描述】
小 A 是小 B 家的园丁。小 B 的家里有 n 棵树,第 i 棵树的横坐标为 i。一天,小 B 交给 小 A 一个任务,让他降低自己家中的某些树木的高度。这个任务对小 A 来说十分简单,因 为他有一把极其锋利的斧头和一门独门砍树秘籍,能够轻易地砍断任何参天大树。小 A 的 砍树方法有 3 种,都是沿着一条 y=kx+b 的直线砍一段区间的树,相同的方法 k 值相同。只 用了一个下午,小 A 就完成了小 B 的任务。第二天,小 B 来视察小 A 的任务完成情况。小 B 想知道小 A 是否真的用心砍树,于是提出了 q 个询问,每次询问一段区间中最低的树的 高度。小 A 当然是不会记住树木的砍伐情况的,他只知道自己按什么顺序,使用了什么方 法,砍了哪个连续区间的树,而且区间都是互不包含的。现在小 A 想请你帮帮他,回答小 B 的询问。

【输入说明】
第一行三个整数 k1,k2,k3 表示小 A 三种砍树方法的斜率值; 第二行一个数 n,表示一共有 n 棵树; 第三行 n 个数 hi,分别表示 n 棵树的高度; 第四行一个数 m,表示小 A 一共进行了 m 次操作; 接下来 m 行,每行四个数 L,R,p,b,表示用第 p 种方法,即用 y=kp+b 的直线砍[L, R]区间的树; 接下来一行一个数 q,表示小 B 的询问数; 接下来 q 行,每行两个数 L,R,表示询问[L,R]区间中最低的树的高度。

【输出说明】
一共 q 行,每行一个数 h 表示对应的回答。

【样例输入】
1 0 -1 4 10 30 20 1 2 3425 1 3 3 10 2 12 23

【样例输出】
8 5

【样例说明】
如右图,红色即为树的剩余部分。

【数据范围】
数据组数 1-2 3 4 5-6 7-10 n 1000 50000 50000 50000 1000000 m 500 20000 1 30000 500000 q 1000 1 50000 50000 500000

所有数据保证 0<hi<=10^8,abs(ki)<=1000,0<bi<=10^8,所有砍树线段均在直线 y=0 以 上。


相关文章:
20151024区NOIP模拟测试题目
注意:是每 3 本书都可以打包,你不能尝 2 2015 年 NOIP 普及组南海区模拟赛(一) 试着把 4 本书放在一起打包,也不能把 2 本书放在一起打包。 【输入...
2014noip复赛模拟练习21(附答案)
试试 7 帮助 全部 DOC PPT TXT PDF XLS ...2014noip复赛模拟练习21(附答案)_学科竞赛_初中教育...二十一届全国中学生生物学竞赛将在马鞍山市第二中学...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育...2.背单词(words) 源程序名:words.pas/c/cpp ...他很想把 n 边形的编号复原,可是试了一天也没弄...
CCF全国信息学奥林匹克联赛(NOIP2016)模拟赛
试试 7 帮助 全部 DOC PPT TXT PDF XLS ...CCF全国信息学奥林匹克联赛(NOIP2016)模拟赛_计算机...第 2 页共 5 页 全国信息学奥林匹克联赛(NOIP...
NOIP2014 提高组模拟试题(一试)
NOIP2014 提高组模拟试题(一试)_学科竞赛_高中教育_教育专区。1. 宿舍 (a.cpp...【输入】 输入文件名为 a.in 输入共 2 行 第一行为两个整数 n,m ,表示...
NOIP复赛模拟试题2
N​O​I​P​复​赛​模​拟​试​题​2 暂无评价|0人阅读|0次下载|举报文档2013 开明中学 NOIP 模拟试题 2 题目 1、NBA 总冠军(nba....
NOIP复赛模拟题
Noip2006 复赛模拟NOIP2006 复赛模拟题(普及组水平) (时间:3 小时)注意事项: 1. 严格按照题目所要求的格式进行输入、输出。 2. 题目测试数据有严格的时间,...
NOIP复赛模拟题2
NOIP复赛模拟2_IT/计算机_专业资料。NOIP复赛模拟2NOIP 复赛测试题 3 1、神牛果(cow.cpp) 神牛果(cow.cpp) 【题目描述】 在某次膜拜大会上,一些神牛被要...
兴业中学模拟试
会昌中学高二下学期期中... 5页 2下载券 温州中学noip二试模拟 4页 免费 民...2012 年兴业中学物理摸拟试一、单项选择(本大题共 14 小题,42 分) 单项选择...
2014noip复赛模拟练习22(附答案)
试试 7 帮助 全部 DOC PPT TXT PDF XLS ...2014noip复赛模拟练习22(附答案)_学科竞赛_初中教育...【样例输入】 ACDEF ABCDE 【样例输出】 2 【分析...
更多相关标签:
noip模拟赛 | noip 资料 雅礼中学 | noip模拟题 | noip普及组模拟题 | noip初赛模拟题 | 温州中小学云图书馆 | 温州中学 | 温州市中小学云图书馆 |