tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

温州中学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 以 上。


推荐相关:

温州中学noip二试模拟

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


2006年届湖南省江华一中高三年级第一次考试模拟试题

温州中学noip二试模拟 4页 免费 高三英语模拟试题(二) 15页 免费 12“五五”普法基本知识 9页 免费 高考数学复习填空题系列训... 2页 2财富值 2006年南川中...


CCF NOIP2011复赛提高组部分选手成绩公示

二中学 学军中学 温州中学 学军中学 余姚中学 绍兴一中 镇海中学 镇海中学 温州中学 衢州二中 温岭中学 温州二中(黄龙校区) 绍兴一中 杭州第二中学 镇海中学 ...


信息学竞赛题库

试试 7 帮助 全部 DOC PPT TXT PDF XLS ...2,部分 NOIP 初赛选择题(基础知识) http://bbs....(14)温州中学:http://wzioi.wzms.com/usaco/ ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com