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

admin · 发表于 2010-5-15 00:24:36

欢迎您注册加入！这里有您将更精采！

您需要登录才可以下载或查看，没有账号？注册

x

"有道难题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","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: 0

4) {"BWBW", "BBBB", "WWWW", "BWBW"}
Returns: 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: YoudaoIntern
Method: numberOfWays
Parameters: int, String[]
Returns: int
Method 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 {"2"}
Returns: 1
只有一个方案把2个实习生安排在这一排。

1) 4 {"1"}
Returns: 4
实习生可以被安排在这排的4个座位中任何一个。

2) 3 {"1 1"," 1"}
Returns: 2
两种方案如下：
X.. ..X
..X X..
X.. ..X

3) 14 {"2 1","0"}
Returns: 0
没有方法可以安排这么多实习生在同一排。注意intern代表int[] {2, 10}。

4) 4 {"1 1 1"}
Returns: 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: SlidingPenguins
Method: determineWinner
Parameters: 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,2}
Returns: "JILL WINS"
Jill 会在她的第一步将这只企鹅方向定为左。因为所有的企鹅都已经被确定方向，Jack 不得不将这只企鹅向前滑行1或2步。不管他怎样做，Jill的下一步都可以将这只企鹅滑行到片段0，然后Jack无法做出合法的移动。

1) 6 {3} {1,2,3}
Returns: "JACK WINS"
不管 Jill 将这只企鹅如何定向，Jack都可以移动这只企鹅使得Jill输。

2) 6 {0,5} {1,3}
Returns: "JACK WINS"

3) 15 {1, 4, 9, 12} {2, 5, 4}
Returns: "JILL WINS"

4) 1234 {1,35,82,193,203,299,303,388,509,684,718,994,1111,1223} {1,4,8,3,91,12,40,31,13}
Returns: "JILL WINS"

Final Round 2
题目: 2.1 TheHieroglyphs (easy)
Problem Statement:
   象形文字H[0],H[1],…,N[n-1]组成的长度为n的序列称为一个句子。如果句子中不存在两个下标i和j（0 < = i < j < n - 1），使得句子中的第i个元素H和第j个元素H[j]是同一个象形文字，且H[i+1]和H[j+1]是不同的象形文字，那么这样的一句话称为是 “严格的”。

假设有k个象形文字，请计算长度为n的序列中有多少个是“严格的”。
Definition:
Class: TheHieroglyphs
Method: count
Parameters: int, int
Returns: long
Method signature: long count(int n, int k)
(be sure your method is public)
Constraints:
n 和k 的取值在1到18之间，含1和18。
Examples:
0) 7 1
Returns: 1
这里只有1个象形文字，所以只有1种句子，且是“严格”的。

1) 1 7
Returns: 7

2) 4 2
Returns: 6
我们用A和B表示这2种象形文字，那么能够构造出的长度为4的句子为：AAAA、BBBB、ABBB、BAAA、ABAB、BABA。

3) 2 4
Returns: 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: SlidingPenguins
Method: determineWinner
Parameters: 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,2}
Returns: "JILL WINS"
Jill 会在她的第一步将这只企鹅方向定为左。因为所有的企鹅都已经被确定方向，Jack 不得不将这只企鹅向前滑行1或2步。不管他怎样做，Jill的下一步都可以将这只企鹅滑行到片段0，然后Jack无法做出合法的移动。

1) 66 {3} {1,2,3}
Returns: "JACK WINS"
不管 Jill 将这只企鹅如何定向，Jack都可以移动这只企鹅使得Jill输。

2) 6 {0,5} {1,3}
Returns: "JACK WINS"
不管 Jill 将这只企鹅如何定向，Jack都可以移动这只企鹅使得Jill输。

3) 15 {1, 4, 9, 12} {2, 5, 4}

4) 1234 {1,35,82,193,203,299,303,388,509,684,718,994,1111,1223} {1,4,8,3,91,12,40,31,13}
Returns: "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: OneOfEachKind
Method: choose
Parameters: 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", "00"}{"00", "00"}{"12", "21"}
这个例子中没有满足所有条件的挑选方案

2) {"00", "00"}{"00", "00"}{"00", "00"}
Returns: {"#.", ".#"

3) {"00", "00"} {"00", "00"} {"01", "22"}
Returns: {".#", "#." }

4) {"001", "100"} {"000", "000"} {"001", "102"}
Returns: {".#.", "#.#" }

5) {"0010", "0000"} {"0000", "0000"} {"0010", "1022"}
Returns: {"..#.", "#..#" }

前三名解题思路
第三名: 楼天城
我此次比赛其实没有什么值得分享的题目，就写这一个自以为发挥还过得去的题目吧。其他问题我觉得留给年轻人吧，呵呵。

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表示的那些行里塞了人，且第1~i-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 ))== 0；统计一个集合的元素个数，可以用递归式bitcount(a)=bitcount(a>>1)+(a&1)；看两个集合是不是可以作为相邻两列出现，可以写(a&b)==0 && ((a|b)&((a|b)< < 1))= = 0，等等。当然，比赛的时候不会太多地考虑简化代码，我的代码在细节上没有完全使用上述技巧，但因为是一气呵成，完成得相当迅速。

此外这题还有另一种写法。大致的思路是用f(i,j,S)表示第1~i-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，它们怎么抑或，都是0~63内的数。所以时间复杂度关于企鹅只数是线性的。
Final Round 2, Easy

这是我两试放在一起看，代码最短的题。题目给出了一个有趣的定义，是说一个字符集大小为K的串，串长度为N。题目要求，如果串的第i位和第j位相同（i < j），且第j位不是最后一位，则第i+1位就必须和第j+1位相同。问符合条件的串有多少个。

