I Wanna Beat the Joke 我们定义f(n)为前n个数中关系左侧首次出现的数的数量。 可得f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 3。 以n=4为例，前四个数中首次出现的是1、2、3，而4并非首次出现 (因为n = 1时1 ⊨ 4已经出现4)。 易知题目所求即为2 * f(n)。 可以得到递推关系：f(n) = 总数 - 非首次出现的数 = n - f(n / 4)。 “非首次出现的数”为f(n / 4)是因为这些数都是之前“首次出现的数”乘 4 得到的。 f(n)可以通过递归或者迭代实现计算，时间复杂度为log(n)。  递归： def f(...

由于需要三个点才能计算平行四边形面积，枚举点时间复杂度不符合要求，所以我们考虑枚举边。我们对每两个点构成的向量用哈希表分组，注意向量的方向性。这里不用存下每组所有的向量然后进行排序，只需要维护一个最大值和最小值，不过需要用到一点简***面几何。 我们将当前分组的向量平移到原点，由于需要求每组向量之间能够组成的最大面积（如图中的红色面积），这可以拆成两个平行四边形面积之和（如图中绿色的S1和S2)。由于S是用叉积计算的（带正负），所以其实红色面积是S2 - S1。因此，我们只需要维护每组S的最大值和最小值，两者之差即为该组的最大面积。 from collections import defaul...

牛客练习赛114E Kevin的抽奖黑幕 题目链接 E的官解用的是期望dp的标准做法，其实赛时通过的大部分选手用的是概率dp拆开算期望。很多地方会看到这样的说法：通常情况下，期望dp从后往前递推，概率dp从前往后递推。这里的“前”和“后”其实指的并不是正序循环和逆序循环，而是起始状态和终止状态。在本题中，起始状态为未开始抽奖，终止状态为轮抽奖过后。那么期望dp是从轮抽奖之后的状态递推到未开始抽奖的状态，概率dp是从未开始抽奖的状态递推到轮抽奖结束的状态。记抽中概率为win = k / n , 未抽中概率lose = 1 - k / n。 概率dp 思路 这里的概率dp用到了期望的定义和线性性质...