1. 奇数层的数字为偶数,而且从左到右严格递减;
2. 偶数层的数字为奇数,而且从左到右严格递增.
假设有一个圆心固定,半径无限,角度为 angle 的扇形,它可以任意旋转.给定一些点,问这个扇形最多能盖住多少个点.
首先根据圆心算出所有点的角度(x轴正方向为 0 度),然后按照大小排序.然后用 two pointers 来找出角度差为 angle 的最大长度.需要注意的是如果两个角度的差大于 180 度,那么我们要将这个角度差调整成 360 - 角度差.为了方便,我将所有的角度每个加上 360 也考虑进来,这样就不用调整了.
base += 1
对于一个数 n 的二进制,我们可以进行以下两种操作:
问至少操作几次能将 n 变成 0.
一开始的时候假设 n 的二进制是 1x...x,长度为 l.而110...0 变成0的操作次数是 2l,所以我们只需要求出将 x...x 变成 10...0 的最小步数.x...x 的长度为 l - 1,但是我们希望将其变成 10..0,而不是 0.总结以下,我们将原来的问题转化成:给定一个长度是 l 的 01 序列 x...x, 将其变成 c0...0 至少需要 f(x...x c0...0) 步,求 f(x...x c0...0).c 是 0 或 1.这个想法让我有了以下的算法:
为了方便讨论,我们将 01 序列的最左那位用 y 表示.假设当前 01 序列是 yx...x, 长度为l,我们需要将其变成 c0...0.
比赛的时候 (2.2) 的分析一直没有弄对,有点可惜了.