算法是什么样子呢？考虑这个串前x个字符是各不相同的（就有K!/(K-x)!种方案），而第x+1个字符与前面发生了重复（可以选择与前面的x个字符中的任何一个产生重复），而从第x+2个字符开始，后面都要受到题目条件的限制，有唯一的填法了。这也就是本题的计算公式。

Final Round 2, Medium

这题是说有四类东西，分别有a,b,c,d种。任取两个不同的东西组成一组可以得1分，问你得到最高分的方案。输出的顺序是 a+b,a+c,a+d,b+c,b+c,c+d，如果有多个方案需要字母序最大（即输出最前面a+b尽量大，a+b相同的情况下a+c尽量大……）。

本题是这次比赛里正确做法最多的一题，同时也是一道错误人数很高，错误种类很多的题目。我先说我的算法，毕竟我是这题做得最快的嘛

首先，如果某种东西比另外三种东西的总和还多，那么就去掉一些使得剩下的个数与另外三种东西的总和一样多，这显然是不影响结果的。这样，答案就可以确定是 (a+b+c+d)/2向下取整了。注意是向下取整，因为输入2 1 1 1这样的情况是可能的。然后，我们二分查找答案里的每个数字，基于这样一个事实（以下用二分查找a+b组的个数的情况举例）：我们定义 valid(a,b,c,d)为true当且仅当四类东西个数为a,b,c,d时存在一种取法使得得分就是(a+b+c+d)/2向下取整。那么，如果 valid(a-k,b-k,c,d)是true，那么就存在一种取法(x1,x2,x3,x4,x5,x6)可以把(a-k,b-k,c,d)取完或者取到只剩一个东西；那么存在取法(x1+1,x2,x3,x4,x5,x6)可以确保valid(a-k+1,b-k+1,c,d)为true。这样可以大致说明二分查找的正确性，我们每次查找最大的保证剩下数非负且valid的取的个数就行了。

还有几种值得一提的做法。首先是一种在程序逻辑结构上比我更合理的做法：实现一个函数f(a,b,c,d)表示(a,b,c,d)情况的最高得分。这可以通过一个不太困难的贪心实现。然后不需要事先降低特别高的某一项什么的，只需要逐一二分，然后用f(a-k,b-k,c,d)+k == f(a,b,c,d) 作为valid(a-k,b-k,c,d)的替代品即可。

然后还有一种类似的二分算法，但是适合对于前面的贪心不太放心的选手使用，那就是二分结果，然后用网络流去实现那个f(a,b,c,d)。当然这是比较浪费时间的做法了，但是在赛场上，安定也是一个决策目标。此外还有不用二分的贪心算法，旨在直接算出每次的取值。比如取a和b的组合，假设我们取了k个，那么k不能超过a，不能超过b，如果(c,d)的较大值是 c的话，那么k不能超过(a+b+d-c+1)/2，d的情况同理。在满足这些限制的情况下，k尽量往大了取就好。当然，我如果这里疏漏了什么情况也是可能的，毕竟我只是challenge的时候看代码看到这个的。我觉得这个算法应该是这题最究极最合理的解法了，当然这个算法也比较需要认真细致。相较而言，二分显得简单粗暴但是安定很多。BTW：yuhch123的这题就是挂在贪心写不小心了……

Final Round 2, Hard

这题的题意看起来和Round 1的Medium有联系，当然算法是无关的。题目是给你一个最多50x50的矩阵，里面每格可以是1~999的一个整数，或者没有整数。每种整数出现最多2次。你要选择这些格子的一个子集，使得

(1)这个子集包含了每个出现了的整数恰好1次；
(2)这个子集中不包含相邻的两个格子，这里相邻说的是某格子是另一个格子周围的4个格子之一；
(3)这个子集是所有符合条件的子集中字典序最小的一个，注意“选取”是用比“不选取”小的字符所表示的。

对于这类题目（求字典序最小解），一类通用的处理方法是写一个判断是否有解得函数，然后从解的第一位开始枚举看看能不能取，如果取了以后还有解的话就取吧。

我的算法不太优秀，实现起来也麻烦，写在这里仅供大家参考吧。从还剩58分钟左右开始写这题，一直写到还有15分钟的时候才写完。当然，这是我前面所谓的状态最好的一段时间。但是这状态最好只是保证了我把这么丑陋的代码稳稳当当地写了出来而且写对了。至于算法的质量，我觉得有很多值得商榷之处。
首先，一开始我理解错了题意，我把选取这些格子的一个子集理解成了选取有数字的格子的一个子集。当然这样是过不了样例的……不然还不知道我能不能发现这个重大错误（这也就是我为什么说我“几乎”没有失误的原因了）我的算法的第一步是优先选取只出现了1次的数字。把它强行标记为已经选取。而这样的已经选取的格子周围4格强行标记为不能选取。注意标记某格为不能选取以后可能会又导致某个本来出现2次的数字变成出现一次；又要注意如果某种数字本来出现不是0次，而因为不能选取的缘故出现次数变成0了，这和根本没有出现的数字不能等同对待，而是应该直接算作无解……

然后取完这些以后，就来到了我们算法的核心——2-SAT。因为每种数字都出现了恰好两次，如果某种数字我们取了两个格子中的某一个，那么与这个格子相邻的别的数字就不能取这个相邻的格子了。那么我们给每个数字准备两个节点，假设刚才说的两个数字是a和b，分别对应格子a1,a2和b1,b2，相邻的格子是a1和b1，那么我们就从a1连一条有向弧到b2，即选了a1就被迫要选b2。那么，如果对于某个a，从a1可以沿一条路径走到a2，又从a2可以沿一条路径走到a1，那么就无解了。否则，如果a1不能沿一条路径走到a2，我们就可以选取a1；反之亦然。这样，我们从头往后，每找到一个没有确定选哪个的数字a，就检查一下是选a1还是a2，直到全部确定。

