腾讯笔试 9.15 技术研究

技术研究的笔试感觉比第一次难😅😅
只做了4题出来了，时间根本来不及

1. 统计每个元素次数，然后对统计出来的次数组成的集合，枚举子集，对每个子集求积，然后所有积求和。 DFS枚举子集会超时。这边考虑次数组成的集合里面，每增加一个元素，最终的和会 增加 v[i] *（1+ans）其中ans是不增加元素的答案，所以直接for循环累加得到最后的ans。

2. 按照题目的意思，先对最后的公式化简一下，得到一个包含（k-1 / k+1）的n次方的式子，对这个式子累加求积，不断约分，最后再加1，再除以2，再约分。

3. 不断合并2项，求出所有合并过程中第1项的和，直到最后只剩下两项目。首先求出合并次数，是一个M＝log2（n）次，然后每个元素的权重从M到1降低，每个权重需要2的c次方，c为当前合并次数。依次加一次就好，加的过程注意每个元素的次数a是否能满足当前需要的元素个数2的c次方。

4. 给平面n个点的坐标，求起点到终点的最短路径长度。由于距离是欧式距离，可以很容易的证明到，最短路径中间最多只经过一个点。因此只要枚举所有中间点即可。O(n)的复杂度。

5，时间来不及了。