OPPO9.9笔试软件类后端C卷（AK）

第一题太简单就不说了；

第二题：
1、如果d是奇数，那其实是没办法往集合里插入新元素的，假设挑出ai和aj(j > i)，若(j - i) % 2 == 1，则ai+aj必定不为偶数，不符合条件，若(j - i) % 2 == 0，则ai + aj / 2必然已在集合中，故当d是奇数直接返回n；
2、如果d是偶数，则可以往集合中插入n - 1个元素，因为每次只需要将相邻两个元素相加并除以2放到数组中就可以了，因为当两个元素不相邻时计算出来的新元素已经被前面的情况覆盖了。所以，当d是偶数，可以在集合中插入n-1个元素，并且，此时集合相当于变成了一共长度为2 * n - 1，公差为 d / 2的新等差数列，此时继续判断新的公差是否为偶数并继续插入即可。

第三题：n个杯子，其中k杯有水，求喝完水的回合期望数。喝完所有水的回合期望数，等于 喝完第一杯水的回合期望数 + 喝完第二杯水的回合期望数 + ...... +喝完第k杯水的回合期望数。此时先不考虑不能连续两回合喝水这个条件，考虑一般情况，假设现在还剩i杯水，则此时能喝到水的概率为A = i  / n，根据概率论的知识，我们可以知道此时喝一杯水的回合期望数sum = A * 1 + A(1 - A) * 2 + A(1 - A)(1- A) * 3...... ，敏感的同学应该发现了，这个式子的每一项近似于等比数列，我们设公比q =（1 - A），则sum = A * (1 + 2 * q + 3 * q * q + 4 * q * q * q......)，数学不错的同学应该知道怎么处理了，取 q * sum = A * (q + 2 * q * q + 3 * q * q * q......)，再将sum与 q * sum做差即可构造出等比数列，后面再使用等比数列求和公式并取极限，可以计算出下面图片的公式，也就可以计算出还剩i杯水时喝一杯水的期望回合数了，那我们只需要使i 从 k 到 1进行计算并累加即可，计为ans。最后，如果考虑不能连续两回合喝水这个条件，其实只需要给ans加上k - 1即可，令ans += k - 1，此时ans即为最终答案。

最后两道题一道等差数列，一道等比数列加求极限，你说我是在做数学题我都信