第六届北航程序设计大赛现场决赛解.doc

第六届北航程序设计大赛现场决赛解题报告圆有点挤 圆有点挤时间限制：1000 ms | 内存限制：65535 KB 描述 gg最近想给女友送两个精美的小礼品：两个底面半径分别为R1和R2的圆柱形宝石，并想装在一个盒子里送给女友。好不容易找到了一个长方体的盒子，其底面为A*B的矩形，他感觉好像宝石装不进去，但又不敢轻易塞进去试试。现请你帮他判断两个宝石能否放进盒子里(宝石只能竖直放置，且不能堆叠)。输入 输入的第一行是一个整数，为数据的组数t（t=1000）。每组数据占一行，包括4个数A，B，R1，R2，均为不超过104的正整数。输出 对于每组数据，若两个宝石能放进盒子中，则输出YES，否则输出NO。样例输入 210 10 1 110 10 4 4样例输出 YESNO题目本质为判断两个半径分别为R1和R2的圆能否放进A*B的矩形中，显然最好的放法是一个紧靠左上角，另一个紧靠右下角。因此只需判断数据能否满足以下两个条件：两个圆都能放进矩形中，即：2*R1=A2*R1=B2*R2=A2*R2=B采用紧靠对角放法后，两圆圆心的距离不小于半径之和，即：sqrt(A-R1-R2)2+(B-R1-R2)2)=R1+R2本题数据全为int型，为避免不必要的精度问题，可以将两边平方再进行比较，即：(A-R1-R2)2+(B-R1-R2)2=(R1+R2)2lzx的智商barty的智商时间限制：1000 ms | 内存限制：65535 KB 描述 barty后宫三千，但是正宫只有一个。他的正宫为了他能好好学习，成为学霸，给他定下要求，一定要把和计算机相关的各种课程都学完。对于每种课程，都会有几个或0个课程作为它的先修课程，只有把那些先修课程学完才能学习该课程，但是这个规定并不是特别严格。设barty的智商为T，且课程A有一门先修课程为B，根据B课程对A课程的影响，会规定一个相关系数C，如果TC，就是说barty足够聪明，那么就可以无视先修课程B而直接去学习A，另外一个很关键的问题就是可能存在A是B的先修课程，B是C的先修课程，C又是A的先修课程（这在实际情况中也是可能存在的），但不会有课程是它自己的先修课。需要你计算的就是：barty的智商最低为多少的时候可以让barty学完全部课程。输入 输入的第一行是一个整数，为数据的组数t（t=20）。对于每组数据，第一行为2个正整数n和m（1=n,m=10000），分别表示课程数和课程先修关系数，之后的m行，每行三个数ai、bi、ci，表示bi为ai的一门先修课程，且相关系数为ci（1=ai,bi=n，ci=109）。输出 每组数据一行，为最低需要的智商。样例输入 16 62 3 23 4 54 2 72 1 13 5 26 4 7样例输出 2首先，根据每两个课程之间是否有先修关系可以建一个有向图。课程为节点，先修关系为边。当然，每条边是有边权的，也就是每对关系的相关程度。对于特定的智商T，根据每条边权与T的关系（边权小于等于T则这条边对应的先修关系可以忽略，即这条边可以删除），能够生成一个唯一的有向图，它是否有环也是可以确定的（一次拓扑排序即可知晓），并且只要没环，那么智商T就可以学完所有的课程。而且，随着T的增加，所对应生成的有向图的边会比原来更少，并且实际上整个图会是增加前的图的子图。基于这样的偏序条件，就可以想到用二分法枚举答案，然后对这个答案构造的图进行拓扑排序（O(m)的时间复杂度可以完成）验证。这样总时间复杂度就是O(mlogm)的，其中m为边的数目。寒假安排时间限制：3000 ms | 内存限制：65535 KB 描述 寒假又快要到了，不过对于lzx来说，头疼的事又来了，因为众多的后宫都指望着能和lzx约会呢，lzx得安排好计划才行。假设lzx的后宫团有n个人，寒假共有m天，而每天只能跟一位后宫MM约会，并且由于后宫数量太过庞大了，而寒假的天数太少，所以lzx在寒假里不会与一个MM约会一次以上。现在lzx想要知道：寒假安排的方案数如果写成k进制，末位会有多少个0。输入 输入的第一行是一个整数，为数据的组数t（t=1000）。每组数据占一行，为3个正整数n、m和k（1=m=n231，2=k231），意思如上文所述。输出 对于每组数据，输出一个数，为寒假安排的方案数写成k进制末位的0的数目。样例输入 310 5 1010 1 210 2 8样例输出 110约会的方案数显然就是f=n!/(n-m)!，于是关键就是求出f的k进制末尾有多少个0。如果k分解质因数后的结果是：而某个整数x分解质因数后的结果是：即对于k的每个质因子pi，x包含了Ei个，那么x的k进制末位的0的个数就因该是：（其中 / 为整除）而对于某个质数p，n!中包含了p因子的个数就是：（其中 / 为整除）于是f中包含的p因子的个数就应该是：于是f的k进制末尾的0的数目就是：算法也就出来了。此外需要注意：k包含了一个非常大的质数或者k本身可能就是个很大的质数，有可能在分解质因数时漏掉了这种情况。木板切割木板切割时间限制：1000 ms | 内存限制：65535 KB 描述 mm有一块A*B的矩形木板，但木板上有一些钉子。ta现在需要从中切割出一个矩形木板，且只能按照与原木板边缘平行或垂直的方向切割，使切割出的木板内部(边缘不算)包含且仅包含1枚钉子，问ta能够切割出满足条件的木板的最大面积。特别的：若原木板只含一枚钉子，则不需要切割即可满足条件。输入 输入的第一行是一个整数，为数据的组数t（t=10）。每组数据第一行为三个整数A(2=A=100)，B(2=B=100)和钉子的数量n(1=n=100)。接下来n行每行2个整数，表示第i枚钉子的坐标Xi，Yi（以原始木板的左下角为原点(0，0)，0XiA，0Yi(8,2)-(8,8)-(2,8)-(2,4)-(4,4)-(4,6)-(6,6)-(6,2)输入 输入第一行为数据组数t（t=20）。对于每组数据，第一行包含两个整数X，Y（1X,Y=1000），表示战场大小。后面Y行，每行X个整数，表示战场上的战力分布，正数表示己方战力，负数表示敌方战力。下面一行包含一个整数k（k=1000），表示查询的总数。紧跟着k行表示k组查询区域：每组查询首先是一个整数T（T=1000），表示这个轮廓线上的折点数。后面有2*T个正整数，每两个整数，表示一个折点的坐标（保证按顺时针顺序给出）。保证这条折线是封闭的，并且不相交（相交于点上不算，详细见样例的第2组查询）。输出 对于每组查询，输出一个整数，表示这次闪电战的结果。样例输入 210 90 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 00 0 0 0 0 1 -1 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 028 6 2 8 2 8 8 2 8 2 4 4 4 4 6 6 610 5 3 7 3 7 6 4 6 4 4 5 4 5 5 6 5 6 4 5 4 10 90 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 00 0 0 0 0 1 -2 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 028 6 2 8 2 8 8 2 8 2 4 4 4 4 6 6 610 5 3 7 3 7 6 4 6 4 4 5 4 5 5 6 5 6 4 5 4样例输出 01-10提示 输入数据庞大，请谨慎使用C+的cin（可用C语言的scanf代替），很容易超时。其实不管查询的多边形怎么复杂，只需要考虑其与x轴平行的边与之在x轴上的投影围成的矩形（可以称为这条边“到x轴的投影区域”），把这个矩形内方格的数字和统计出来并相加就可以了（见下图）：此外需要注意一下方向，如果是从左向右的边，那么矩形的值应该取其相反数。全部相加后，就能得到多边形内的所有方格中的数的和了。证明可以话，可以这样考虑：无论多边形怎么复杂，它一定可以通过无数条x=c的竖线切成很多个矩形。因为对边缘的描述是顺时针的，所以每个矩形的上边缘一定某条从左向右的边缘线的一部分，其到x轴的投影区域的和会被减掉；而下边缘一定是某条从右向左的边缘线的一部分，其道x轴的投影区域的和会加上；合起来就正好是这个矩形内的和了。而对于每条与x轴平行的边(x1,y1)(x2,y1)的投影区域的和，其实就是：“以(x1,y1)为右下角(0,0)为左上角的区域和”减去“以(x2,y1)为右下角(0,0)为左上角的区域和”，方向的问题也正好处理好了。所以正确的解法就是：l 输入矩阵l 统计矩阵的“左上角和”（以各个点为右下角，(0,0)为左上角的区域和）l 对于每个多边形，依次（顺时针）输入边界点。每次判断相邻的两个点的连线是否是水平线，若是的，则计算这两个点的“左上角和”之差，并加入统计量。不要忘了最后一个点和第一个点的连线也是多边形边缘的一部分。此外，点的坐标与方格坐标，以及x坐标和y坐标都注意不要搞混了。人民城管爱人民人民城管爱人民时间限制：6000 ms | 内存限制：65535 KB 描述 一天GG正在和他的后宫之一的MM在外面溜达，MM突然说了一句，“我想吃鸡蛋灌饼”当他们吃的正high的时候，城管出现了！作为传说中的最强军事力量，卖鸡蛋灌饼的小贩在他们面前也只算是战力为的5的渣滓，一秒钟就被秒杀了在这场屠杀中，GG和他的后宫本来只是围观群众，但是不幸的是，城管看到了GG胃里的鸡蛋灌饼，他们要逮捕GG！但是GG显然不能让他们如愿，于是GG带着后宫开始了往大运村的逃亡之旅。整个地图有n个路口，灌饼摊在0号路口，大运村在n-1号路口。有m条只能单向通过的道路连接这n个路口，每条道路用一个正整数表示走过需要的时间。整个地图没有环路，但两个路口之间可能有多条通路。现在GG希望以最短的时间到大运村，但不幸的是，城管为了抓住他动用了卫星对他进行空中跟踪，并且会在某一时刻空降到某一条道路上进行封锁（封锁会在瞬间完成，可惜动静太大了GG也能在第一时间知道哪条道路被封锁了），之后这条路就无法通过了。在整个行动中只会出现一次空降，而且不会在GG经过这条道路的时候进行封锁，也就是说，不会在GG在某条路上走了一半的时候封锁这条路。而且，城管们希望尽可能的延缓GG到达大运村的时间。现在GG希望知道，自己多久能到达大运村，方便安排之后和其他后宫的约会。注意双方是以博弈的思想来进行选择，即GG希望时间最短，城管希望时间最长，而且他们都非常聪明会做出最佳的选择。输入 输入第一行为数据组数T（T=30）。每组数据第一行包含两个整数n,m（2=n =10000，1=m=100000），表示路口数和道路数。之后m行描述了所有的道路，每行有三个整数u,v,w（0=u,vn，0w=1000），表示路口u到路口v有一条需要w时间走过的道路。输出 对于每组数据输出一个整数，表示GG最后到达大运村需要的时间。如果GG无法到达大运村，输出-1。样例输入 25 60 1 11 2 12 4 11 4 30 3 23 4 13 40 1 10 1 21 2 31 2 4样例输出 45提示 输入数据庞大，请谨慎使用C+的cin（可用C语言的scanf代替），很容易超时。如果没有空降，那么显然就是最短路问题了，而且还是无向图的最短路，可以依拓扑序逆序递推求得。但关键是有一次空降的可能。用disti表示从i号节点出发到达终点n-1号节点的最少需要的时间（不考虑空降），这个照前面所说可以依拓扑序逆序递推求得；用fi表示GG站在i号节点上，城管有一次空降机会，双方都选取最优选择下，GG最少要花的时间。fi的求解可以这样考虑（假设i出发的所有边为line1.ci）：现在城管只有两种选择：现在不堵，即i节点出发的所有边都不堵。那么GG为了保险起见，一定是走linej.t+flinej.v最小的边，此时GG最少需要的时间就是：现在就堵，即堵住i节点出发的某条边。那么易知：堵linex的情况下，GG最少需要的时间就是而既然要堵，肯定就是堵得让GG要花的时间最长，所以现在堵的话，GG最少需要的时间就是：于是城管在权衡这两种情况后，肯定是选择让GG耗时更长的一种，于是：由此得到fi的递推式，于是可以按拓扑序逆序的顺序依次计算出所有点的f值来。最后的结果就是f0。在计算过程中要注意，t2的计算如果写成了2层循环是不行的（总时间复杂度将变为O(m2)，这会超时），可以定义：于是：即在要算fi时先预处理好st和pt数组（在O(ci)的时间复杂度内可以完成），那么计算t2的时间复杂度就是O(ci)的了，计算t1的时间复杂度也显然是O(ci)的，于是用O(ci)的时间复杂度就完成了fi的计算，于是计算f序列的总时间复杂度就是O(m)的了。lzx的向量lzx的向量时间限制：2000 ms | 内存限制：65535 KB 描述 lzx的后宫们最近在研究平面向量。向量是非常可爱的东西，它们有方向又有长度。现在lzx的每个后宫都在心里想了一个平面向量Vi，并写在情书上送给了lzx。lzx决定带一些后宫出游，至于带多少后宫那就随便啦，他要把出游的后宫们的情书拿出来，并把后宫们的向量根据平面向量加法规则加起来，得到一个新向量T，lzx说出游的快乐指数就取决于T的长度。哦，一件神奇的事情发生啦！lzx发现，所有后宫提供的向量加起来竟然是(0,0)这意味着lzx肯定不能带所有的后宫出去啦怎样让T的长度最大呢lzx找到了你。输入 输入第一行是测试数据的组数T（T=30）接下来有T组数据，每组测试数据的第一行是n（2=n=1000），接下来的n行，每一行包括两个整数ai,bi（-100000=ai,bi|S(T)|。S(T)AS(T)-A即：若T中有一个成员A与S(T)的夹角不是锐角，那么T一定不是最优的。由此可得集合T作为T0最优子集的第一必要条件：T中的任意一个元素A与S(T)的夹角都是锐角。对于某个满足第一必要条件的子集T，若将其所有元素的和S(T)作为竖直向上的法向量，则其所有成员向量必定都在地平线以上。S(T)A1A2A3A4地平线于是可得集合T作为T0最优子集的第二必要条件：T中的所有元素都在某条直线的同一侧。这样的直线若存在，可能存在无限多条，但不管哪一条，其绕原点逆时针旋转第一次碰到的T集合中的向量总是一样的，可以定义这条向量为R(T)（可能不唯一，此时R(T)为其中任意一个都没关系）；绕原点顺时针旋转第一次碰到的T集合中的向量也总是一样的，可以定义其为L(T)。对于两个向量A和B，一定可以确定其中一个（设为A）在另一个（设为B）的顺时针方向，那么对于任意的向量C，若C在A的逆时针方向上，且C在B的顺时针反向上，则称C在A与B之间。对于满足第二必要条件的集合T，若存在某个向量B不在T中，且在L(T)与R(T)之间，则|S(T+B)|S(T)|。因为B在L(T)与R(T)之间，所以B与S(T)成锐角关系，于是|B+S(T)|S(T)|，所以|S(T+B)|S(T)|。S(T)R(T)AjAiL(T)B由此可得集合T作为T0最优子集的第三必要条件：不存在T0-T中的元素A在L(T)与R(T)之间。B以A为基向量的逆时针转角AB由第三必要条件可知：若将T0的所有成员按极角（以x轴正方向为基向量的逆时针转角）排序，最优选择一定是连续的若干个向量或连续的前若干个加上连续的后若干个向量。再由于所有向量的和为0，即S(T)+S(T0-T)=0，即|S(T)|=|S(T0-T)|，即连续的前若干个加上连续的后若干个向量等价于连续的若干个向量，所以最优选择一定是连续的若干个向量。于是得到算法：l 首先将所有向量按极角排序，得到A1.Anl 计算向量序列的前缀和序列S0.Sn（Si=A1+A2+Ai）l 检查所有的i和j（0=ij=n），得到max|Sj-Si-1|。时间复杂度为O(n2)。按极角排序的关键在于如何判断两个向量的极角哪个更大。如果把那个角度确实得算出来又太麻烦了，还要考虑向量与坐标轴平行和垂直的情况。可以这样：先辨别出这个向量在第几象限（可以认为x轴正方向的在第一象限，y轴正方向的在第二象限，x轴负方向的在第三象限，y轴负方向的在第四象限），不同象限的可直接判断大小关系，对于