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

《有道难题2009决赛题目、前三名解题思路、官方答案与点评》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、"有道难题2009"决赛题目、前三名解题思路、官方答案与点评  "有道难题2009"决赛题目FinalRound1题目:1.1CountingCrosses(easy)ProblemStatement:MxN个点构成了一个矩形网格，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

2、个字符如果是’W’，则表明第i行第j列的点是白色，’B’则代表黑色。返回给定网格中有效的十字架个数。DefinitionClass:CountingCrossesMethod:countParameters:String[]Returns:intMethodsignature:intcount(String[]grid)(besureyourmethodispublic)Constraintsgrid包含1到50个元素，含1和50。grid的每个元素含1到50个字符，含1和50。grid的所有元素包含相同数量的字符。grid的每个

3、元素只包含字符'W'和'B'。Examples0){"BWB","WWW","BWB"}Returns:1只有一个白色的十字架。1){"BWB","WBW","BWB"}Returns:0十字架水平部分和竖直部分的交点一定要和端点颜色一样。图中没有满足条件的十字架。2){"WWWW","WWWW","WWWW","WWWW"}Returns:16中央的4个点有希望成为十字架的交点E，每个点对应4个不同的有效十字架，所以总数是4*4=16。3){"W"}Returns:04){"BWBW","BBBB","WWWW","BWBW"}

4、Returns:4分别以点(1,2)B和点(2,1)W为交点，各对应2个有效的十字架，注意十字架中非端点和交点部分的颜色没有要求。题目:1.2YoudaoInterns(DisobidentChildren)(medium)ProblemStatement:有道最近招聘了一批实习生，给他们安排座位时遇到了一个有趣的问题。办公室有N排，每排有M个座位。为了方便实习生和全职员工更好的交流，安排座位时，我们不让任何2个实习生座位水平，竖直或者对角线相邻。给定一个String[]intern,把intern的每个元素依次拼接起来得到一串以

5、单个空格隔开的数字。这串数刚好有N个，第i个数字表示安排在第i排的实习生数量。请计算满足条件的座位安排方案总数。因为总数可能过大，返回方案总数除以1000000007的余数。Definition:Class:YoudaoInternMethod:numberOfWaysParameters:int,String[]Returns:intMethodsignature:intnumberOfWays(intM,String[]intern)(besureyourmethodispublic)Constraints:M在1到15之间，

6、含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{"2"}Returns:1只有一个方案把2个实习生安排在这一排。1)4{"1"}Returns:4实习生可以被安排在这排的4个座位中任何一个。2)3{"11","1"}

7、Returns:2两种方案如下：X....X..XX..X....X3)14{"21","0"}Returns:0没有方法可以安排这么多实习生在同一排。注意intern代表int[]{2,10}。4)4{"111"}Returns:10题目:1.3SlidingPenguins(hard)ProblemStatement:Jack和Jill在南极研究工作站工作。为了消磨时间，他们经常玩一个游戏。这个游戏在一个包含roadLength个路段的路上进行。比赛开始时，路上有一些企鹅；penguins的第i个元素表示第i个企鹅站在这条路上

8、的哪个路段（从0开始编号）。比赛的规则如下：·Jack和Jill交替进行，Jill先开始，初始的时候，所有企鹅都没有确定方向。·在前N轮，其中N表示penguins中的元素个数，当前的游戏者选择最左边一个未定向的企鹅，并且确定它的方向是向左（面向编