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

第六届北航程序设计大赛现场决赛解题报告 圆有点挤 圆有点挤 时间限制：1000 ms | 内存限制：65535 KB 描述 gg最近想给女友送两个精美的小礼品：两个底面半径分别为R1和R2的圆柱形宝石，并想装在一个盒子里送给女友。好不容易找到了一个长方体的盒子，其底面为A*B的矩形，他感觉好像宝石装不进去，但又不敢轻易塞进去试试。现请你帮他判断两个宝石能否放进盒子里(宝石只能竖直放置，且不能堆叠)。

输入 输入的第一行是一个整数，为数据的组数t（t<=1000）。

每组数据占一行，包括4个数A，B，R1，R2，均为不超过104的正整数。 输出 对于每组数据，若两个宝石能放进盒子中，则输出YES，否则输出NO。

样例输入 2 10 10 1 1 10 10 4 4样例输出 YES NO

题目本质为判断两个半径分别为R1和R2的圆能否放进A*B的矩形中，显然最好的放法是一个紧靠左上角，另一个紧靠右下角。因此只需判断数据能否满足以下两个条件： <1>两个圆都能放进矩形中，即： 2*R1<=A 2*R1<=B 2*R2<=A 2*R2<=B <2>采用紧靠对角放法后，两圆圆心的距离不小于半径之和，即： sqrt((A-R1-R2)2+(B-R1-R2)2)>=R1+R2 本题数据全为int型，为避免不必要的精度问题，可以将两边平方再进行比较，即： (A-R1-R2)2+(B-R1-R2)2>=(R1+R2)2

lzx的智商 barty的智商 时间限制：1000 ms | 内存限制：65535 KB 描述 barty后宫三千，但是正宫只有一个。他的正宫为了他能好好学习，成为学霸，给他定下要求，一定要把和计算机相关的各种课程都学完。

对于每种课程，都会有几个或0个课程作为它的先修课程，只有把那些先修课程学完才能学习该课程，但是这个规定并不是特别严格。设barty的智商为T，且课程A有一门先修课程为B，根据B课程对A课程的影响，会规定一个相关系数C，如果T>＝C，就是说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）。

输出 每组数据一行，为最低需要的智商。

样例输入 1 6 6 2 3 2 3 4 5 4 2 7 2 1 1 3 5 2 6 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<=n<231，2<=k<231），意思如上文所述。

输出 对于每组数据，输出一个数，为寒假安排的方案数写成k进制末位的0的数目。

样例输入 3 10 5 10 10 1 2 10 2 8样例输出 1 1 0

约会的方案数显然就是f=n!/(n-m)!，于是关键就是求出f的k进制末尾有多少个0。 如果k分解质因数后的结果是： 1iheiikp

而某个整数x分解质因数后的结果是：

1ihEiixyp

即对于k的每个质因子pi，x包含了Ei个，那么x的k进制末位的0的个数就因该是： 1/miniiihEe（其中 ’/’ 为整除）

而对于某个质数p，n!中包含了p因子的个数就是： 23,///......countnpnpnpnp

（其中 ’/’ 为整除）

于是f中包含的p因子的个数就应该是： ,,countnpcountnmp

于是f的k进制末尾的0的数目就是： 

1,,/miniiiihcountnpcountnmpe

算法也就出来了。此外需要注意：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))，00

输出 对于每组数据，输出满足条件的木板最大面积。 样例输入 2 10 10 1 5 5 100 100 5 20 90 90 20 50 50 30 80 80 30

样例输出 100 6400

题目要求找出能切割出的最大面积的包含且仅包含一枚钉子的小木板。这样的小木板其四个边缘要么已经是原木板的边缘，要么边缘上有钉子，否则还可以将该边缘继续向外扩展。

于是可以枚举小木板的上、下边缘（枚举值为所有钉子的y坐标以及0和B），这样只要找到一个最长的横向跨度使其仅包含一枚钉子。将所有位于两条边缘线之间的钉子投影为x坐标轴上的点。记录每个x位置上点的数量，找出包含且仅包含一个点的最大长度区间作为横向长度(注意边界)，纵向长度即为上下边缘的y坐标之差。两者之积为当前枚举情况下的最优解。最终答案为所有枚举情况最优解的最大值。

时间复杂度为n2的纵向枚举乘以n的横向扫描，即O(n3)。 闪电战 时间限制：6000 ms | 内存限制：65535 KB 描述 最近北航ACM队内看是流行一款叫做RUSE的即时策略游戏，这款游戏的迷人之处就在于真真假假虚虚实实，对抗性很强。Sbihero是这方面的达人，因为他为了这个游戏构造了一个合适的模型：

将整个战场可以视为为n*m的一个矩阵，每个元素值都代表着这一区域内的战力值，正值代表己方的战力，负值代表敌方的战力，零表示无军事力量。 而Sbihero最喜欢用的国家德国还有一项特殊的战术——闪电战。闪电战必须在一个连续的区域内发动，动员这一区域内的全部己方军事力量向敌方进攻。如果此区域己方的战力总和大于敌方的战力总和，那么这场闪电战就记为胜利，否则为失败。结果即为己方战力和敌方战力的差值。

现在Sbihero算数算不过来了„他麻烦你来写一个程序，计算在已知战场上任意一连续区域内发动闪电战的结果。（每个连续区域用一个封闭的顺时针折线来围成）如下图区域：

可以表示为(6,2)-->(8,2)-->(8,8)-->(2,8)-->(2,4)-->(4,4)-->(4,6)-->(6,6)-->(6,2) 输入 输入第一行为数据组数t（t<=20）。 对于每组数据，第一行包含两个整数X，Y（1个整数，表示战场上的战力分布，正数表示己方战力，负数表示敌方战力。

下面一行包含一个整数k（k<=1000），表示查询的总数。 紧跟着k行表示k组查询区域：每组查询首先是一个整数T（T<=1000），表示这个轮廓线上的折点数。后面有2*T个正整数，每两个整数，表示一个折点的坐标（保证按顺时针顺序给出）。

保证这条折线是封闭的，并且不相交（相交于点上不算，详细见样例的第2组查询）。 输出 对于每组查询，输出一个整数，表示这次闪电战的结果。 样例输入 2 10 9 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0