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

《2014ACM区域赛北京赛区题目讲评.pptx》由会员分享，可在线阅读，更多相关《2014ACM区域赛北京赛区题目讲评.pptx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三十九届ACM-ICPC国际大学生程序设计竞赛北京赛区题目讲评A Curious MattA Curious MattBlack And WhiteBlack And WhiteBlack And WhiteBlack And White题目解法：1.搜索加剪枝有解的必要性条件：任意一种颜色的棋子个数不能多于棋盘格子数的一半逐格搜索，使用必要性条件进行剪枝 Black And WhiteBlack And WhiteCollisionCollision题目大意：在一个平行于坐标轴的矩形框中，有两个质点，以（1,1）的初速度移动。触碰边界将按照反射定律不损失能量地反弹。输出是否能够相遇，以及首

2、次相遇的时间。总提交人数：19+77=96封榜前AC数：2 题目解法：CollisionCollisionCollisionCollisionCollisionCollisionDire WolfDire Wolf题目大意：N只狼站成一列，每只狼有一只初始攻击力，并且可以为左右相邻的两只狼暂时提升给定的攻击力。每当击败一只狼的是否会受到该狼当前的攻击力。询问最少需要受到多少的伤害可以击败所有的狼总提交人数：174+158=332封榜前AC数：74题目解法：Dire WolfDire WolfEverlasting LEverlasting LFluorescentFluorescentFluo

3、rescentFluorescentFluorescentFluorescentHappy Matt FriendsHappy Matt Friends题目大意：给N个数构成的集合。询问有多少个子集满足，子集中的数的异或和大于等于M总提交人数：293+48=341封榜前AC数：135题目解法：Happy Matt FriendsHappy Matt FriendsHappy Matt FriendsHappy Matt FriendsIntersectionIntersection题目大意：输入两个圆环，输出两圆环的面积交。总提交人数：405+193=598封榜前AC数：116题目解法：使用容

4、斥原理，可转化为求两圆的面积交。两圆的面积交可由余弦定理求出交点后得到。K.Bro SortingK.Bro SortingGRE Words Once MoreGRE Words Once More题目大意：输入一个自动机，保证转移方程为一个DAG。有若干询问，每个询问要求输出自动机所接收的所有串中，字典序第K大的串的字符长度。总提交人数：1+5=6封榜前AC数：0 题目解法：可持久化平衡树GRE Words Once MoreGRE Words Once More根据题目条件，从一个点出去不会有两个相同的边可以知道，对于一个从1出发的路经，只要路径不一样，那么得到的串就是不一样的。如果只要

5、处理一个询问，根据DAG的性质，我们可以首先处理出从一个点出发能走出多少个合法的串（DP预处理），然后对于一个询问k，我们可以沿着这个图上走，逐一确定每一步怎么走，最后以答案长度的复杂度得到答案。上述算法时间复杂度为O(NM)GRE Words Once MoreGRE Words Once More换一个思路，如果我们不再只记录从一个点出发，能有多少个合法的串，而且还记录每一个合法的串的长度，我们把他们按字典序排一个序，并且只记前1e9个，这个我们可以用平衡树存储，那么我们DP的时候，从后往前，对于每一个点x，按照出边从小到大，把后继节点按顺序插入x的平衡树中，最后，如果x本身就是个合法的结

6、束点，那么我们在x的平衡树最前面加一个长度为0的节点。但问题是现在平衡树不可能存这么多个元素，所以我们使用可持久化平衡树即可，每次就是可持久化的合并两个平衡树而已，而且要保证平衡树的深度是log级别的，而且不能rotate，所以可以用平衡树的一些特别写法，比如基于随机合并的Treap。Just A MistakeJust A Mistake题目大意：输入一棵树，求在随机均匀采样一个排列P，输出此排列对应的独立集大小的期望。总提交人数：7+7=14封榜前AC数：0 题目解法：树形DPJust A MistakeJust A Mistake根据期望的线性可叠加的性质，我们可以分别计算每一个点得贡献，也就是先枚举一个点r，计算有多少个permutation使得r可以被选中。枚举完r后，那么唯一会影响到r得只有r的相邻点，如果r的某个相邻点x，permutation中的位置在r之后，那么他不会对r有什么影响，关键在于如果在r之前，如果x成为了独立集中的点，那么r自然就不行了，否则，还要看x得孩子中的选取情况。就这样，成了一个树上的DPJust A MistakeJust A Mistake谢谢大家谢谢大家ACMAlways Challenge Miracles