顶级选手IOI2006选拔第

1、IOI2006 选拔 第一试5 月 11 日题目一览OverviewIOI2006 中国队选拔赛第一试竞赛时间：2006 年 5 月 11 日上午 8:15-13:15第 1 页 共 7 页题目名称歌唱王国寻找盆地拼图英文代号singlandbasinjigsaw可执行文件名singlandbasinjigsaw输入文件名singland.injigsaw.in输出文件名singland.outjigsaw.out每个测试点时限3 秒3 秒1 秒测试点数目101010每个测试点分值101010附加文件无basin_libjigsaw_c题目类型传统交互传统IOI2006 选拔 第一试5 月 1

2、1 日歌唱王国singland歌唱王国singland【问题描述】在歌唱王国，所有人的名字都是一个非空的仅包含整数 1n 的字符串。王国里生活着一大群咕噜兵，他们靠不停的歌唱首领牛人酋长们的名字来获取力量。咕噜兵每一次歌唱过程是这样的：首先，他从整数那儿获得一个数字，然后花一个时间将此数字唱出来，如果他发现某个牛人酋长的名字已经被歌唱出来（即此名字是歌唱序列的续子串），那么这次歌唱过程就立即结束。相关名词定义歌唱序列：如果唱序列=(a1,a2,ax)。歌唱了 x 个数i 次歌唱的数字为 ai，那么歌整数：歌唱王国的神物，它有一个按钮，如果你按一下按钮，将从 1n 数字中等概率的随机返回一个整数

3、。歌唱时间：在一次歌唱过程中花费的时间。歌唱时间是随机的，无法预料；不过歌唱时间的期望值是固定的，此期望值即平均来说歌唱时间有多长，亦可称作平均歌唱时间。王国里的人非常喜欢歌唱，他们希望歌唱的时间越长越好，所以他们决定罢免一些牛人酋长，使得平均歌唱时间变长。但是他们不能掉所有的牛人酋长，否则他们每次歌唱都无法停止，无法获取力量；于是他们决定只保留一个牛人酋长而其余的牛人酋长。你的任务是：对于给定的 n、牛人酋长的个数 t 以及每一个牛人酋长的名字，告诉王国里的人们，对于 1it，如果保留第 i 个牛人酋长， 么平均歌唱时间将是多少。提示：此数为一个非负整数！掉其余的，那输出要求：由于这个数字太

4、大，所以你只需输出这个数的末 4 位数字。如果不足 4 位，则前面补 0(见样例)。【输入文件】第一行，两个整数 n、t；以下 t 行描述 t 个牛人酋长名字。文件第 i+1(1it)行格式如下第一个数为 mi 表示第 i 个牛人酋长的名字的长度，在一个空格之后，接下来有 mi 个数，这个牛人酋长的名字，相邻两个整数之间用一个空格。【输出文件】共 t 行，第 i 行为一个整数，表示若保留第 i 个牛人酋长而其余的，则平第 2 页 共 7 页IOI2006 选拔 第一试5 月 11 日歌唱王国singland均歌唱时间最长的末四位数字是多少。【约定】1n105，t50，1mi105。有 30%的

5、数据满足 n103，mi103有 50%的数据满足 n104，mi104【样例】样例 1： 输入：2 21 13 1 2 1输出：00020010解释：保留第 1 个牛人酋长其余酋长时，一次歌唱结束时可能的歌唱序列为："1","2,1","2,2,1","2,2,2,1",，它们的概率分别为 1/2,1/4,1/8,1/16,，歌唱时间为 1,2,3,4,。不难证明å i = 2 。2ii³1保留第 2 个牛人酋长其余酋长时，平均歌唱时间为 10。样例 2： 输入：26 16 1 2 3 1 2

6、 3输出：3352解释：平均歌唱时间为 308933352。第 3 页 共 7 页IOI2006 选拔 第一试5 月 11 日寻找盆地basin寻找盆地basin【问题描述】五一节到了，为了摆脱紧张且繁忙的学习生活，寻找久违的刺激，小强打算和朋友们去城探险。城是一个边长为 n 的正方形区域，被人为地划分成了 n*n 块小区域，每块小区域都是一个正方形。为了方便起见，我们定义第i 行第 j 列的小区域坐标为(i, j)。我们称两块小区域(x1, y1)和(x2, y2)相邻，当且仅当它们有一条公共边，即|x1 y1|+|x2 y2|=1。每块小区域都有一个海拔高度（用实数表示），不同的小区域高度

7、不同。小强想在这 n*n 块小区域中找到一块盆地，即一块比相邻小区域海拔都低的小区域。城被一圈很高的围墙包围，所以盆地可以出现在边上，此时它只需比相邻的三块小区域海拔低；盆地甚至可以出现在角上，此时它只需比相邻的两块小区域海拔低。城处有一个地形系统，每次可以输入两块不同的小区域，系统会告诉你谁的海拔高。由于一块盆地，你能帮他设计速度很慢，小强想用尽量少的询问次数找到案吗？【交互方法】本题是一道交互式题目，你的程序应当和测试库进行交互，而不得文件（包括临时文件）。测试库提供了若干函数，它们的用法和作用如下：任何¾¾¾init 必须先调用，但只能调用一次，用作初始化测

