省选、noi正式比赛oj数据相关1试题day

1、IOI 2007 中国国家队选拔赛CTSC 2007竞赛时间：2007 年 5 月 14 日上 午 8:15-13:15提交源程序须加后缀注意：最终测试时，所有编译命令均不打开任何优化开关第 1 页 共 8 页对于 Pascal 语言matrix.paspendant.pasN/A对于 C语言matrix.cpendant.cN/A对于 C+语言matrix.cpppendant.cppN/A题目名称矩阵挂缀激光目录matrixpendant可执行文件名matrixpendant输入文件名matrix.inpendant.1.10.out输出文件名matrix.outpendant.out1.

2、out10.out每个测试点时限3s4sN/A测试点数目101010每个测试点分值101010是否有部分分有有有题目类型传统传统提交矩阵【问题描述】给定一个整数 D，n 行 m 列的实数矩阵 A，其第 i 行第 j 列的元素是 aij，且 0 D (1in, 1jm）。 希望你能够由此提供一个 n 行 m 列的 01 矩阵B，第 i 行第 j 列的元素是 bij(1in, 1jm），bij 非 0 即 1。对于给定的 A 矩阵和你提供的 B 矩阵，可以求出aijmax)naij1 jm(bDij i1p max ；1mamax(b ) ijDij1inj1 b (ai, j ai1, j ai

3、, j1 ai1, j1 )p bbbmaxD i, ji1, ji, j1i1, j121in,1 jm在不同的测试例子中，希望提供的 B 矩阵能使 p1 或者 p2 尽量小。【输入文件】输入文件 matrix.in 第一行有一个整数 c，有两种取值：c = 1 表示化目标是 p1，c = 2 则表示希望 p2 尽量小。的最小第二行有 3 个整数 D, n, m，相邻的两个数字间用一个空格隔开，D 的含义如上文所述，n 和 m 分别表示 A 矩阵的行数和列数。以下有 n 行，每行 m 个实数，描述 A 矩阵。其中第 i 行第 j 列的实数表示 aij，相邻的数字用一个空格隔开。【输出文件】输

4、出文件 matrix.out 中仅包含一个 n 行 m 列的 01 矩阵 B，表示你求出的使pc 尽量小的隔开。其中第 i 行第 j 列的数字表示 bij。相邻的整数之间用一个空格【样例输入 1】32 5 1 5第 2 页 共 8 页【样例输出 1】0 1 0 11 0 1 00 1 0 1【样例输入 2】27 3 45【样例输出 2】0 1 0 11 0 1 00 1 0 1【样例说明】在样例 1 中 p1 = 37 0.4286，而在样例 2 中，p2 = 57 0.7143。【评分标准】如果你的程序输出点你的得分为 0。否则（不是一个合法的 n 行 m 列的 01 矩阵），则在该测试计算

5、出和你的程序输出相对应的 pc，设 Total 是测试点的总分，而你在该点的得分是 YourScore。YourScore Roundmax1.5 max p1,1, 0* 2 *Total若 c = 1，有YourScore Roundmax2 max p2 ,1.5, 0* 2 *Total若 c = 2，有其中 Roundx表示距离 x 最近的整数（即四舍五入）。【数据规模】100%的数据中，2 n, m 700，1 D 1 000 000 000；40%的数据中，c = 1；60%的数据中，c = 2。第 3 页 共 8 页挂缀【问题描述】“珠缀花蕊，人间几多酸泪”挂缀在很早就们作为一

6、种装饰品，垂坠的风韵，华丽摇曳的摆动，展现出一种与众不同的优雅与高贵。而在寝室里作为装饰。的主人公小 Q，正想买一条漂亮的挂缀放挂坠的，是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成：分别是珠子、珠子上方的连接环与珠子下方的挂钩（如下图）。可以简单的认为从上往下数的第 i 个缀珠是将它的连接环套在其上方（也就是第 i-1 个）缀珠的挂钩之上（第一个除外）。小 Q 想买一根足够长的挂缀，这样显得更有韵味然而商店的 告诉小 Q，挂缀是不可能做到任意长的，因为每一个珠子都受到重力作用，对其上方的挂钩有一定的拉力，而挂钩的承受能力是有限的。老板还告诉小 Q，他一共拥有 N 个珠缀（假设每一个珠缀都

7、很漂亮，小 Q 都很喜欢），每个珠缀都有其各自的重量与承受能力。一个挂缀是稳定的，当且仅当对于其上的每一个珠缀，它下方所有珠缀的重量和（不包含自身）不超过其挂钩的承受能力。小 Q 希望挂缀尽量长，你能帮她计算出最长可能的稳定挂缀么？当然，如果有多个可选方案，小 Q 希望总重量最小的。【输入文件】输入文件 pendant.in 第一行包含一个正整数 N，表示商店拥有的珠缀数目。接下来 N 行，每行两个整数(Ci , Wi)，分别表示第 i 个珠缀的承受能力与重量。【输出文件】输出文件 pendant.out 包行两行。第一行包含一个整数 L，表示可以找到的最长稳定挂缀长度。第二行包含一个整数 W

8、，表示可以找到的长度为 L 的稳定挂缀中的最小重量和。第 4 页 共 8 页【样例输入】43 55 13 24 6【样例输出】38【评分标准】每一个测试点单独评分，对于每一个测试点：如果挂缀长度 L 与如果挂缀长度 L 与试点则得 4 分。否则得 0 分。一致，且最小重量和 W 也正确，则得 10 分。一致，而最小重量和 W 与不一致，该测【数据规模】对于 30%的数据，N 10000； 对于 100%的数据，N 200000；对于所有的数据，Wi, Ci 不超过 231。第 5 页 共 8 页激光【问题描述】小朋友最近迷上一款 PC 上的益智小，名叫激光。有些关卡实在是太难了，他在鏖战了若干

9、个小时之后，决定来请教作为编程高手的你。希望你能帮他写一个程序来通关。原太复杂，你在这里只需要解决简化了的版本。在的战场上（可以的大小相对于整个物，每个都可以看看作一个平面），有 N 个敌方的，可以认为单个战场很小，是一个点。同时战场上还有 M 个栅栏一样的作是一条线段，这些线段不会相交，也不会有公共端点。你的任务自然是要摧毁所有的敌方激光，而你手上所拥有的就是一个激光。可以放置在战场的任何位置（但不能放置在物所在的线段上），一旦放置之后就不能再移动。它可以向任何方向发射激光，激光沿直线运动，不能横穿栅栏（但是可以紧贴着栅栏经过）。当激光碰到栅栏的时候会发生反射，此时可以把栅栏看作镜子，反射规

10、则和镜面反射相同。经过一次反射的效果特殊情况：紧贴栅栏而过任何被激光打到（即在激光的运动路径上）的敌方都会被立即摧毁，我们称从发射源开始，沿着这条激光运动直到目标的路径为激光路径。但激光在每次被栅栏反射的时候都会有能量的衰减，如果被反射的次数超过 K 次，激光就不会再具有摧毁敌方的能力了。现在希望你能够找到一个合适的位置安放激光来摧毁所有的坦克，并且设计摧毁每个敌方需要的激光方向。同时，他希望在满足摧毁所有敌方的前提下，最长的激光路径长度尽量短，因为才能拿到比较高的通关分数。本题是提交式题目，分为10 个测试数据，分别1.10.in，在选手不需要提交程序，只需要针对每个数据给出相应的输出文件，

11、 1.out10.out 即可。【输入文件】每个输入文件第一行包含两个实数 C1，C2。它们仅仅参与该测试点的分数计第 6 页 共 8 页算，与题目本身无关。第二行包含三个整数，分别为 N、M 和 K。他们的意义已经在题目中说明了接下来 N 行，每行两个实数 Xi，Yi，表示每个敌方标值。i 的 X 坐标值和 Y 坐随后的 M 行，每行四个实数 X1i，Y1i，X2i，Y2i。表示每条栅栏个端点的坐标。物的两【输出文件】输出文件第一行为 Ans，表示最长的激光路径的长度。第二行为两个实数 AnsX，AnsY。表示激光源摆放的位置。以下 N 行，每行两个实数 Sxi，Syi。表示为了摧毁敌方i，

12、需要从激光源发出一条射向点(Sxi, Syi)的直线。即激光的方向为(AnsX,AnsY)(Sxi,Syi)，要求输出点(AnsX, AnsY)与点(Sxi, Syi)的距离要超过 0.1。【样例输入】1 2 2 1-4 -44 01 1 1 -1-2 2 4 2【样例输出】5.65690 0-4 -42 2（上面的例子中，两条路径长度都是）【评分标准】每个数据的满分是 10 分。对于每个数据，如果出现下列情况，则程序得 0 分：没有输出文件输出不合法3有敌方没有被摧毁，即给出的不是可行解。否则你的得分将按照下面的公式计算：第 7 页 共 8 页Ans Best Ans C2 BestC2 Ans Best Ans10Score C1(Best C Ans) (10 C ) C21 1(1 C ) Ans2【调试工具】本题提供了一个检测程序（check）来帮助选手调试，具体使用方法是：./check XX 表示测试点的，为 110。如果你的输出文件给出的Your output is correct正确，你会得到如下信息：with striking distance Ans, givenhe file!Ans 是你的输出中给出的。如果你的错误，会得到这样的信息：Your output is not correct!The