2014ACM区域赛北京赛区题目讲评

《2014ACM区域赛北京赛区题目讲评》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三十九届ACM-ICPC国际大学生程序设计竞赛北京赛区题目讲评ACuriousMatt题目大意：读入一个仅含折线段的路程-时间图像，求速度最大值。总提交人数：227封榜前AC数：182题目解法：将读入的点按照时间为关键字排序，相邻两点斜率绝对值的最大值即是答案。时间复杂度。BlackAndWhite题目大意：在的棋盘中放置种颜色的棋子，第种颜色的棋子需使用恰好个。询问是否可行，若可行，输出任一放置方案。总提交人数：176+248=424封榜前AC数：39题目解法：BlackAndWhite题目

2、解法：1.搜索加剪枝有解的必要性条件：任意一种颜色的棋子个数不能多于棋盘格子数的一半逐格搜索，使用必要性条件进行剪枝BlackAndWhite题目解法：2.构造有解的充要条件：任意一种颜色的棋子个数不能多于棋盘格子数的一半黑白染色，先放黑格，再放白格（需要视情况交换N,M）。时间复杂度。Collision题目大意：在一个平行于坐标轴的矩形框中，有两个质点，以（1,1）的初速度移动。触碰边界将按照反射定律不损失能量地反弹。输出是否能够相遇，以及首次相遇的时间。总提交人数：19+77=96封榜前AC数

3、：2题目解法：Collision题目解法：1.将速度按照横纵方向分解为两维独立处理。对于每一维，可以发现该维度上两质点相遇的时间呈等差数列。于是可将题目转化为求两个等差数列第一次相等的项。可列同余方程并用扩展欧几里得算法求解。时间复杂度。Collision题目解法：2.将速度按照横纵方向分解为两维独立处理。对于每一维，可以发现该维度上两质点相遇的时间呈等差数列。于是可将题目转化为求两个等差数列第一次相等的项。由于初始速度为（1,1），上述等差数列的公差乘2一定为整数。因此可以对其中一个等差数列的

4、项进行枚举，O（1）判断是否在另一个等差数列中出现。由于公差的特殊限制，只需枚举矩形框长宽的两倍即可。时间复杂度。Collision题目解法：2.由于公差的特殊限制，只需枚举矩形框长宽的两倍即可。所以可以直接维护两点轨迹（前10000次碰撞），求出首次相遇位置。时间复杂度。DireWolf题目大意：N只狼站成一列，每只狼有一只初始攻击力，并且可以为左右相邻的两只狼暂时提升给定的攻击力。每当击败一只狼的是否会受到该狼当前的攻击力。询问最少需要受到多少的伤害可以击败所有的狼总提交人数：174+158=

5、332封榜前AC数：74题目解法：DireWolf题目解法：动态规划。定义F[I][J]表示率先消灭第I只狼到第J只狼间的所有狼所需要的最少代价。枚举这些狼中最后一只被消灭的狼。由于状态假设了其他的狼都还存活，因此此时该只狼被I-1和J+1两只狼提升了攻击力。即。EverlastingL题目大意：给出N个范围在200*200以内的整点集合S，求有多少个S的子集构成的有序对。要求两点集分别构成L型，L的长宽互素，两子集的交为空。总提交人数：12+30=42封榜前AC数：5题目解法：预处理出以集合S内

6、的点构成L拐点的子集个数。首先求出允许子集交不为空的有序对个数。在此基础上减去子集的交一定不为空的有序对个数即可。时间复杂度，X为整点坐标的最大值（小于200）Fluorescent题目大意：有N盏灯，M个开关，每个开关可以控制若干盏灯（打开开关可以反转灯的暗灭状态）。在初始的时候所有灯都是暗的状态。每个开关以0.5的几率被打开。令X表示最后亮着的灯的个数，求总提交人数：23+36=59封榜前AC数：13题目解法：Fluorescent题目解法：1.根据期望的线性可加性，可枚举三盏灯，并通过DP求

7、出这三盏灯最终同时处于亮的状态的概率。最终答案即为所有概率的总和。DP的状态为F[I][J][K][L]（依次枚举至第I个开关，三盏灯的亮灭情况分别是J,K,L，此情况发生的概率）DP的时间复杂度为。总时间复杂度。Fluorescent题目解法：2.根据期望的线性可加性，可枚举三盏灯，求出这三盏灯最终同时处于亮的状态的概率。最终答案即为所有概率的总和。由于该概率可转化为判断一个3*M的矩阵的秩。可用位运算在常数时间内求解。时间复杂度。HappyMattFriends题目大意：给N个数构成的集合。询

8、问有多少个子集满足，子集中的数的异或和大于等于M总提交人数：293+48=341封榜前AC数：135题目解法：HappyMattFriends题目解法：1.对数的每一位列方程，高斯消元求解自由元的个数。总时间复杂度。HappyMattFriends题目解法：2.折半搜索，使用TIRE树统计答案总时间复杂度。Intersection题目大意：输入两个圆环，输出两圆环的面积交。总提交人数：405+193=598封榜前AC数：116题目解法：使用容斥原理，可转化为求两圆的面积交。两圆的面