8、试库。get_n 的作用是返回城的边长 n。query(x1, y1, x2, y2)的作用是询问小区域(x1, y1)和(x2, y2)的相对高低。如果(x1, y1)比(x2, y2)高，则返回 1，否则返回-1。answer(x, y)的作用是向测试库报告结果，(x, y)表示你找到的盆地的坐标。当这个函数被调用后，测试库会自动中止你的程序。¾【对使用 Pascal 选手的提示】你的程序应当使用如下的语句测试库。uses basin_lib_p;测试库使用的函数原型为：procedure init;function get_n: longint;function query(x

9、1, y1, x2, y2: longint): longint; procedure answer(x, y: longint);【对使用 C/C+选手的提示】你应当建立一个工程，把文件 basin_lib_c.o 包含进来，然后在程序头加一行：#include “basin_lib_c.h”测试库使用的函数原型为：void init();第 4 页 共 7 页IOI2006 选拔 第一试5 月 11 日寻找盆地basinint get_n();int query(int,int, int, int);void answer(int, int);【你如何测试的程序】¾在工作目录下建

10、立一个文件叫做 basin.in，文件的第一行包括一个整数 n 为城的边长。接下来的 n 行，每行 n 个实数，表示每个小区域的海拔高度。执行你的程序，此时测试库会产生输出文件 basin.log，该文件中包括了你程¾序和库交互的和最后的结果。¾¾¾如果程序正常结束，basin.log 的最后一行包含一个整数，为你的次数。，则我们不保证 basin.log 中的内容有意义。如果程序正式测试时，测试库会自行生成地形，并使得每次回答尽量对你不利。【约定】Ø 2 n 63【样例】basin.in 内容如下一种可能得满分的调用方案如下：注意，该例子只是

11、对库函数的使用说明，并没有算法上的意义。【评分方法】如果你的程序有下列情况之一，该测试点 0 分：¾¾¾¾了任何文件(包括临时文件)或者自行终止； 调用库函数；让测试库异常。次数超过 200 次。否则，该测试点满分。第 5 页 共 7 页Pascal 选手的调用方法C/C+选手的调用方法说明init;init();初始化程序query(3,3,2,3);query(3,3,2,3);返回 1query(3,3,3,2);query(3,3,3,2);返回-1query(2,3,2,2);query(2,3,2,2);返回 1query(1,3,2,3);

12、query(1,3,2,3);返回 1query(1,2,2,2);query(1,2,2,2);返回-1query(2,1,2,2);query(2,1,2,2);返回 1query(1,2,1,1);query(1,2,1,1);返回-1query(1,3,1,2);query(1,3,1,2);返回 1answer(1,2);answer(1,2);(1,2)确实是盆地，共8 次39.1 1.2 7.35.4 2.5 3.66.7 8.8 4.9IOI2006 选拔 第一试5 月 11 日拼图jigsaw拼图jigsaw【问题描述】5 岁的小 P 对剪纸很感，他总是喜欢把一个矩形的纸片剪

13、成一个又一个的凸多边形。但是，每一次剪完后，他总是怀疑弄丢了一些纸片。聪明的他想到了一个方法来检测纸片是否弄丢：他将这些凸多边形拼起来，如果能够拼成一个矩形，他就认为纸片没有弄丢。由于纸片的数量不是很多，这个工作并不难。但是，久而久之，他对这项工作不感了，所以，他找到了你，希望你能够告诉他，这些凸多边形纸片能不能够拼成矩形。【输入文件】第一行只有一个正整数 n（1n8），表示凸多边形的个数。以下 n 行每一行描述一个凸多边形，格式如下：第 i+1 行的第一个数 mi（3mi8）表示凸多边形的点数，接下来有 mi 对实数，一对实数给出了一个点的坐标，这 mi 个顶点按照从任意一个顶点出发的逆时针

14、顺序给出。且所有实数都在(-1000,1000)的范围内，小数点后不超过 8 位。【输出文件】如果不能拼成矩形，输出只有一行“No”。如果能拼成矩形，输出的第一行为“Yes”。接下来的 n 行描述拼法。如果能够拼成一个 X*Y 的矩形，那么矩形的四个顶点的坐标是(0,0)、(0,Y)、(X,Y)、(X,0)。这 n 行输出每一个凸多边形的顶点的坐标（拼成矩形后）。按照输入的顺序，即第一个输出的凸多边形对应输入的第一个凸多边形。对于每一个凸多边形，输出也按照输入的顺序，即一个多边形的第一个顶点对应输入的第一个顶点。这样，输出总共有 n 行，第 i 行有 mi 对数。【输入样例】34 0 0 4 -1 5 4 0 44 0 0 5 -1 8 3 0 34 0 0 0 -8 3 -4 4 0【输出样例】Yes0 4 4 3 5 8 0 85 8 4 3 8 0 8 80 0 8 0 4 3 0 4【样例说明】第 6 页 共 7 页IOI2006 选拔 第一试5 月 11 日拼图jigsaw如下图，左上、右上和左下描述了输入的凸多边形，右下描述了输出的的矩形。【注意】由于矩形纸片的两面的颜