有道难题2009决赛题目、前三名解题思路、官方答案与点评.doc

有道难题2009决赛题目、前三名解题思路、官方答案与点评有道难题2009决赛题目Final Round 1 题目: 1.1 CountingCrosses (easy)Problem Statement:M x N个点构成了一个矩形网格，M行N列。每个点是黑色或者白色。十字架由2个相交线段构成：垂直线段AB和水平线段CD，其中，A，B，C，D是不同的网格格点，点A和B不属于线段CD，点C和D不属于线段AB。设交点为E，一个有效的十字架要求满足如下条件：A，B，C，D和E颜色相同。给定String grid，grid数组第i个元素的第j个字符如果是W，则表明第i行第j列的点是白色，B则代表黑色。返回给定网格中有效的十字架个数。Definition Class: CountingCrosses Method: count Parameters: String Returns: int Method signature: int count(String grid) (be sure your method is public)Constraints grid 包含1到50个元素，含1和50。 grid的每个元素含1到50个字符，含1和50。 grid的所有元素包含相同数量的字符。grid的每个元素只包含字符W和 B。Examples 0)BWB,WWW,BWBReturns: 1只有一个白色的十字架。1)BWB, WBW, BWBReturns: 0十字架水平部分和竖直部分的交点一定要和端点颜色一样。图中没有满足条件的十字架。 2)WWWW, WWWW, WWWW, WWWWReturns: 16中央的4个点有希望成为十字架的交点E，每个点对应4个不同的有效十字架，所以总数是4*4=16。 3)WReturns: 04)BWBW, BBBB, WWWW, BWBWReturns: 4分别以点(1,2) B 和点(2,1)W为交点，各对应2个有效的十字架，注意十字架中非端点和交点部分的颜色没有要求。题目: 1.2 YoudaoInterns(DisobidentChildren) (medium)Problem Statement:有道最近招聘了一批实习生，给他们安排座位时遇到了一个有趣的问题。办公室有N排，每排有M个座位。为了方便实习生和全职员工更好的交流，安排座位时，我们不让任何2个实习生座位水平，竖直或者对角线相邻。给定一个String intern, 把intern的每个元素依次拼接起来得到一串以单个空格隔开的数字。这串数刚好有N个，第i个数字表示安排在第i排的实习生数量。请计算满足条件的座位安排方案总数。因为总数可能过大，返回方案总数除以1000000007的余数。 Definition:Class: YoudaoInternMethod: numberOfWaysParameters: int, StringReturns: intMethod signature: int numberOfWays(int M, String intern)(be sure your method is public) Constraints:M 在1到15之间，含1和15。intern有1到50个元素，含1和50。intern的每个元素包含1到50个字符，含1和50。intern所有元素拼接起来后，会得到一串以单个空格隔开的数字，数字不会以0开始，这串数不会以空格开始或结尾，也不会有连续的空格。 intern元素拼接得到的数字串包含1到200个数字，含1到200，每个数字大小在0到M之间，含0和M。Examples:0)3 2Returns: 1只有一个方案把2个实习生安排在这一排。1)4 1Returns: 4实习生可以被安排在这排的4个座位中任何一个。 2)3 1 1, 1Returns: 2两种方案如下： X. .X.X X.X. .X3)14 2 1,0Returns: 0没有方法可以安排这么多实习生在同一排。注意intern代表int 2, 10。4)4 1 1 1Returns: 10题目: 1.3 SlidingPenguins (hard)Problem Statement:Jack 和 Jill 在南极研究工作站工作。为了消磨时间，他们经常玩一个游戏。这个游戏在一个包含roadLength 个路段的路上进行。比赛开始时，路上有一些企鹅；penguins 的第i个元素表示第i个企鹅站在这条路上的哪个路段（从0开始编号）。比赛的规则如下：Jack 和 Jill 交替进行，Jill 先开始，初始的时候，所有企鹅都没有确定方向。在前N轮，其中N表示penguins中的元素个数，当前的游戏者选择最左边一个未定向的企鹅，并且确定它的方向是向左（面向编号更小的路段）还是向右（面向编号更大的路段）。一旦企鹅被确定方向，它的方向是不可以被改变的。在随后的游戏中，每一轮游戏者挑选一个企鹅，并且让其朝它之前被设定的方向滑行。moveLengths 包含了企鹅可以滑行的所有步数；比如，1, 4, 3表示企鹅可以向前滑行1、4或者 3步，但由游戏者来从中选择具体滑行哪个步数。企鹅向前滑行的过程中，会在它离开某个路段的时候融化掉这个路段。被融化的路段不能被任何企鹅再次通过或者停留。任何一个企鹅都不能滑出这条路，到达或者通过一个被融化的路段，也不可以到达或通过一个已经有其他企鹅的路段。如果一个游戏者无法做出一个合法的动作，他（她）输掉这个游戏。Jack 和Jill 会一直选择最优策略来进行游戏。请确定这个游戏的获胜者。如果Jill 获胜，返回JILL WINS。否则，返回JACK WINS。 Definition:Class: SlidingPenguinsMethod: determineWinnerParameters: int, int, int Returns: String Method signature: String determineWinner(int roadLength, int penguins, int moveLengths)(be sure your method is public) Constraints:roadLength是1到30000之间的整数，含1和30000。Penguins包含1到50个元素，含1和50。Penguins中每个元素都是0到roadLength - 1的整数，含0和roadLength - 1。Penguins中的元素已经按照升序排列，且没有重复的元素。moveLengths包含1到50个元素，含1和50。moveLengths中每个元素都是1到30000之间的整数，含1和30000。moveLengths中没有重复元素。 Examples:0)6 3 1,2Returns: JILL WINSJill 会在她的第一步将这只企鹅方向定为左。因为所有的企鹅都已经被确定方向，Jack 不得不将这只企鹅向前滑行1或2步。不管他怎样做，Jill的下一步都可以将这只企鹅滑行到片段0，然后Jack无法做出合法的移动。1)6 3 1,2,3Returns: JACK WINS不管 Jill 将这只企鹅如何定向，Jack都可以移动这只企鹅使得Jill输。2)6 0,5 1,3Returns: JACK WINS3)15 1, 4, 9, 12 2, 5, 4Returns: JILL WINS4)1234 1,35,82,193,203,299,303,388,509,684,718,994,1111,1223 1,4,8,3,91,12,40,31,13Returns: JILL WINSFinal Round 2 题目: 2.1 TheHieroglyphs (easy)Problem Statement: 象形文字H0,H1,Nn-1组成的长度为n的序列称为一个句子。如果句子中不存在两个下标i和j（0 = i j n - 1），使得句子中的第i个元素Hi和第j个元素Hj是同一个象形文字，且Hi+1和Hj+1是不同的象形文字，那么这样的一句话称为是“严格的”。假设有k个象形文字，请计算长度为n的序列中有多少个是“严格的”。 Definition:Class: TheHieroglyphs Method: countParameters: int, int Returns: longMethod signature: long count(int n, int k)(be sure your method is public) Constraints:n 和k 的取值在1到18之间，含1和18。 Examples:0)7 1Returns: 1这里只有1个象形文字，所以只有1种句子，且是“严格”的。1)1 7Returns: 72)4 2Returns: 6我们用A和B表示这2种象形文字，那么能够构造出的长度为4的句子为：AAAA、BBBB、ABBB、BAAA、ABAB、BABA。3)2 4Returns: 16我们用A和B表示这2种象形文字，那么能够构造出的长度为4的句子为：AAAA、BBBB、ABBB、BAAA、ABAB、BABA。题目: 2.2 SlidingPenguins(medium)Problem Statement:Jack 和 Jill 在南极研究工作站工作。为了消磨时间，他们经常玩一个游戏。这个游戏在一个包含roadLength 个路段的路上进行。比赛开始时，路上有一些企鹅；penguins 的第i个元素表示第i个企鹅站在这条路上的哪个路段（从0开始编号）。比赛的规则如下：Jack 和 Jill 交替进行，Jill 先开始，初始的时候，所有企鹅都没有确定方向。在前N轮，其中N表示penguins中的元素个数，当前的游戏者选择最左边一个未定向的企鹅，并且确定它的方向是向左（面向编号更小的路段）还是向右（面向编号更大的路段）。一旦企鹅被确定方向，它的方向是不可以被改变的。在随后的游戏中，每一轮游戏者挑选一个企鹅，并且让其朝它之前被设定的方向滑行。moveLengths 包含了企鹅可以滑行的所有步数；比如，1, 4, 3表示企鹅可以向前滑行1、4或者 3步，但由游戏者来从中选择具体滑行哪个步数。企鹅向前滑行的过程中，会在它离开某个路段的时候融化掉这个路段。被融化的路段不能被任何企鹅再次通过或者停留。任何一个企鹅都不能滑出这条路，到达或者通过一个被融化的路段，也不可以到达或通过一个已经有其他企鹅的路段。- 如果一个游戏者无法做出一个合法的动作，他（她）输掉这个游戏。- Jack 和Jill 会一直选择最优策略来进行游戏。请确定这个游戏的获胜者。如果Jill 获胜，返回JILL WINS。否则，返回JACK WINS。 Definition:Class: SlidingPenguinsMethod: determineWinnerParameters: int, int, int Returns: StringMethod signature: String determineWinner(int roadLength, int penguins, int moveLengths)(be sure your method is public)Constraints:roadLength是1到30000之间的整数，含1和30000。Penguins包含1到50个元素，含1和50。Penguins中每个元素都是0到roadLength - 1的整数，含0和roadLength - 1。Penguins中的元素已经按照升序排列，且没有重复的元素。moveLengths包含1到50个元素，含1和50。moveLengths中每个元素都是1到30000之间的整数，含1和30000。moveLengths中没有重复元素。 Examples:0)6 3 1,2Returns: JILL WINSJill 会在她的第一步将这只企鹅方向定为左。因为所有的企鹅都已经被确定方向，Jack 不得不将这只企鹅向前滑行1或2步。不管他怎样做，Jill的下一步都可以将这只企鹅滑行到片段0，然后Jack无法做出合法的移动。1)66 3 1,2,3Returns: JACK WINS不管 Jill 将这只企鹅如何定向，Jack都可以移动这只企鹅使得Jill输。2)6 0,5 1,3Returns: JACK WINS不管 Jill 将这只企鹅如何定向，Jack都可以移动这只企鹅使得Jill输。3)15 1, 4, 9, 12 2, 5, 44)1234 1,35,82,193,203,299,303,388,509,684,718,994,1111,1223 1,4,8,3,91,12,40,31,13Returns: JILL WINS题目: 2.3 OneofEachKind(hard)Problem Statement:有一个M x N的矩形网格，其中每个单元格包含一个1到999之间的整数（含1和999）或者为空，而且每个数字在矩形网格中至多出现两次。你必须选择一些单元格组成的一个集合，满足下述条件：1.对于网格中的每一个数字，必须在你选中的单元格中恰好出现一次。2.任意两个选中的单元格都不相邻。两个单元格相邻是指它们有一条公共边。你不光可以选择带有数字的单元格，你同样可以选择空的单元格。只要不违反上述条件2，你可以选择任意多的空单元格。矩形网格由三个String a、b和c给出。矩形网格位置(i, j)处的单元格数字是a、b、c第i个元素的第j个字符的依次拼接而成。每个数字都恰好有三位，其中某些有前导零。数字000表示一个空的单元格。你需要返回一个String，如果你选中了位置(i,j)处的单元格，则第i个元素的第j个字符为#，否则为.。如果有多个解，那么返回一个字典序最小的答案。如果无解，则返回一个空的String。 Definition:Class: OneOfEachKindMethod: chooseParameters: String, String, String Returns: String Method signature:String choose(String a, String b, String c)(be sure your method is public) Notes:如果两个 String A 和 B 包含同样个数的元素，那么A的字典序比B小当且仅当在它们编号最小的不同的元素处，A包含字典序更小的 String。 如果两个 String A 和 B 长度相同，那么 A 的字典序比 B小当且仅当在它们编号最小的不同的字符处，A包含字典序更小的字符（# 的字典序比 .小）。 Constraints:a、b和c包含相同个数的元素。a、b和c中每个元素都拥有相同的长度。a、b和c包含1到50个元素，含1和50。a、b和c中每个元素都包含1到50个字符，含1和50。a、b和c中每个元素都只包含字符 0到9。a、b和c所表示的单元格中，每个数字至多出现两次。 Examples:0)00, 00 00, 00 11, 22这个例子中没有满足所有条件的挑选方案1)00, 0000, 0012, 21这个例子中没有满足所有条件的挑选方案2)00, 0000, 0000, 00Returns: #., .# 3)00, 00 00, 00 01, 22Returns: .#, #. 4)001, 100 000, 000 001, 102Returns: .#., #.# 5)0010, 0000 0000, 0000 0010, 1022Returns: .#., #.# 前三名解题思路第三名: 楼天城我此次比赛其实没有什么值得分享的题目，就写这一个自以为发挥还过得去的题目吧。其他问题我觉得留给年轻人吧，呵呵。Finalsround1_hard: 由于Round1时在500分题目上浪费了许多时间，我打开1000分题时只有20分钟，不过幸运的是我很快想到了正确的做法。1000分题目的描 述很长，不过分阶段的博弈题目描述其实已经告诉选手这题的做法了。首先，如果没有第一阶段（确定企鹅的方向的过程），那么这题就是经典的NIM问题。所 以，只要把这个NIM值也作为状态进行动态规划即可。不过这题的Sample很弱，许多选手包括我都由于一些小错误造成了不小的损失。 第二名: 俞华程我一些题的解题过程：online round由于比较早，题目我都记得不是特别清楚了，所以就写写onsite的吧。Final Round 1:Easy:这题既然是Easy，它就应该比较简单：直接枚举十字架中心，计算左右上下分别能取多少格子，然后乘起来，复杂度是立方的。其实也很容易用部分和做到平方的复杂度，只不过这里没有这个必要。Medium: 这题个人认为属于不错的Medium。比赛当时，看完题和数据范围，第一想法就是状态压缩动态规划。记录当前格子往前数一行加一格共m+1个格子是否选了，然后转移只需枚举当前格子是否选择，还有换行的时候要看一下当前行是否满足人数要求。但是这个算法写起来比较复杂，而且一旦出错了，非常难调试。由于m只有15，并且一行的人数是固定的，好像一行的状态不是很多，然后打开计算器算了一下C(15, 8)差不多6400多。每次记录一行的状态，枚举下一行的状态再算上行数，似乎有点大。突然想到选出来的格子不能相邻，这样状态数就巨少了，才三位数。于是就毫不犹豫写了。（一个小插曲，我一开始把n看成了50，再加上没有滚动，数组就开小了。本来这题似乎是分数最高的或者第二高的，结果到快结束才发现重交了一下只有1xx的分了。）challenge的时候看了xreborner的程序，然后发现我的程序似乎写长了。主要是生成有效状态那个部分直接for (i = 0; i (1 m ); i +) 差不多5行就搞定了，而我却写了个dfs。Hard:由于第二题写完的时候，分数暂时排在第一还是第二，这题就求稳写了个不高不低的分数，不过似乎后来一些人resubmit或者fail了，本题最终排名还是可以的。企鹅定向好了以后，相当于是把一段路分成了若干段，每段互不干扰，每次玩家可以把一段路减少一个值，不能动的玩家输。假设已经定好向了，很容易发现是一个典型的游戏论的题，暴力算出每个状态的sg函数，然后异或一下即可。注意到一个状态最多能到50个其他状态，因此一个状态的sg函数不会超过50。现在就是要给企鹅定向，这也是一个博弈问题。如果某一段两侧的企鹅朝着两个方向，那么这一段就不能被访问。可以用动态规划解决，状态是前i段，上一个企鹅的朝向，前面所有能被访问的段的sg函数异或值，只要想清楚，还是比较好写的。由于第二题resubmit，第三题分数不高，system test前排第6还是第7。Final Round 2:比赛开始前5分钟进room的时候看到三题分数都比正常要大的时候，就想到这可能是用来给Round 1失误的人翻盘的。然后也没怎么想就开始比赛了。Easy:刚开始看到是300(还是275?)，觉得可能比较难。看完题以后，想了想，写了写。发现一下子就写完了，程序很短，在犹犹豫豫之间交了，觉得会不会是我想错了。结果一看room summary，已经交了一堆了。Medium:看完题，发现这题果然比普通的500要难。想了一会儿觉得贪心是对的。就是如果存在一个点的度超过其他三个加起来，那么显然直接其他三个往它连满就是唯一的最大值。否则，我觉得一定可以做到所有点的度加起来除以2取下整这么多条边。这样，我只要保证任何时候取一条边之后，不会有一个点度大过其他三个加起来就行了，答案一定不会变小。这样一条边一条边取过来，每次取尽量多，并且满足上一个条件即可。但是，我在比赛当时一个细节想错了，我一开始以为如果当前取的这条边的两个端点有一个度是4个当中最大的，那么可以随便连边。但这个结论显然是错的，比如7 6 8 4，7和6不能乱连，如果连了6条以后，8的度就超过其他三个加起来了。杨弋发现了我的错误然后把我的500 cha了这题也是我6题中唯一没有过的题。Hard:这题算法很明显就是2-sat，算了一下复杂度，觉得稍微有点大，比较危险。不过暂时想不到别的方法，就直接写了。写啊写，写啊写写完了，然后改了1个bug就过了样例。还是觉得比较危险，想想也不差这点分了，还是先测一些大数据再交好了。一开始测了一个全白的，1.8秒加了个小优化1.6秒觉得很可能会挂，就用各种方法生成了一些大数据来测，发现要不是无解，要不就只要1秒。既然没有发现会TLE的，那就交了吧。交完发现好像还没有别人交，又想了想，发现全白似乎基本上是最慢的数据了。事实证明最后的确也过system test了。第一名: 杨弋 Overview比赛当天的状态相当不错，就是那种感觉自己的思维很活跃的状态，而且编码准确率也很高，具体的体现就是二试第3题，写了279行，虽然编码速度不算快，但是很稳稳当当地可以通过，整场比赛几乎没有什么失误。题目是TopCoder平台上举办一贯的质量，相当不错。至于难度，我觉得比较适中。平心而论，即使是题目分数异常高的二试，难度也比不上某些最难的Single Round Match。而这样一个难度就更需要稳定的发挥了。有些幸运的是那天我达到了我最好的状态。在比赛策略上，我采取了自己很习惯的策略，就是按顺序一题一题地做。作出这样的决定，一是因为很习惯，二也是因为，我感觉自己在比赛开始15分钟以后，直到结束前15分钟，这中间的45分钟时间状态比较好。所以把medium甚至hard放在这样一个时间区间里面，做起来会比较舒服。而easy正好可以起到一个热身的效果。当然，这样的策略在某些medium特别难而hard又特别简单的Single Round Match里面有可能会栽跟头。但是在这次的有道决赛里，题目难度的梯度挺明显的，这样的顺序应该没什么问题。Challenge阶段一直是我的弱项，每每在这个阶段被人超越。其实我也劝说过自己，只要自己有大于三分之一的把握觉得自己可以challenge掉某个代码，就应该立刻下手，因为这样得分的期望是正的。但是在大赛的时候，还是会选择谨慎地读完程序再challenge。这就让我几乎一无所获。实际上，我唯一的收获是在二试的challenge阶段末期，challenge掉最终第二名的yuhch123的medium的代码。当时只是感觉rating低的选手的代码被翻了无数遍，有错的早就被challenge掉了，所以抱着试试看的态度看看yuhch123的代码，结果竟然真的发现程序有问题了。（关于这个challenge熟人的事情，很多人说会掉rp。我觉得要是这样掉rp的话，最终system test的那台电脑的rp岂不是要掉到负无穷了。反正错的代码总是错的，challenge掉一个程序其实并不会导致那个人的分数额外减少，只是自己的分数增加而已）Final Round 1, Easy题目大意是在一个01矩阵里数十字架。十字架的意思是某五个元素，其中有个元素在中间，它的正上，正下，正左，正右方各有一个元素，且它们五个的数值一样。这题的算法从O(n2)到O(n6)有很多很多种。既然n是50，我比赛的时候选择了实现比较简单，idea也很直观的想法：枚举十字架的中心元素，然后统计它上，下，左，右四个方向的同值元素的个数，这四个数字相乘就是以这个元素为中心的十字架个数，再累加一下就是答案了。时间复杂度是不好也不坏的O(n3)。话说回来，我的实现实在不算很简洁，challenge阶段看别人代码的时候就深深地orz了，大家好像都比我的代码短不过这题我最终得分还是说得过去的，可能是因为选择了一个思维难度和实现难度都很小的算法吧。就是做起来感觉特别顺，虽然代码写丑了，也还是不算慢Final Round 1, Medium题目大意是说，有一个N行M列的座位，让你往里面塞人，第i列要塞恰好Ki个人进去。另外要求你塞的任意两个人不能相邻。这里相邻指的是一个人坐在另一个人周围的8格之一。N不超过15。这题的基本思路其实不是很难。就是用f(i,S)表示，第i列的集合S表示的那些行里塞了人，且第1i-1列已经被按照题目要求塞好人的方案数。那么f(i+1,T)就等于所有满足“在第i列的S所表示的行和第i+1列T所表示的行里塞了人之后没有出现相邻情况”的f(i,S)的和。具体实现却要注意很多问题。首先第一点是时间问题。如果仅仅按照上面的定义去做的话，考虑到表示S需要用N个bit，时间复杂度会高达O(4NM)，如果这样的话就太慢了。最朴素的优化是事先筛去那些饱含相邻行的集合（它们肯定不会出现），并且把剩下的集合按照元素个数分好类。这样，最坏情况好像是N=15，且Ki=4的情况（记不太清了），这时候，能拿来当S的集合有300多个。其他情况能拿来当S的集合的个数就更少了。这样，时间复杂度就在可以忍受的范围内了。然后还有一些实现技巧，比如位运算。可以用一个0到32767的整数表示，整数的二进制表示的右数第i位为1表示此集合包含第i行。判断一个集合本身不包含相邻两行，可以简单地写成(a&(a 1)+(a&1)；看两个集合是不是可以作为相邻两列出现，可以写(a&b)=0 & (a|b)&(a|b) 1)= = 0，等等。当然，比赛的时候不会太多地考虑简化代码，我的代码在细节上没有完全使用上述技巧，但因为是一气呵成，完成得相当迅速。此外这题还有另一种写法。大致的思路是用f(i,j,S)表示第1i-1列以及第i列的前j行都已经塞好人，并且第i列的前j行和第i-1列的后N+1-j列的塞人情况可以用集合S表示。这样，状态转移就从之前的O(2N)以及优化后的大约O(S的个数)变成了地地道道的O(1)。代码也不会变长多少，但是个人觉得，可能会略微容易写错一点点。如果选择这种做法，最好还是多分配一点时间想清楚算法细节再开始编码。Final Round 1, Hard题目是说，一个一维棋盘上有N（30000以内）个格子，上面放了一些企鹅（50个以内）。一开始每个企鹅都没有确定方向。玩家1和玩家2轮流行动。每次行动是这样的：如果存在没有确定方向的企鹅，那么选取最左边的企鹅并选择它头朝左或者朝右；如果不存在没有确定方向的企鹅，那么就选取任何一只企鹅，让它向前走若干步，有一个可选择的步数列表（步数不超过50），你可以在列表里选择一个步数然后让企鹅走这么多步。然而，企鹅不能走出棋盘，也不能走过任何一个被企鹅碰过的格子。谁无法行动谁就输了。题目描述就很长，所以需要仔细分析。首先，整个棋盘可以被看成是被这N只企鹅分成了N+1块，我们可以选择让第i只企鹅头朝着第i块棋盘或者第i+1块。然后，一块棋盘被一只企鹅面对着还是两只企鹅面对着是没有区别的。因为移动左边的企鹅向右移动K步和移动右边的企鹅向左移动K步的后果是等价的。做这道题需要一些组合游戏（combinatorial game）方面的基本知识。在这里做一点点简单的介绍：一个两个人轮流走，然后有很多个状态，每个人可以从当前状态走到它的某个后继状态，而且不存在从某个状态走回它自己的情况。最后谁无法行动（处在一个没有后继状态的“死”状态）谁就输了。这是一类通常的组合游戏。对于这类组合游戏，我们定义一个状态的SG函数值为，最小的不是它的后继状态的SG函数值的非负整数值。那么，不难推出的一个简单结论是，SG函数为0的状态是必败态，其他状态是必胜态。有一个关于SG函数的重要结论：如果我们把几个这样的组合游戏“加”在一起，规则变为每次玩家需要在某个游戏中走一步，则组合得到的游戏为这几个游戏的SG函数的按位异或值。回到我们的游戏。棋盘的每个块相当于一局独立的小组合游戏。两个人首先是通过博弈选择这些块的一个子集，接下来先手是否能获胜我们就可以直接通过SG函数来判断了。因此，我的算法是这样的：用f (i,j)表示，如果确定了第i-1只企鹅的方向以后，已经选择的棋盘块的SG值的异或为j，且第i-1只企鹅头是朝右的，那么当前玩家能否获胜；再用g(i,j)表示第i-1只企鹅头朝左的情况。那么就能得到动态规划的方程：f(i,j) = not g(i + 1,j xor sg(i) or not g(i+1,j xor sg(i+1);g(i,j) = not f(i+1,j) or not g(i+1,j xor sg(i+1);其中sg(i)表示第i块的SG值。注意到企鹅最多一次走50步，那么每个块的SG函数值最多也就是51，它们怎么抑或，都是063内的数。所以时间复杂度关于企鹅只数是线性的。Final Round 2, Easy这是我两试放在一起看，代码最短的题。题目给出了一个有趣的定义，是说一个字符集大小为K的串，串长度为N。题目要求，如果串的第i位和第j位相同（i y2有边，就一定有y1-x2的边。通过一次归纳法可以得到这个结论。当然，不用这个结论应该也能用类似的算法做出这题。官方答案与点评题目: CountingCrosses:Topcoder官方解法:我们可以穷举所有十字架的交点E，并计算给定交点E时有效的十字架个数。当给定交点E时，A，B，C，D需要满足下列条件：1）A和E同色，并在E的上方2）B和E同色，并在E的下方3）C和E同色，并在E的左边4）D和E同色，并在E的右边计算A，B，C，D可能的位置总数，分别记为c(A)，c(B)，c(C)，c(D)，则给定E时，有效十字架个数是 c(A) c(B) c(C) c(D)。c(A)，c(B)，c(C)，c(D)可以直接穷举计算，所以本题的一个简单解法如下：public class CountingCrosses public int count(String grid) int res = 0; int N = grid.length, M = grid0.length(); for (int i=0; i N; i+) for (int j=0; j M; j+) int A = 0, B = 0, C = 0, D = 0; for (int x=0; x i; x+) if (gridx.charAt(j) = gridi.charAt(j) A+; for (int x=i+1; x N; x+) if (gridx.charAt(j) = gridi.charAt(j) B+; for (int y=0; y j; y+) if (gridi.charAt(y) = gridi.charAt(j) C+; for (int y=j+1; y M; y+) if (gridi.charAt(y) = gridi.charAt(j) D+; res += A * B * C * D; return res; 有道点评：这题比较简单，供大家热身:) 题目: YoudaoInterns(DisobidentChildren):Topcoder官方解法:这是一道标准的动态规划问题。有两个地方需要注意：1）使用位操作来降低代码量，并提高代码性能2）充分优化你的解法，因为原始解法需要230 150左右的运算量，会在系统测试时超时。但是也没有必要优化到最优，因为目前这种比赛形式，解题时间很影响得分。首先，每排的状态可以用二进制位掩码来表示，某bit位是1，则该位置有一个实习生，0则代表没有。比如当M=5时，21 = (10101)2则表示这一排最左边，中间和最右边各安排了一个实习生。给定实习生数量时，先生成所有可能的座位安排方法。我们可以穷举所有可能的状态，并判断是否存在水平相邻的实习生。用位操作可以简单的写成： (mask & (mask 1) = 0。 部分代码如下： / for each possible number of interns N / arrangements.get(N) is the list of all possible / ways to place N interns in the same row List arrangements = new ArrayList(); for (int i=0; i = M; i+) arrangements.add(new ArrayList(); / iterate through all masks for (int mask=0; mask (1 M); mask+) / ch