leetcode 第 219 场算法比赛

零、背景

这次比赛，前两题 5 分钟写完后，第三题本来两分钟随手敲出了正解的DP，但是多看了一眼题，想复杂了，当成最大值最小值博弈动态规划题了，感觉很复杂。

又看了眼第四题，发现数据范围不大，暴力做就是最小生成树或者动态规划。

可能最近一周工作比较忙吧。

我突然不想打比赛了。

由于买的钢化膜已经到了，我便去 B 站上学习了怎么贴膜，然后给 ipad 贴膜去了。

贴完后，自我感觉良好，B 站有各种教程，真是一个神奇的网站。

明天就去买他的股票。但一想，是美股，那还是算了。

下面来看看四道题吧。

四道题源代码：
https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/219 ·

一、比赛中的配对次数

题意：一个数字，偶数除2，奇数除2向上取整，问除多少次到 1。

思路：由于每次缩小一倍，暴力计算即可。 复杂度：O(log(n))

优化：简单模拟一下，可以发现答案是有规律的，直接套公式即可。
复杂度：O(1)

二、二进制数的最少数目

题意：给一个十进制字符串，问最少可以由多少01组成的十进制字符串想加得到。

思路：简单分析之后，可以发现每一位是没有关系的，至于当前位的数字有关。
当前位是几，就至少需要多少个字符串。
所以答案就是所有位数的最大数字。
复杂度：O(n)

三、石子游戏 VII

题意：给n 堆石子排成一排，每堆石子有若干个。
A 和 B 两人依次从两头选择一堆石子，选择的得分是剩余石子的总个数。
A 的目标是使两个人的得分差值最小，B 的目标是使两个人的得分差值最大。
假设两个人都选择最佳策略，A 先走，问最终得分差值是多少。

思路：原先题意为了降低题意，文中直接说明了无论如何走， B 的得分肯定是小于 A 的。

如果不看这个提示，这道题就非常复杂了。

因为假设最终 B 的得分大于 A 的，那 B 选择的时候，就需要适当放水，让自己的得分与 A 近一些。
而 A 知道 B 会放水，会想办法也放水或者不防水，就可以把得分差值拉的更大点。

总之，我想复杂了。

回到原题，由于每次操作的得分是剩余石子之和。
这个性质决定了，先走者永远必胜。

证明：将所有操作按顺序两两分组，则每次第一个人的得分肯定大于第二个人的得分。
因为第一个人的得分是第二个人得分加上第二个人拿走的那堆石子数量。
如果石子有偶数堆，显然没问题。
如果石子有奇数对，第一个人最后拿走一堆石子，得分是0，可以忽略。
证闭。

有了第一个人 A 必胜这个条件，这个问题就变得简单了。

因为 A 必胜，说明 A 的总得分比 B 多。
那 A 的目标就是所有操作中，尽量多的得分。

而 B 由于必败，想要与 A 的总得分差值尽量小，A 的目标也是所有操作中尽量多的去得分。

A 和 B 的目标都是尽量多的去得分时，问题就简单了。

定义dp[l][r]为当前操作者在[l,r]区间内的最多得分差值。
则当前有两个选择：

1）选择左侧，则得分差值是sum[l+1,r] - dp[l+1][r]。
2）选择右侧，则得分差值是sum[l][r-1] - dp[l][r-1]。

当前的最优值两者取最大值。

由于中间过程状态可能为负，可以使用递推的方式两层循环来做。

四、堆叠长方体的最大高度

题意：给 n 个长方体，问能否选若干子集，使得长方体堆积在一起后高度最高。
堆积规则：下面的长方体长宽高应该不小于上面的长方体。

思路：

我第一想法是最小生成树。
每个长方体旋转后有 6 中摆法，每中摆法都是一个顶点，共有 6n 个顶点。
一个长方体的一种摆法可以放在另一中摆法的长方体下面时，则可以连一个有向边。
然后使用最大生成树算法计算即可。
复杂度O((6*n)^2)

其实，这个图是一个有向无环图，也可以直接按照最长上升子序列算法来暴力计算。
复杂度：O((6*n)^2)

再分析一下这个有向无环图，长宽高排序后，即使只考虑长方形，也是没有环的。
即这个是一个拓扑图。

所以可以先排序得到拓扑图，然后使用O(n^2)的动态规划找到最长上升子序列即可。
复杂度：O(n^2 + n log(n))

五、最后

这次比赛前两题是签到题，后两题是动态规划题。

对于第三题，能想到两个人的目标是一致的，都是求最大得分就可以写出状态方程了。
而对于第四题，无脑最大生成树即可。

对了，周日以为 atcode 是22点的比赛，打游戏比较晚。
等快 22 点的时候，一看时间，比赛已经结束了。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code