《2014acm区域赛北京赛区题目讲评》由会员分享，可在线阅读，更多相关《2014acm区域赛北京赛区题目讲评（27页珍藏版）》请在金锄头文库上搜索。
1、第三十九届ACM-ICPC国际大学生程序设计竞赛北京赛区题目讲评A Curious Matt Black And White Black And White 题目解法： 1.搜索加剪枝 有解的必要性条件： 任意一种颜色的棋子个数不能多于棋盘格子数的一半 逐格搜索，使用必要性条件进行剪枝Black And White Collision 题目大意：在一个平行于坐标轴的矩形框中，有两个质点，以（ 1,1）的初速度移动。触碰边界将按照反射定律不损失能量地反 弹。输出是否能够相遇，以及首次相遇的时间。 总提交人数：19+77=96 封榜前AC数：2 题目解法：Collision Collision C
2、ollision Dire Wolf 题目大意：N只狼站成一列，每只狼有一只初始攻击力，并且可 以为左右相邻的两只狼暂时提升给定的攻击力。每当击败一只狼 的是否会受到该狼当前的攻击力。询问最少需要受到多少的伤害 可以击败所有的狼 总提交人数：174+158=332 封榜前AC数：74 题目解法：Dire Wolf Everlasting L Fluorescent Fluorescent Fluorescent Happy Matt Friends 题目大意：给N个数构成的集合。询问有多少个子集满足，子集 中的数的异或和大于等于M 总提交人数：293+48=341 封榜前AC数：135 题目解
3、法：Happy Matt Friends Happy Matt Friends Intersection 题目大意：输入两个圆环，输出两圆环的面积交。 总提交人数：405+193=598 封榜前AC数：116 题目解法：使用容斥原理，可转化为求两圆的面积交。两圆的面 积交可由余弦定理求出交点后得到。K.Bro Sorting GRE Words Once More 题目大意：输入一个自动机，保证转移方程为一个DAG。有若干 询问，每个询问要求输出自动机所接收的所有串中，字典序第K 大的串的字符长度。 总提交人数：1+5=6 封榜前AC数：0 题目解法：可持久化平衡树GRE Words Once
4、 More根据题目条件，从一个点出去不会有两个相同的边可以知道，对于一个从1出发的路经，只要路径不一样，那么得到的串就是不一样 的。如果只要处理一个询问，根据DAG的性质，我们可以首先处理出从 一个点出发能走出多少个合法的串（DP预处理），然后对于一个 询问k，我们可以沿着这个图上走，逐一确定每一步怎么走，最后 以答案长度的复杂度得到答案。上述算法时间复杂度为O(NM)GRE Words Once More 换一个思路，如果我们不再只记录从一个点出发，能有多少个合法 的串，而且还记录每一个合法的串的长度，我们把他们按字典序排一个序，并且只记前1e9个，这个我们可以用平衡树存储，那么我 们“DP
5、“的时候，从后往前，对于每一个点x，按照出边从小到大， 把后继节点按顺序插入x的平衡树中，最后，如果x本身就是个合法 的结束点，那么我们在x的平衡树最前面加一个长度为0的节点。但问题是现在平衡树不可能存这么多个元素，所以我们使用可持久 化平衡树即可，每次就是可持久化的合并两个平衡树而已，而且要保证平衡树的深度是log级别的，而且不能rotate，所以可以用平衡 树的一些特别写法，比如基于随机合并的Treap。Just A Mistake 题目大意：输入一棵树，求在随机均匀采样一个排列P，输出此 排列对应的独立集大小的期望。 总提交人数：7+7=14 封榜前AC数：0 题目解法：树形DPJust A Mistake根据期望的线性可叠加的性质，我们可以分别计算每一个点得贡献 ，也就是先枚举一个点r，计算有多少个permutation使得r可以被选 中。枚举完r后，那么唯一会影响到r得只有r的相邻点，如果r的某个相 邻点x，permutation中的位置在r之后，那么他不会对r有什么影响 ，关键在于如果在r之前，如果x成为了独立集中的点，那么r自然 就不行了，否则，还要看x得孩子中的选取情况。就这样，成了一个树上的DPJust A Mistake 谢谢大家 ACMAlways Challenge Miracles
