温州中学noip二试模拟

1、4温州中学NOIP2011模拟赛DAY2题目基因光线好朋友砍树题目名称lightfrien dscut输入文件light.i nfrien ds.i ncut.in输出文件light.outfrien ds.outcut.out时间限制1s1s3s空间限制64MB64MB64MB每个测试点分值101010代码长度限制：50KB评测机配置为Celeron(R) CPU2.66GHz , 1G的内存(古董机，速度你懂的)。为了评测及整理方便起见，文件夹名请使用学校名-选手名”的格式，里面需要使用子文件。基因光线【题目描述】黑大帅统治古古怪界后，一直在玩一种很奇葩的游戏。在一个二维平面上，他先复制了

2、 n个小A，把他们放在不同的位置，然后射出一条ax+by+c=0的基因光线，宽度为 d,即离 TOC o 1-5 h z 这条直线的距离不大于 d的小A会被射中。当然，某些悲剧的小 A就会被射中，并变成黑 小A。当然，这不是重点。玩了很久后，黑大帅猛然发现，自己竟然一次都没有射中小A。黑大帅怒了，于是他开启了作弊模式， 将c改成自己想要的任意数值。 现在，黑大帅想知道， 在开启了作弊模式后，他射出一道基因光线最多能击中几个小A。【输入说明】第一行五个数字a， b，d，n，接下来n行每行两个数字x，y表示这个小A的坐标。【输出说明】一行一个数字表示最多能击中几个小A。【样例输入】-1 0.707

3、106782 50 000 101【样例输出】【样例说明】将c值改为0或-1可以击中4个小A，可以证明不可能同时击中5个小A。数据范围】50%的数据满足 a=0;100%的数据满足 *=100000,其余所有数值均为绝对值不大于1000的实数。好朋友【题目描述】noip2011 就要来了, W 校的同学们不仅看重这次比赛,更看重 noip2011 和谁住在同一 个房间。同学之间的关系好坏可以用一个亲密值表示,亲密值越大,两个同学关系越好。小 A 作为 W 校信息组的组长,自然想要让同学们在比赛前能好好休息,放松心情,让同学们 在赛场上能够超常发挥。 他现在知道自己预订的房间都是双人间, 且知道

4、这 n 个同学之间的 关系。n个同学的关系可以用一个 n条双向边的连通图来描述，即某个同学只愿意和与他有 边相连的同学住同一个房间,边权即为两个同学的亲密值。数据保证没有重边、自环。现在小A想知道在让所有同学的要求满足的情况下，亲密值最低的一对同学亲密值最高是多少。【输入说明】第一行一个正整数 n，下面n行每行三个数u，v，w，表示u到v有一条边权为 w的双 向边。【输出说明】假如无论如何都无法满足所有同学的要求，输出”no answer”否则输出亲密值最低的一对同学的最高亲密值。【样例输入】41 2 32 3 104 31 4 1【样例输出】3【样例解释】有两种选择。一种选择是 、，最低亲密

5、值为 3；另一种选择是 、 ， 最低亲密值为 1 。所以最高的最低亲密值为 3。【数据范围】50%的数据满足 n=20；80%的数据满足 n=1000；100% 的数据满足 *=100000，-10A9=w=10A9砍树【题目描述】小A是小B家的园丁。小B的家里有n棵树，第i棵树的横坐标为i。一天，小B交给 小A 一个任务，让他降低自己家中的某些树木的高度。这个任务对小A来说十分简单，因为他有一把极其锋利的斧头和一门独门砍树秘籍，能够轻易地砍断任何参天大树。小A的砍树方法有3种，都是沿着一条 y=kx+b的直线砍一段区间的树，相同的方法k值相同。只用了一个下午，小 A就完成了小B的任务。第二天

6、，小 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 -1410 30 20 124 2 51 3 3 1085如右图，红色即为树的剩余部分。【样例说明】【数据范围】数据组数nmq1-210005001000350000200001450000