理解正确题目以后，我就得多考虑一种情况了：如果我要选一个空格，那么就要check一下周围4个格子有没有数字，选取这个空格相当于决定选取周围4个格子里数字的另一个出现地方。那么如果选取那个格子不可行，或者这个空格周围4个格子已经有被选过的，这个空格就不能选了，否则就选上。

这样的话，回头看看整个算法，我感觉我的第一步是毫无必要的。在后面的每一步里都出现某个数字的两个格子只有一个可以选择的情况，比如已经确定选哪个，或者a1会连到a2但是a2不连到a1的情况等等。所以好像可以使用一个更简单的方法更通用性地处理这些步骤，比如给每个只出现一次的数字a一个“虚格子”a2，而实际存在的格子是a1。那么我们在算法的一开始就强行选择a1，如果a1走到了a2，就出问题无解了。这样的话，代码实现上会简单很多吧。

最后注一下，由于2-SAT构图的对称性，如果选取a1以后导致某个数字b的b1和b2两个格子都被选取（从而有矛盾出现），那么a2一定会被选取（从而导致我们上面的算法可以检查到矛盾），因为如果x1->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 = grid[0].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 (grid[x].charAt(j) == grid.charAt(j)) A++;

      for (int x=i+1; x < N; x++)
      if (grid[x].charAt(j) == grid.charAt(j)) B++;

      for (int y=0; y < j; y++)
      if (grid.charAt(y) == grid.charAt(j)) C++;

      for (int y=j+1; y < M; y++)
      if (grid.charAt(y) == grid.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++) {
// check if arrangement is valid
if ((mask & (mask << 1)) != 0)
   continue;

// count the number of bits in mask
int tmp = mask, cnt = 0;
while (tmp > 0) {
   tmp &= (tmp - 1);
   cnt++;
}

arrangements.get(cnt).add(mask);
  }

为了估算时间消耗，我们可以看M=15时，打印每种实习生数量时对应的座位安排方案数。可以发现，当M=15，实习生数量是4，这时候方案总数最多，为495。

用List < I nteger> rows存储每排的实习生数量。定义F(rowNum，ind) 表示安排好第0排一直到第rowNum排的有效方案数，并且第rowNum排的安排方案是arrangements.get(NrowNum)中的第 ind种(从0开始计数)。

我们可以按照rowNum从小到大的顺序来计算F。在rowNum = 0时，所有的F值是1。递推计算F(rowNum，ind)时，需要用到F(rowNum - 1，i)，i取遍第rowNum – 1排的方案数。计算的核心是判断2个掩码对应的安排方案是否可以放在相邻两排(即没有水平，竖直，对角相邻)。用位运算可以方便的表达成：(x & y) == 0 && (x & (y < < 1)) == 0 && ((x < < 1) & y) == 0。

动态规划递推计算代码如下：

final int MOD = 1000000007;
  int[][] F = new int[rows.size()][500];

  // calculate for row 0
  for (int i=0; i < arrangements.get(rows.get(0)).size(); i++)
F[0] = 1;

  // calculate for other rows
  for (int i=1; i < rows.size(); i++) {
int j = 0;
for (int x : arrangements.get(rows.get(i))) {
   int k = 0;
   for (int y : arrangements.get(rows.get(i - 1))) {
      if ((x & y) == 0 && (x & (y << 1)) == 0 && ((x << 1) & y) == 0)
      F[j] = (F[j] + F[i - 1][k]) % MOD;
      k++;
   }
   j++;
}
  }

最后的总方案数就是所有可能ind对应的F(last,ind)的总和，last表示最后一排的行号：

int res = 0;
for (int i=0; i < 500; i++)
   res = (res + F[rows.size() - 1]) % MOD;

这种解法的运算复杂度大约是 495 * 495 * 150 = 36,753,750，一定可以在几秒内完成，为了确信不会超过2秒的时间限制，可以测试下M = 15， 150排并且每排安排4个实习生这种情况。
有道点评:
经典动态规划，每排的选择只和上一排座位安排有关。此外，本题解法代码中F可以精简成一维数组，有些DP问题不做这样的优化会爆掉内存。位操作在本题中有很精彩的应用，感兴趣的同学可以阅读《hacker's delight》。
题目: SlidingPenguins:
Topcoder官方解法:
为了更好的理解这个解答方法，你需要去了解一些组合游戏理论的基础知识：winning/losing positions, sum of games, grundy function。如果你不知道上述提到的这些话题，在你自己阅读这篇解答之前请先看这个指导。

让我们首先来解决一个这个游戏饿简化版本，也就是当所有的企鹅初始的时候都被设定了方向的问题。注意这些企鹅将整条路分成了一些片段，每个片段是两个连续企鹅中间的一段或者是一个企鹅和路的尽头中的一段。尽管如此，依据这些企鹅的方向，有些片段可以被这些企鹅访问到（我们称这些片段为活跃的），而有一些则不能被访问。比如，假设如下的这张图(箭头表示企鹅和他们的方向，灰色的单元格表示活跃的片段)。

在这种情况下，有六个片段长度分别为2，1，2，3，1和3.但只有4个片段是活跃的，长度分别为1，2，1和3。一些活跃的片段可以被两个企鹅访问，而某些则只能被一个企鹅访问，但是因为所有企鹅可能移动的步数是一样的，所以这个对我们没有什么影响。

在解决完这个简单的游戏之后，我们回到原始的问题。现在唯一一个不清晰的阶段是如何设定方向。在方向被设定好之后，唯一重要的事情就是定义这个结果为所有活跃片段Grundy numbers的XOR。这允许我们将这个游戏按照通常的组合游戏理论转化成如下几种状态：

