CSDN 编程竞赛六十九期题解

竞赛总览

CSDN 编程竞赛六十九期：比赛详情 (csdn.net)

竞赛题解

题目1、S数

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为S数。现在，给定两个正整数L、R，返回包含在范围 [L, R] 中S数的数目。

给出的数据范围很吓人，博主选择直接使用Python来解决此题，避免C++处理大数时产生不必要的麻烦。实际上，由于条件比较苛刻，因此满足条件的回文数并不多，直接打表也是一种不错的选择。

如果使用常规方式解决，需要检测三项内容：

1、当前数字本身是否为回文数。

2、当前数字是否为某数的平方。

3、对应开方数字是否为回文数。

原数字记为 a，开方之后的数字记为 b = int (a ** 0.5)。

如果 b ** 2 == a，可以认为原数字 a 是开方数字 b 的平方。

然后，再判断两个数字是否为回文数。

题目2、最小H值

给你一个二维的地图，其中 map [row] [col] 表示格子 (row, col) 的高度（注意，下标从 0 开始编号）。一开始在左上角的格子 (0, 0)，且希望去最右下角的格子 (rows - 1, columns - 1)。每次可以往上下左右四个方向之一移动，目标是找到H值最小的一条路径。一条路径的H值是路径上相邻格子之间高度差绝对值的最大值决定的。请你找出从左上角走到右下角的最小H值。

这个题目可以从四个方向进行移动，因此不能使用动态规划方法了。可以使用深度搜索算法，结合剪枝操作。当搜索完一条路径时，更新历史最小H值。如果其它正在搜索的路径的当前最小H值已经超过这个局部最优解，那么可以直接放弃搜索该路径。

不过，实际上测试数据很水，地图一共没超过5*5的大小。另外，地图上格子的高度相差也不大，答案同样很水。博主很懒，没有使用搜索算法，而是选择了直接骗分快速通过。