Kick Start

Google Kick Start 2019 G轮题解

查阅更多的题解,请点击
github传送门 (求个star哇)

A. Book Reading

题目地址

Solution

解法

本题如果采用暴力求解,最坏情况下,每个读者都需要O(n) time, 则总的时间复杂度为O(nq) time. (一个简单的例子,q个读者对应的R_i都是1,那么每个读者都要算n次)

为了避免上述暴力过程中出现的重复计算,可以将结果提前存下来,count(i)代表i的倍数且未被撕掉页的个数。那么计算整个count数组需要N+N/2+N/2+\cdots+1=N(1+1/2+1/3+\cdots+1/N):

其中的N(1+1/2+1/3+\cdots+1/N)是调和数,H_{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\sum_{k=1}^{n} \frac{1}{k},利用极限可以得到\lim _{n \rightarrow \infty}\left(\sum_{k=1}^{n} \frac{1}{k}-\ln n\right)=\gamma,最终有H_{n} \sim \ln n+\gamma

所以整个算法的时间复杂度为O(nlogn+q) time.

复杂度分析

见上,O(nlogn+q) time

代码

code

B. The Equation

題目地址

Solution

解法

这道题思路很清晰:将A_i转化为二进制表示, (A_1\ xor\ k)+(A_2\ xor\ k)+\cdots+(A_k\ xor\ k)仅由二进制表示中,每位上1的个数和k对应位置取值(0或1)决定,令count(i)为二进制表示中第i位(由低到高标号,从0开始)1的个数,count(i)\in [0,n]

注意0\leq M\leq10^{15}且0 \leq \mathrm{A}_{\mathrm{i}} \leq 10^{15}, for all i。由于2^{49}<10……{15}<2^{50},而2^{50}的二进制表示有51位(注意不是50位,博主就是写成了50位,导致大数据集没有过),所以i\in[0,50]

要求最大的k,可以用贪心策略,从高位到低位依次枚举,在满足(A_1\ xor\ k)+(A_2\ xor\ k)+\cdots+(A_k\ xor\ k)\leq M的情况下,k当前位取1。

可以提前判断是否存在符合题意的k:即最小化(A_1\ xor\ k)+(A_2\ xor\ k)+\cdots+(A_k\ xor\ k)=\sum_{i\leq 50}{(1ll<<\ i)* min(n-count(i),count(i))}=sum,若sum>m,则不存在符合题意的k。

复杂度分析

由于A_i二进制表示的位数上界为常数,所以可以认为上述过程是O(N) time.

代码

code

C. Shifts

题目地址

Solution

解法

设两个保安分别为A和B,总共有n个时间段,每个时间段有3种选择,共有O(3^n)种不同的方案,直接暴力搜索是O(3^n) time,只能过小数据集。直观的想法是对搜索过程进行剪枝(参考该方案),暴力求解的dfs搜索树共有n层,下一层的节点数是上一层节点数的3倍,总共有2种有效的剪枝策略:

  • 当搜索到第i层时,当前节点:A和B的开心值均已满足要求,则无需继续搜索,之后的排班方案对结果无影响,res+=pow(3,n-i)
  • 当搜索到第i层时,当前节点:之后的每个时间段,A和B均参与工作,开心值总和不满足要求,则无需继续搜索,这里需要提前计算后缀和

官方题解:官方题解是利用meet in the middle来减少搜索空间,整个思路的本质同上,且更优,然而merge的时候需要range tree,本人并不会。。

复杂度分析

O(3^n) time.

代码

code

发表评论

电子邮件地址不会被公开。 必填项已用*标注