《挑战程序设计竞赛》题解 | shu_mj 的博客

1 / 1 Problem A POJ 2386 Lake Counting
A 是例题啊，就直接 dfs 就好了，注意是 8 连块。

1 / 1 Problem B POJ 1979 Red and Black
B 就直接 dfs 数有多少个联通块。

1 / 1 Problem C POJ 3009 Curling 2.0
C 题算法也简单，可是实现麻烦。我是一步一步模拟的，并且用了"迭代深搜"。如果之前的搜索是可以最优化剪枝的，那直接每次设置最优解就好了，第一次找到的解就是最优的。直接 bfs 也是可行的，只不过需要记录整张图。迭代深搜看似好写，但是在深度过大时，可能会超时。

1 / 2 Problem D POJ 3669 Meteor Shower
这一题我看了 POJ 的 discuss，很多同学认为数据有问题，其实不然。数据是正确的，人的活动范围是第一象限，输入的坐标最多是 (300, 300)，也就是最多会影响到 301，那么数组开到 303，就可以过了。

1 / 1 Problem E POJ 2718 Smallest Difference
后面几道题目都是枚举的了。这个直接全排列枚举，如果不符合数字规范就 continue 掉。直接认为前一半是一个数字，后一半是一个数字，这是贪心，可以证明。如果是奇数个数字，就认为前一半少一个数字，可以证明不丢失最优解。

1 / 2 Problem F POJ 3187 Backward Digit Sums
暴力枚举了，我发现下面一行的数字对原数组的使用其实跟组合数有关。所以我先算了一个组合数，然后全排列枚举原数组，对每个排列，O(n) 计算结果。我觉得这个是可以二分的，不深究了。

1 / 1 Problem G POJ 3050 Hopscotch
这题为什么我觉得是 DP 呢？反正我是 DP 解的，DP[i][j][k]，表示在 (i, j) 位置，长度为的 k 的串的集合。 DP[i][j][k] = U{ DP[与 (i, j) 相邻][k - 1] }。最终答案为 U{ DP[ALL][6] } 的元素个数。

Read full article from 《挑战程序设计竞赛》题解 | shu_mj 的博客