- pos – 当前被确定方向的企鹅个数（pos的特殊值是N，N是企鹅总数，用来表示所有的企鹅都已经被确定方向了）

- fun – 编号为pos-1的企鹅左边所有的活跃片段的Grundy numbers的XOR值。（非常重要的一点是至多只有50个可能的步数，所以Grundy numbers 不会超过50，而且他们的XOR不会超过63；并且请注意上述提到的活跃的片段是已经确定了的，不会因为后面的企鹅的方向而发生改变；当pos = 0时，为了方便我们让fun也为0）

- last – 最后一个企鹅的方向，也就是编号为pos–1的企鹅的方向（0表示 “面向左”， 1表示“面向右”; 当pos = 0时，为了方便我们让last也为0）。

- 让我们实现一个递归的函数，以pos, fun 和last为参数，并且返回一个布尔值——下一步走的这个选手的胜负结果。（true表示“这个选手获胜”，false表示“这个选手失败”）。这个函数是这样进行的：

- 如果pos = N，也就是所有的企鹅都被定向了，首先检查编号为N-1的企鹅的方向（也就是last）。如果它被定向为右边，那么添加一个活跃片段，即从这个企鹅到这条路的尽头，然后我们照此修改fun的值。之后，如果fun是正的，我们返回true，否则返回false。

- 如果pos < N, 从这个状态开始有两个可能的移动，我们可以将当前的企鹅定向成左或者右。而对每一个方向，我们都计算出新的状态并且调用我们的函数来确定新状态的答案。如果至少有一个结果时“false”，那么我们返回true，放走我们返回false。

剩下的就是在我们从给定状态走了任意一步可行的移动之后，如何计算新状态。这其实非常简单，如果我们将这只编号为pos的企鹅定向为左，那么添加了一个新的活跃片段（如果pos>0, 则是编号为pos-1和pos之间的片段，如果pos=0，则是路的开始到编号为0的企鹅之间的片段）。如果我们将这只编号为pos的企鹅定向为右，那么当且仅当编号为 pos – 1的企鹅面向右时，它添加上述同样的一个活跃片段。

可能的状态至多有50 * 64 * 2个，所以在利用添加了备忘录的方式来实现函数计算，它会运行的非常快。

述算法的Java实现如下：

import java.util.*;

public class SlidingPenguins {

int[] grundy;

int[][][] memo;

int[] penguins;

int N, roadLength;

// the function to determine the outcome from the current state

boolean win(int pos, int fun, int last) {

      // all penguins are oriented

      if (pos == N) {

         if (last == 1)

            fun ^= grundy[roadLength - 1 - penguins[N-1]];

         return fun > 0;

      }

      // take care of memoization

      if (memo[pos][fun][last] != -1)

         return memo[pos][fun][last] > 0;

      // calculate the lengths of the active segment that can be created

      int prev = (pos == 0 ? -1 : penguins[pos - 1]);

      int diff = penguins[pos] - prev - 1;

      // orient the current penguin to the left

      boolean value1 = win(pos + 1, fun ^ grundy[diff], 0);

      // orient the current penguin to the right

      boolean value2 = win(pos + 1, fun ^ (last == 0 ? 0 : grundy[diff]), 1);

      // find the outcome

      if (!value1 || !value2) {

         memo[pos][fun][last] = 1;

         return true;

      } else {

         memo[pos][fun][last] = 0;

         return false;

      }

}

public String determineWinner(int roadLength, int[] penguins, int[] moveLengths) {

      // calculate Grundy numbers for all possible lengths

      grundy = new int[roadLength];

      grundy[0] = 0;

      for (int i=1; i < roadLength; i++) {

         boolean[] was = new boolean[100];

         for (int j=0; j < moveLengths.length; j++)

            if (i >= moveLengths[j])

                  was[grundy[i - moveLengths[j]]] = true;

         grundy[i] = 0;

         while (was[grundy[i]])

            grundy[i]++;

      }

      // initialize

      this.penguins = penguins;

      this.N = penguins.length;

      this.roadLength = roadLength;

      memo = new int[N][64][2];

      for (int i=0; i < memo.length; i++)

         for (int j=0; j < memo[i].length; j++)

            Arrays.fill(memo[i][j], -1);

      // see who wins

      return win(0, 0, 0) ? "JILL WINS" : "JACK WINS";

}

}
复制代码

题目: TheHieroglyphs:
Topcoder官方解法:
让我们按照从左至右每次添加一个象形文字的方法来构造一个严格的句子。当所有用过的象形文字都不同的时候，我们可以自由的进行选择。但一旦我们添加了一个已经被用过的象形文字，剩下的句子就被完全确定了。比如，我们构造的句子以”FABEC”开头，当我们再添加一个”A”得到”FABECA”。很容易发现，这个”A”后面必须紧跟一个”B”因为前一个”A”后面紧跟着”B”。同理，这个”B”后面必须紧跟着”E”。如此下去，这个句子必须看起来是”FABECABECABEC…”，且停止在所需长度的位置。

现在如何计算严格句子的个数的问题已经变得清晰。让我们的句子以i个不同的象形文字开始，接下来跟着重复的象形文字。一共有k种方法来选取第一个象形文字，k-1种方法来选取第二个象形文字（因为他们必须不同），k-2种方法来选取第三个象形文字，……，k-i+1种方法来选取第i个象形文字，然后有i 种方法来选取后面重复的象形文字。所以这样句子的总数当k < i 时为0，而当k >= i时为 k * (k – 1) * … * (k-i+1) * i。把对所有的i，即1 < =i < n计算出来的这些数求和就是答案。哦，对了，我们还忘记了一种情况就是所有的象形文字都不同的情况。这个数当k < n时为0，当K >= n时为 k * (k – 1) * … * (k – n + 1)。加上这个数就得到了最终的答案。

