leetcode 第 401 场算法比赛

零、背景

这次比赛最后一题感觉暴力会超时，就没做了，赛后发现暴力也可以通过，正规做法是 bitset。

A: 模拟。
B: 模拟。
C: 枚举。
D: bitset。

排名：230
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/401

一、找出 K 秒后拿着球的孩子

题意：n 个人占在一排传球，起始从第一个人开始传，传到最后一个人再往相反方向传，问 k 秒后球在第几个人。

思路：模拟或者公式计算。

模拟：维护一个方向和下标，模拟即可。

公式：每过 2*(n-1) 秒，球就回到第一个人手上，所以时间可以对周期进行取模。
之后，如果时间不大于 n-1，则是从小到大，否则就是从大到小。

二、K 秒后第 N 个元素的值

题意：大小为 n 的数组，起初值都是 1，每过一秒每个位置的值都是前缀和，求第 k 秒最后一个位置的值。

思路1：按题意循环模拟。
复杂度：O(nk)

思路2：矩阵幂, k 很大时可以用来加速。
复杂度：O(n^2 * log(k))

思路3：公式C(n + k - 1, k)

三、执行操作可获得的最大总奖励 I

题意：给一堆金币，金额为 0，可以从金币中拿出一个价值大于金额的金币，加到金额里，不断这样操作，问最终金额最大是多少。

思路1：模拟。
第三题数据样例小，第四题数据样例比较弱，可以暴力通过。
复杂度: O(nV)
优化：从前到后枚举判断金额 V 是不是答案时，只需要判断是否存在一个价值为 B=[V/2, V-1] 的金币，同时保证金额 A=V-B是答案。
复杂度：O(nV/2) 很多人使用这个方法通过
反例：有 10^5个金币，金额分别为 2,4,6,...,2k，必然会超时。

思路2：bitset
假设当前可以得到的小于 V 的金额集合有 k 个，加上 V 后，又可以得到 V+k个金额，可以加入集合。

这里需要对集合做下面几个元素：

1、选出集合里小于 V 的元素，得到新的集合
2、集合里所有元素值加上 V，得到新的集合
3、两个集合求并集

对于这个操作，每个值当做一个bit，即可转化为 bit 位的操作，如下。

1、选出集合里小于V 的元素：
假设有一个前 V-1个元素的全1 bit， 求且即可。
如果没有这样的全 1 bit， 可以通过位运算左移右移来得到。

2、集合里所有元素值加上 V：bit 右移 V 位。
3、两个集合求并集 ：bit 求或运算。

复杂度：O(nv/8), leetcode 不会超时

模板地址：https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/stl/bitset.cpp

四、 执行操作可获得的最大总奖励 II

与第三题一模一样，数据范围变大了。

五、最后

这次比赛最后一题是 Bitset， 之前知道 bitset，但是从来没有应用过，这次算是掌握了新的算法。

《完》

-EOF-

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