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

2011 阿里巴巴程序设计公开赛 作者的解说

以下是解题报告

1001 Coin Game

类型:博弈/想法题(简单)

假设我们有10枚硬币,K=2,第一个玩家拿走一枚之后,第二个玩家在圆的对称点拿走相应的,保持剩下的两边硬币相等,这样不管第一个玩家怎么取,第二个玩家只要在另一边一样的取法就能保证自己是最后一个取硬币的.也可以根据SG定理知道,SG值一样的两个游戏为必败状态.

推广到更大的情况也一样,所以第一个玩家胜利的情况只可能是N为奇数且K为1,或者K>=N,

其他情况均第二个玩家胜.

当然你也可以用sg定理去推出初始状态的必胜必败情况,从而得到规律.不过比较费时间且没有上述推论直观.

1002 Fruit Ninja

类型:几何(简单)

假设有一条线穿过一些水果,那么我们将这条线平移,使之与一水果的一个点相交,然后按这个点进行旋转,又可以使之与另一水果的一个点相交.这次这条线还是穿过这些水果.

所以,我们可以枚举两两水果的点做直线,然后计算该线穿过水果的个数

数据规模很小,随意随便搞.复杂度O(n^3*k^3).

1003 I'll play a trick on you

类型:非主流(简单)

呵呵,本题的名字就是我会和你开个小玩笑.

第一眼看到这题,很容易得到99-72=27这样的结论,并且?=15的时候,36-21=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数据范围这么大已经给了很大提示了,就禁止大家往很复杂的方面想,什么素数啊什么的.

Word文档免费下载Word文档免费下载:阿里巴巴2011程序设计公开赛的解题报告 (共4页,当前第1页)

你可能喜欢

  • 季度财务报表
  • 阿里巴巴研究
  • 阿里巴巴财务分析
  • 商业模式分析
  • 阿里巴巴分析报告
  • 小学信息学竞赛
  • c语言程序设计报告

阿里巴巴2011程序设计公开赛的解题报告相关文档

最新文档

返回顶部