这种方法的Java实现如下：

public class TheHieroglyphs {

  public long count(int n, int k) {

long res = 0;

for (int i=1; i <= n; i++) {

   long add = 1;

   for (int j=k; j > k - i; j--)

      add *= j;

   if (i < n)

      add *= i;

   res += add;

}

return res;

  }

}
复制代码

有道点评:
这道题简单的说就是从1..min(n, k)中枚举i，表示其前i个字符互不相同，得到组合公式C(k, i)*i! =k!/(k-i)!求得这样的串的个数再求和就是答案。
题目: Detail:
Topcoder官方解法:
让我们首先将这个问题简化成计算能够被面试的申请人总数的最大值的问题。如果A,B,C,D中有一个数严格大于剩下三个数之和，比如B > A+C+D。任意一个被B面试的申请人必须被A,C,D中的一个面试，所以B能至多面试 A+C+D个申请人。很容易发现这种情况下最多有A+C+D个人可以被面试。而当A>B+C+D, C>A+B+D, 以及D >A+B+C的情况可以按照类似的方法处理。现在假设没有上述这样的情况，这样我们就能利用下面的引理将面试官的容量用尽（或者几乎用尽）。

引理

让 A < = B+C+D, B< = A + C+D, C< = A+B+D, D< =A+B+C (这四个条件可以统一写成 max(A,B,C,D) < =A+B+C+D – max(A,B,C,D) ，也等价于 2*max(A,B,C,D)< =A+B+C+D )。这样当A+B+C+D是偶数的时候我们可以面试(A+B+C+D)/2个申请人，当A+B+C+D是奇数的时候我们可以面试(A+B+C+D-1) /2个申请人。

证明
我们可以通过将一个申请人的面试官容量减一来安排这个申请人的面试，很容易证明有方法使得上述引理中的条件在修改的容量下仍然是成立的。当A+B+C+D >= 2时，我们可以重复这个过程来得到必须的结果。

不失一般性，我们可以假定A< =B< =C< =D，所以引理中的条件简化为 D < = A+B+C。我们的策略是分配一个申请人给面试官C和D，所以修改后的容量为 A, B, C-1和 D-1。有一些我们需要检查的情况:

A < = B < = C < D。这种情况下 D -1 仍然不比 A , B, C -1小。所以我们需要检查条件D-1 < = A + B + C – 1，这等价于 D < = A +B+C，所以仍然成立。

A< =B< C=D。这种情况 A< = B < = C – 1 = D – 1，我们依旧需要检查条件D-1 < = A + B + C – 1，显然成立。

A < B = C = D。这种情况我们有 A < = C-1 = D-1 < B, 所以我们需要检查条件B< =A+C+D-2。因为B=C=D，条件可被简化成 B < = A+B+B-2 或者A +B >= 2。除了A=0, B=1的情况，条件显然是成立的。而在A=0, B=1情况下 A= 0, B=C=D=1，显然只能再面试一位申请人，所以引理仍然是满足的。

A=B=C=D。这种情况下我们可以让A和B组成AB面试，C和D组成CD来面试，引理仍然满足。

证毕。

现在，当我们知道在各种情况下怎样确定最大的被面试申请人数，让我们找到正确的方法来将将面试官组成对面试。首先我们需要创造足够多的AB对，让我们用 max(AB)来表示AB对的最大个数，用M来表示面试官容量为 A,B,C,D时最多能被面试的申请人数。我们可以选择一个任意的数字x，得到x对 AB，然后计算y —— 容量 A-x, B –x, C, D情况下最多能配成的面试官对数（就是在面试官A和B一起面试了x个学生后剩下的容量）。显然 x + y < = M。如果x + y = M , 则 x < = max(AB) ，因为不然我们已经找到一个解面试了最大可能的申请人，而且还至少有x对AB。并且如果 x + y < M，则x > max(AB)，因为要不然在分配了x个AB对以后我们仍然有能力将剩余的申请人都指派给剩余的容量A – x, B – x, C, D，这样 x + y< M就不满足了。这样我们就得到了一个比较任意一个数x和max(AB)的方法，这就允许我们用二分搜索（如果你不知道什么是二分搜索，这个指导会很有帮助）的办法来确定max(AB)的准确数值。在确定了max（AB）后，我们可以用类似的方法用二分搜索确定max(AC)的值，但是是针对修改后的容量 A – max(AB), B- max(AB), C, D。之后重复这个方法四次我们可以确定其他四个数字max(AD), max(BC), max(BD), max(CD) 的值。

这种方法的Java实现如下：

import java.util.*;

public class Details {

  // the maximum number of applicants for the

  // given array of interviewers' capacities

  public int getNumber(int[] X) {

int sum = X[0] + X[1] + X[2] + X[3];

Arrays.sort(X);

return (2 * X[3] > sum ? sum - X[3] : sum / 2);

  }

  public int[] count(int a, int b, int c, int d) {

// initialize

int[] res = new int[6];

int[] val = new int[] {a, b, c, d};

int M = getNumber(val.clone());

int pos = 0;

// for each i and j assign the maximum number

// of applicants to i-th and j-th interviewers

for (int i=0; i < 4; i++)

   for (int j=i + 1; j < 4; j++) {

      // binary search

      int l = 0, r = Math.min(val[i], val[j]) + 1;

      while (r - l > 1) {

      int x = (l + r) / 2;

      val[i] -= x;

      val[j] -= x;

      int y = getNumber(val.clone());

      val[i] += x;

      val[j] += x;

      if (x + y == M)

         l = x;

      else

         r = x;

      }

      // modify capacities and the value of M accordingly

      res[pos++] = l;

      val[i] -= l;

      val[j] -= l;

      M -= l;

   }

return res;

  }

}
复制代码

