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

代码长度限制: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模拟试题2

绵阳中学 NOIP 模拟试题 地震了!(earthquake) 模拟赛背景:2008 年 5 月 12 ...第二个需安慰的同学 2 5 3 4 4 3 5 2 对所有数据 N<100,M<=500; ...


学军中学NOIP2013提高组原创模拟题解

学军中学NOIP2013提高组原创模拟题解_其它课程_高中教育_教育专区。学军中学NOIP2013提高组原创模拟题解(每试3.5小时) DAY1 1.装果子关键词:二分二分V,然后...


学军中学NOIP2013提高组原创模拟题day2

学军中学NOIP2013提高组原创模拟题day2_IT/计算机_专业资料。学军中学noip模拟题 学军中学 NOIP2013 提高组原创模拟题 day2 测试时间:3.5 小时 中文题目名称 ...


初赛复习题_NOIP_江苏省南通中学信息学奥林匹克联赛初赛

一台计算机如果要利用电话线上网,就必须配置能够对数字信号和模拟信号进行相互转 ...二十六中信息学奥林匹克联赛初赛系列练习 覃荣幸编辑整理 22 南通中学 NOIP ...


2010年NOIP第二次模拟赛

NOIP2010初赛练习(5) 8页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 2010年NOIP第二次模拟赛 绝对对的!...


关于参加《NOIP2016全国青少年信息学(计算机)奥林区克...

关于参加《NOIP2016全国青少年信息学(计算机)奥林区克...除动员普通中学的学生参赛外,还应积极组织各中等技术...模拟法 4.贪心法 5.简单搜索算法(深度优先 广度...


浙江省西店中学NOIP初赛练习题之四(完善程序题)

浙江省西店中学NOIP初赛练习题之四(完善程序题)_中考_初中教育_教育专区。浙江...OIM 地形 (2003 高中组第二题) [题目描述]: 二维离散世界有一种地形叫 OIM...


绵阳中学NOIP练习题1

绵阳中学NOIP搜索测试报... 绵阳中学NOIP动态规划基... 绵阳中学NOIP模拟试题2...题目名称: gather 输入格式 * 第一行:一个整数 N * 第二到 N+1 行:第 ...


NOIP普及组初赛模拟试题四

NOIP普及组初赛模拟试题四_英语考试_外语学习_教育...二进制数 01100100 转换成十六进制数是( A.32 A....光明中学开设数学、英语和信息学三个兴趣学习小组,其中...


杭州学军中学NOIP2011模拟赛DAY2-2011-10-5

NOIP2011 模拟赛 By 杭州学军中学中文题目名称 题目名 时间限制 空间限制 最大公约数 gcd.pas/c/cpp 1s 256M 序列游戏 game.pas/c/cpp 1s 256M 纪念品 s...

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