阿里巴巴程序设计方案公开赛的解题报告

1、以下是解题报告1001 Coin Game类型:博弈/想法题 (简单)假设我们有 10 枚硬币 ,K=2, 第一个玩家拿走一枚之后 , 第二个玩家在圆的对称点拿走相应的 , 保持剩下的两边硬币相等 , 这样不管第一个玩家怎么取 , 第二个玩家只要在另一边一样的取法就能保证自己是最后一个取硬币的 . 也可以根据 SG定理知道 ,SG 值一样的两个游戏为必败状态 .推广到更大的情况也一样, 所以第一个玩家胜利的情况只可能是N 为奇数且 K 为 1, 或者 K>=N,其他情况均第二个玩家胜.当然你也可以用sg 定理去推出初始状态的必胜必败情况, 从而得到规律 . 不过比较费时间且没有上述推论直

2、观 .1002 Fruit Ninja类型:几何(简单)假设有一条线穿过一些水果 , 那么我们将这条线平移 , 使之与一水果的一个点相交 , 然后按这个点进行旋转 , 又可以使之与另一水果的一个点相交 . 这次这条线还是穿过这些水果 .所以 , 我们可以枚举两两水果的点做直线, 然后计算该线穿过水果的个数数据规模很小 , 随意随便搞 . 复杂度 O(n3*k3).1003 I'll play a trick on you类型 : 非主流 (简单 )呵呵 , 本题的名字就是我会和你开个小玩笑.第一眼看到这题, 很容易得到 99-72=27这样的结论 , 并且 ?=15 的时候 ,36-2

3、1=15和 28-15=13都是成立的 ,估计会有很多人看到此处就会提交A-B,而且范围里给了1<=B<=A<= 10100 ,很容易让人用大数提交.但是 , 最后一个7 却不符合21-13=7的规律 , 所以 .提交 A-B 是 AC 不了的 .其实真相就是9+9+7+2=27,4+5+2+7=18.而 ?=12. 6组数据全部说的通只需要把所有数字加加起来就好了.其实 A 和 B 数据范围这么大已经给了很大提示了, 就禁止大家往很复杂的方面想, 什么素数啊什么的.作为非主流题 , 如果有人能算出 ?并且和给出和官方不一样的解释 , 那就悲剧了 , 所以 Hint 里加了句

4、如果能有更牛逼的解法但 AC 不了 , 我本人给以小安慰一下1004 Level up类型 : 数据结构 -线段树 (中等 )题意很简单 , 成段更新 , 成段询问 , 但是更新却和一般的线段树大不一样, 每个点虽然接收到相同的信息, 但是由于本身不同 , 最终得到的值也是不同的 . 用一般的延迟操作就搞不定了 .突破点在 K, 范围很小 , 只有 10, 可以考虑每次有人升级的时候, 就递归的找下去 , 将这个人进行升级操作. 由于找到某个人只需要logn的复杂度 , 每个人最多升 k 次, 所以 n 个人的复杂度是 O(nklogn)用了两个辅助数组addmaxn 和 MAXmaxkmax

5、n,add用于记录延迟标记 ,MAXk 表示该区间等级为k的最大经验值 . 初始化 add,MAX1 为 0, 其他为 -1, 表示无人在这个等级 . 当 MAXk 的值大于等于 Needk时 ,就对这个区间进行升级操作, 和线段树操作一样递归的将这个区间能升级的人全部升级.单次操作可能会是nlogn(每个人都升级 ), 但是平均下来还是只有nklogn.1005 March类型 : 搜索 (中等偏简单 )理解题意搞清楚优先级后, 然后简单的搜过去就好. 提几个注意点 :1. 奇数行和偶数行的 6 个方向行走坐标变化是不一样的 .2. 就算你当前只剩0.25MPs,你也可以走任意一格, 这样会

6、你消耗光你这回合剩下的MPs3. 敌人优先级最高 . 在 ZOCs 间走消耗所有 MPs4. 然后是路5. 然后是河流6. 最后才考虑前进格子的地形7. 为了避免不必要的错误 , 数据已经保证了这边有河流 , 对应的那格也有河流1006 SanguoSHA类型 : 模拟 + 状态 DP(难)如果没玩过三国杀的话这题简直做这题就是天方夜谭了, 就像国外那种巨长模拟题一样没玩过三国杀的人看过题目, 还是能看明白的, 就是累了点 ., 规则巨复杂, 不过我给1-3 主要是介绍三国杀的一般规则 , 玩过的童鞋扫一遍就 ok 了,4 和 5 才是题目重点 , 标记规则和攻击规则 , 需要仔细阅读dp 的

7、状态是 round:80state_nj:5state_all:36;round表示回合数,8个人 *10论state_nj:表示内奸状态,0:未知身份,1:被认为忠臣,2:被认为反贼,3:被认为内奸,4:死State_all:表示除主公内奸的其他角色状态,0未知身份 ,1身份被标记,2死亡( 由于大家都按常规出牌, 反贼和忠诚不会被标记成其他角色)然后就是安步就班的模拟下去.建议写个函数 , 标注 a 攻击 b 之后状态的变化情况, 然后无论谁攻击谁都调用这个函数就简单方便很多这种模拟题还是多分成小块来写的好, 容易差错标称写了16 个函数1007 Street Fighter类型 :dan

8、cing links( 中等 )很直观的最小支配集问题, 用 dancing links的重复覆盖很好解决.但是由于每个角色只能选一次, 即一个角色只能选一个模式. 所以这又是精确覆盖.一共有 sigma(Mi)+N 最后只要判断覆盖了列,sigma(Mi)sigma(Mi)列就列在搜索时需要重复覆盖ok 了 ., 另外的N 列表示角色的选择, 需要精确覆盖.需要再模板上改好一些内容, 任何一小点都很容易导致死循环.1008 Tower Defence类型 : 插头 DP(难)题目要求放W使得路线最长 , 我们反过来理解ok 了.(或者其他所有的格子都放W), 就可以找一条最长的路( 边不重合

9、 ),然后在这路的边上放满W就为了保证这条路径边不重合, 我们不仅需要记录轮廓线上方的插头状态果当前格上方有路, 但是上方没有插头, 这样这格就不能建任何路了必然导致边的重合., 还需要记录上方的路的状态. 比如 :, 因为在这格建的路不能和上方的路连起来如,由于 S 和 T 都不固定 , 需要有独立插头, 括号表示法的话会比较难写. 建议用最小表示法来标记插头1009 Board Game Dice类型:数学(简单)就是等比公式化简一下. 高中数学 . 概率学的好的童鞋应该一眼就能看出答案.最后的答案是Mx*x/N.1010 World of Warcraft类型 :NP( 无解)我错了 , 大家原谅 .T_T以下是原来错误的方法出题的时候很怕这题被按结束时间优先的方式贪心过去 , 但是贪心没办法处理开始时间和结束时间都相同的指令的安排 ,我特地造了几组数据卡这种贪心 .不知道实际比赛中有木有大神能用更犀利的贪心贪过去 .正解是网络流 ,建一个包含源汇六层的模型.第一层 : 源点 (1)第二层 : 指令 (100)第三层 : 快捷键按时间拆点(104*100)第四层 : 按键按时间拆点 (29*10