有道点评:
这道题目几乎所有答对的选手都是选择了上述二分搜索的办法来做，其实从另一个角度考虑会有一个更加简单的方法。

上述方法首先是先满足被面试总人数最大，再来确定AB，AC，AD，BC，BD，CD对的个数，而我们可以换个角度，先贪心使得AB，AC，AD，BC，BD，CD对的个数尽量大，再通过调整使得被面试的总人数最大。

假设我们有如下两个方法:

ADD(X, Y, XY) 即对容量X，Y，尽可能多的组成XY对。

MOVE(XY, Z, XZ, YZ) 即对XY对的数量，和容量Z，尽可能多的将一个XY对与2个Z转化成一个XZ对和一个YZ对。

我们只需要依次执行

ADD(A, B, AB)
ADD(A, C, AC)
ADD(A, D, AD)
ADD(B, C, BC)
ADD(B, D, BD)
ADD(C，D, CD)
MOVE(AB, C, AC, BC)
MOVE(BC, D, BD, CD)
MOVE(AC, D, AD, CD)
MOVE(AB, D, AD, BD)

最后就可以得到AB,AC,AD,BC,BD,CD对个数为最终答案。

下面我们来证明一下这个方法为什么是对的。首先我们执行六次ADD（）方法就是用贪心的办法来分配面试官，按照AB,AC,AD,BC,BD,CD的顺序依次尽可能的取，得到的结果无法保证所面试的申请人数达到最大值。但我们可以保证至多只有一位面试官的容量没有被用尽，接下来讨论如下几种情况：

- A的容量没有用尽，因为前三条Add（）方法就是尽可能多的分配AB，AC，AD对，还有A剩余，则说明 A > B + C + D，而通过前面的贪心我们已经得到最终答案。

- B的容量没有用尽，很显然AC和AD对数均为0，因为A的容量在AB对时已经用完。那么实际配成对的前三个是 AB, BC, BD，如果还有B剩余，则说明 B > A + C + D，而我们通过前面的贪心也已经得到了最终答案。

- C的容量没有用尽，很显然AD和BD对数均为0，因为A的容量在AC对时，B的容量在BC对时已经用尽。那么实际配成对的为AB,AC,BC,CD，只有 AB对没有用到C。为了使得更多的人可以得到面试机会，我们应该将AB对拆散和两个C组合，得到AC对和BC对。所以通过MOVE(AB, C, AC, BC)进行调整后得到正确答案。

- D的容量没有用尽，AB，AC，BC配对没有用到D，那么我们应该依次拆散BC，AC，AB，将其和D组合以使被面试的人数达到更大。于是通过 MOVE(BC, D, BD, CD)，MOVE(AC, D, AD, CD)，MOVE(AB, D, AD, BD)即可得到正确答案。

这样程序的代码非常简单，效率也更高。
题目: OneofEachKind:
Topcoder官方解法:
这个问题可以被规约到2-SAT的问题。我们首先会解释什么是2-SAT以及如何解决，接下来我们会介绍这个规约的过程。

什么是2-SAT

有布尔变量 x1, x2, … , 也就是可以取值为0(false)和1(true)的变量。有如下一些有用的布尔操作。

x1    x2    not x1    x1 or x2    x1 and x2    x1 => x2
0    0    1    0    0    1
0    1    1    1    0    1
1    0    0    1    0    0
1    1    0    1    1    1

另表达式看起来都是如下形式： E = (y11 or y12) and (y21 or y22) and … and (yn1 or yn2), 其中yij是某个变量xk或者是一个变量的非(not xk)。(x3 or (not x4)) and ((not x1) or (not x3)) 就是这种表达式的一个例子。

2-SAT问题需要找到一个E中所有变量的赋值集合，使得这个表达式E的取值为1(true)。如果这个赋值集合不存在，则无解。

如何解2-SAT

我们可以看到表达式 E1 = (a or b) 和表达式 E2 = ((not a ) => b) and ((not b) => a)) 是等价的。这个表达式E2转化成真实的语言就是”如果(not a)则b，而且如果(not b) 则a”。例如，x1 or (not x2) 和 “如果x1是false，则x1一定是false, 并且如果x2 是true，则x1一定是true” 。

基于上面一段，我们可以介绍一个有向图G。对于表达式E中的每个变量xi在图G中都有两个顶点：一个顶点对应表达式 xi, 另一个对应表达式 (not xi)。因此每一个yij 在图G中都有一个对应的顶点。现在，对于表达式中的每一个括号(yi1 or yi2)，我们在G中添加两条弧：一条弧从(not yi1)对应的顶点指向yi2对应的顶点，另一条弧则从(not yi2)对应的顶点指向yi1对应的顶点。

给定E中所有变量的一个赋值来解决2-SAT，让我们选择一个顶点的结合，让其对应的表达式为真。(也就是对应xi的顶点被选表示xi为true，对于(not xi)的顶点被选表示xi为false)。这个被选择的顶点集合有两个重要的性质。第一个性质是对于任意的xi，对应表达式xi和(not xi)的两个顶点恰好有一个被选中。第二个性质是：如果顶点a被选了，且有一条弧a->b，那么顶点b也必须被选。

通过下面的引理很容易证明上述两个性质足够定义2-SAT的一个实例的解。

引理1：

一个2-SAT的实例被解答当且仅当有可能在对应的有向图中选出一个顶点集合使得如下两个性质都被满足：

1．对于任意一个xi，恰好有xi 和 (not xi)中的一个被选中。

