Coding Kick Start

Google Kick Start 2018 A轮 题解

查阅更多的题解,请点击
github传送门

A.Even Digits

題目地址

Solution

题目大意

題目大意是給定一个数,每次只能加一或是减一,用最少的次数将其变成一个每位数都是偶数的数,求这个次数是多少

解法

小数据集可以暴力求解,尝试加和减两个方向,直至有一个方向达到要求

考虑一个数中存在为奇数的位,显然对结果影响最大的是从高到低第一个奇数,考虑将其变成偶数

  • 若减一,则希望其后的数均为8,这样变化后的结果离原来的数最近。(对于一个十进制数,按位减,需要考虑借位,不过最小的奇数是1,这里不用考虑)
  • 若加一,则希望其后的数均为0,这样变化后的结果离原来的数最近。这里需要考虑9+1需要进位的情况
    • 若第一个奇数为9,由于需要所有位均为偶数,9+1需要向前一位进2,在这种情况,考虑减的方向能得到的结果更小,可以直接忽略
    • 若第一个奇数不为9,则加一,其后的数均变为0

代码

B.Lucky Dip

題目地址

Solution

题目大意

一个人以等概率抽取n个物品中的一个,每个物品的价值不一样,最终他只能拿走一个物品,若抽取后不满意,可以放回再次以等概率抽取n个物品,最多放回k次。求这个人能得到的最大期望回报

解法

  • 若k=0,只能抽一次,最大期望回报就是n个物品的价值平均,设为dp[0]
  • 若k=1,第一次抽取结束后:
    • 若抽到的物品价值v_i\geq dp[0],显然无需放回,因为放回后,总的期望回报会减小
    • 若抽到的物品价值v_i< dp[0],希望放回,再次抽取的期望回报是dp[0] 则总的期望回报为dp[1]=\sum{max(v_i,dp[0])} /n
  • ……

从而得到递归表达式:dp[k]=\sum{max(v_i,dp[k-1])}/n

可以将物品按价值排序,每次进行二分查找,最后算法时间复杂度为O((N + K) log N). 代码

C.Scrmabled Words

题目地址

Solution

题目大意

给定一个长字符串(长度为N)和一个字典(字典中的元素各不相同,大小为L),计算字典中有多少元素在长字符串中出现(字典中每个元素仅计算一次)。判断字典中的词在字符串中出现:该词和字符串的一个子串相同,相同需要满足三个条件:

  • 词和子串的首尾字符相同
  • 字典中的词和子串由相同的字符构成

解法

问题的关键在于如何判断两个字符串由相同的字符构成,一个高效的做法是统计字符串中字符出现频率,由于问题中的字符串一定由小写字母组成,所以一个字符串的信息可以由26个int值来表示。数组的比较麻烦,可以利用hash函数将26个int值hash成一个数字,这样问题就变成了比较两个数是否相同

有了上述过程,一个直观的求解方式为:对于每一个字典中的词,设长度为w,遍历一次长字符串中所有长度为w的子串,所用时间为O(N) time(词的长度通常远小于N,可以忽略; 子串遍历过程是每次向右移一位,所以下一个子串的词频统计信息可以由上一个子串在常数时间得到,hash的过程同样是常数时间)。由于字典中有L个词,所以遍历过程是O(NL) time的。对于字典中所有词求hash的过程是O(L) time。所以该算法的时间复杂度为O(NL) + O(L)=O(NL) time。

注意上述过程中会出现冗余过程:对于字典中长度相同的两个不同词,长字符串遍历过程中的子串是相同的。基于这样的观察,可以将长度相同的词的遍历过程合并到一起。设字典中词有P种不同的长度,则上述算法可以优化到O(NP) time.

这样对于P,可以求出一个准确的上界,注意题目要求:

  • 字典中的每个词长度\in [2,10^5]
  • 字典中所有词的长度之和不超过10^5,设为M.

设字典中词最长为X,则使得P最大的,字典中词的长度分布为:1, 2, 3, 4,\cdots, X, 其和不超过10^5, 即(1+X)X/2=M\leq 10^5,可以得到X\leq \sqrt{M},此时P最大,为P=X\leq \sqrt{M}

所以最终算法时间复杂度为O(N\sqrt{M}) time.

代码

发表评论

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