2．如果顶点a被选中且有一条弧a->b, 那么顶点b也被选中。

现在，让我们寻找一个方法来在G中挑选顶点，使得上面被提到的两个性质都得到满足。让我们选择一些变量，首先试图去选择顶点x1，选中以后，我们接下来需要选择所有的y，如果有一条弧x1->y。在选定所有的y以后，我们需要继续选择一些未被选择的顶点z，如果有一条弧从一些已经被选的顶点指向z，继续该过程。总的来世，我们需要选择所有的顶点y，如果在图G中有一条从x1指向y的路径的话。这些顶点可以用图论的任意遍历算法来实现，比如 DFS，BFS。假设我们已经选择了顶点x1和所有它在G中能到达的顶点。这个选择可能会导出矛盾，也就是可能存在一些变量xi，我们选择了xi 和 (not xi) 。如果存在这样的情况，那么x1显然是不能被选的。这种情况下我们要取消选择x1,然后试图去选择 (not x1)。如果x1 和 (not x1) 都会导出矛盾，那么这个2-SAT的实例是无法被解决的。如果至少有一个不会导出矛盾，那么我们可以确定这个选择并且针对另一个未被选择的变量重复这个过程。

下面是一段解决2-SAT问题的伪代码:

While there are variables xi such that both

   vertices xi and (not xi) are not selected

  Choose any such variable xi

  Try to select vertex xi and all vertices reachable from xi

  If there is no contradiction

Continue

  Cancel the selection of vertex xi and of all vertices reachable from it

  Try to select vertex (not xi) and all vertices reachable from it

  If there is contradiction

No solution

End While
复制代码

请注意上面是一段简单的算法描述而没有进行完整的正确性证明。如何进行形式化的证明留给读者作为一个练习。

如何从这个问题规约到2-SAT

对于任意出现两次的数字，我们设立为一个变量。定义当这个变量的值取0时我们选择这个数字的一次出现，变量值取1时我们选择这个数字的另一次出现。对于任意的一个空单元格，我们也设立一个变量，定义当这个变量取0时我们不选它，而当变量取1时我们选它。这样，每一个空的单元格也有了一个对应的变量，当且仅当该变量为1时我们选它。而每个包含有出现两次的数的单元格也有一个对应的表达式(xi 或者 (not xi)，其中xi是对应这个数字的变量)，而这个表达式为真当且仅当这个单元格被选择。

现在让我们设立一个表达式E，E为真当且仅当它描述了一个单元格的有效选择。对于上述要求，我们需要分析每一个相邻的单元格对，并且在E中添加一个括号，具体做法如下：

1.如果这两个单元格中每一个都是空的或者包含一个出现两次的数字，那么他们之中至少有一个不能被选，所以我们添加一个括号((not a) or (not b)),其中a和b都对应变量（表达式）。

2.如果这两个单元格中有一个是空的或者包含一个出现两次的数字，而另一个包含一个仅出现一次的数字。因为每个数字都必须被选择恰好一次，那么第二个单元格必须被选，因此第一个单元格不能被选。所以我们添加一个括号((not a) or (not a))，其中a对应变量（表达式）。

3.如果两个单元格都包含仅出现一次的数字，那么两个都必须被选，因为相邻的两个是不能都被选的，所以这导出了一个矛盾。所以这个题目在这种情况下是无解的。

我们有了一个对于2-SAT实例的完整的定义。如果它无解，那么我们的问题也无解。否则，我们可以找到一个字典序最小的解。这需要在解决2-SAT的问题的时候按照一个恰当的顺序检查变量。更确切的说，我们按照行从上到下，并且每一行中按照列从左到右的顺序进行检查。对于每一个空的单元格（如果对应变量的值还没有确定），我们先试着去选择它（因为这样的结果在字典序中更小），并且只有当我们选择它会导出矛盾的时候，我们才试图去不选它。类似的，对于任意一个包含两次出现数字的单元格（如果这个对应变量的值还没有确定），我们可以首先试着选择这个单元格，当且仅当它导出矛盾时，我们才试图去选择包含这个数字的另一个单元格。

上述算法的Java实现如下：

import java.util.*;

public class OneOfEachKind {

  // this is (relatively) abstract 2-CNF solver

  class Solver {

int varNum;       // number of variables

int[] value; // value of each variable (-1 - undefined, 0 - false, 1 - true)

// each vertex is encoded with pair (var, val), where

// (i, 0) is xi and (i, 1) is (not xi)

int[][] arcCnt; // number of arcs from each vertex

int[][][] arcVar; // vars of all arcs destinations from each vertex

int[][][] arcVal; // vals of all arcs destinations from each vertex

// constructor (it assumes there are at most 10 arcs from

// a single vertex -- this is enough for our problem)

public Solver(int varNum) {

   this.varNum = varNum;

   this.value = new int[varNum];

   Arrays.fill(this.value, -1);

   this.arcCnt = new int[varNum][2];

   this.arcVar = new int[varNum][2][10];

   this.arcVal = new int[varNum][2][10];

}

// add arc to the graph G

public void addArc(int var1, int val1, int var2, int val2) {

   arcVar[var1][val1][arcCnt[var1][val1]] = var2;

   arcVal[var1][val1][arcCnt[var1][val1]++] = val2;

}

// add bracket to the expression E

public void addEquation(int var1, int val1, int var2, int val2) {

   addArc(var1, 1 - val1, var2, val2);

   addArc(var2, 1 - val2, var1, val1);

}

// recursive selection of vertex (var, val) and all

// reachable vertices

// returns false if there's contradiction and true otherwise

public boolean recursiveSet(int var, int val) {

   if (value[var] != -1)

      return value[var] == val;

   value[var] = val;

   for (int i=0; i < arcCnt[var][val]; i++)

      if (!recursiveSet(arcVar[var][val][i], arcVal[var][val][i]))

      return false;

   return true;

}

// tries to select the vertex (var, val) and cancels

// everything if there's contradiction

public boolean tryToSet(int var, int val) {

   int[] tmp = value.clone();

   boolean ret = recursiveSet(var, val);

   if (!ret)

      value = tmp.clone();

   return ret;

}

// return the value of variable var

public int getValue(int var) {

   return value[var];

}

  }

  boolean retFlag = false;

  Solver solver;

  // analyzes two neighboring cells and adds the necessary bracket to E

  void addConstraint(int num1, int var1, int val1, int num2, int var2, int val2) {

if (num1 == 0 && num2 == 0) {

   solver.addEquation(var1, 0, var2, 0);

} else if (num1 > 0 && var1 == -1 && num2 > 0 && var2 == -1) {

   retFlag = true;

} else if (num1 > 0 && var1 >= 0 && num2 > 0 && var2 >= 0) {

   solver.addEquation(var1, 1 - val1, var2, 1 - val2);

} else if (num1 == 0 && num2 > 0 && var2 == -1) {

   solver.addEquation(var1, 0, var1, 0);

} else if (num1 == 0 && num2 > 0 && var2 >= 0) {

   solver.addEquation(var1, 0, var2, 1 - val2);

} else if (num1 > 0 && var1 == -1 && num2 > 0 && var2 >= 0) {

   solver.addEquation(var2, 1 - val2, var2, 1 - val2);

} else addConstraint(num2, var2, val2, num1, var1, val1);

  }

  public String[] choose(String[] a, String[] b, String[] c) {

// parse input and remember occurrences for each number

int[] occ1X = new int[1000], occ1Y = new int[1000];

int[] occ2X = new int[1000], occ2Y = new int[1000];

int N = a.length, M = a[0].length();

int[][] num = new int[N][M];

Arrays.fill(occ1X, -1); Arrays.fill(occ2X, -1);

for (int i=0; i < N; i++)

   for (int j=0; j < M; j++) {

      num[i][j] = 100 * (a[i].charAt(j) - '0') + 10 * (b[i].charAt(j) - '0') + (c[i].charAt(j) - '0');

      if (occ1X[num[i][j]] == -1) {

      occ1X[num[i][j]] = i;

      occ1Y[num[i][j]] = j;

      } else {

      occ2X[num[i][j]] = i;

      occ2Y[num[i][j]] = j;

      }

   }

// introduce variables

int varNum = 0;

int[][] var = new int[N][M];

int[][] val = new int[N][M];

for (int i=0; i < N; i++)

   Arrays.fill(var[i], -1);

for (int i=0; i < N; i++)

   for (int j=0; j < M; j++)

      if (num[i][j] == 0) {

      var[i][j] = varNum++;

      } else if (occ2X[num[i][j]] != -1 && var[i][j] == -1) {

      var[i][j] = varNum;

      val[i][j] = 0;

      var[occ2X[num[i][j]]][occ2Y[num[i][j]]] = varNum++;

      val[occ2X[num[i][j]]][occ2Y[num[i][j]]] = 1;

      }

// add brackets to E

solver = new Solver(varNum);

for (int i=0; i < N; i++)

   for (int j=0; j < M; j++) {

      if (i + 1 < N)

      addConstraint(num[i][j], var[i][j], val[i][j], num[i + 1][j], var[i + 1][j], val[i + 1][j]);

      if (j + 1 < M)

      addConstraint(num[i][j], var[i][j], val[i][j], num[i][j + 1], var[i][j + 1], val[i][j + 1]);

   }

// check if there were two neighboring cells

// with numbers that occur only once

if (retFlag)

   return new String[] {};

// solve 2-SAT

for (int i=0; i < N; i++)

   for (int j=0; j < M; j++)

      if (num[i][j] == 0) {

      if (!solver.tryToSet(var[i][j], 1))

         if (!solver.tryToSet(var[i][j], 0))

            return new String[] {};

      } else if (num[i][j] > 0 && var[i][j] >= 0) {

      if (!solver.tryToSet(var[i][j], val[i][j]))

         if (!solver.tryToSet(var[i][j], 1 - val[i][j]))

            return new String[] {};

      }

// construct the return value based on

// the solution of 2-SAT

char[][] cc = new char[N][M];

for (int i=0; i < N; i++)

   for (int j=0; j < M; j++)

      if (num[i][j] == 0) {

      cc[i][j] = (solver.getValue(var[i][j]) == 1 ? '#' : '.');

      } else if (num[i][j] > 0 && var[i][j] == -1) {

      cc[i][j] = '#';

      } else {

      cc[i][j] = (solver.getValue(var[i][j]) == val[i][j] ? '#' : '.');

      }

// return it

String[] res = new String[N];

for (int i=0; i < N; i++)

   res[i] = new String(cc[i]);

return res;

  }

}
复制代码

有道点评:
这个题初始的时候可以先将确定一些单元格的状态，即包含仅出现一次的单元格肯定要选，然后与它相邻的单元格都不能选，如果这样造成某些本来出现两次的数字变成只出现一次了，那么那一次出现肯定要选，而如果某个本来出现的数字不出现了，则无解。就这样一直做下去，直到出现无解或者无法简单的确定必须要选的单元格时停止。这时再转化成2-SAT求解，就只有包含出现两次的数字的单元格和不含数字的单元格，情况要简单一些。

账号		自动登录	找回密码
密码			注册

[互联网资讯] "有道难题2009"决赛题目、前三名解题思路、官方答案与点评

欢迎您注册加入！这里有您将更精采！