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

建议首先阅读：

• 算法小结（一）-面对问题如何思考

update: 这一轮通过了，但是ml intern的面试流程也没有更新（貌似可能因为疫情凉凉），感觉kick start失去了意义

先对本轮做个小结吧：这轮参加人远多于之前，总共有10000+人参加，规则也有所改变：

• 题目由原来的3道改为了4道，感觉整体变简单了。
• 没有隐藏的test set

这也是第一次全部AC，不过等结束了去统计了下，有917人满分。感觉意义也不是很大。而且比较难受的是，博主是21届毕业的学生，咨询HR发现仅2020年的成绩对校招有效，去年过了的不算。今年还得重打orz。

A. Allocation

题目地址

Solution

解法

这道题很简单，升序排序，然后从小到大取就可以了。（没想到kick start也有这么简单的题，我多看了好几分钟，都没敢直接写答案）

复杂度分析

瓶颈主要在排序： O(nlogn) time.

代码

code

B. Plates

題目地址

Solution

解法

该题是一道典型的动态规划问题，所求的是n堆plates中，取k个plate，所能得到的最大值

那么可以定义子问题：令dp[i][j] 代表前i堆plates里取j个plates得到的最大值，得到状态转移方程：

dp[i][j]=max\{dp[i-1][j-m]+ sum_{i}(m)|for\ m\in[0,min(k,j)]\}

其中的sum_{i}(m)代表在第i堆取m个plates的结果。注意，这里类似童年游戏汉罗塔，只能从上向下依次取，所以可以用前缀和来加速

复杂度分析

• 前缀和：n\times k
• dp: n\times p\times k

总计：O(npk) time.

代码

code

C. Workout

题目地址

这道题，会用到一个有意思的算法技巧：优化问题转决策问题，知道这个技巧，问题就比较简单了。

Solution

解法

题目要求在插入k个session的情况下，所能得到的最小难度，从问题来看是一个的优化问题；而难度等于整个program中，两个连续session时间差的最大值。那么可以直接求出不加任何session的情况下，运动的难度，记作d，设所求解为res，那么一定有res \in[1,d]

问题就可以从优化问题，转化为决策问题：对于m \in[1,d]，在至多插入k个session的情况下，是否成立？

同时该过程可以用二分搜索加速

复杂度分析

O(N*log(d)) time

代码

code

D. Bundling

题目地址

Solution

解法

从题目描述来看，和字符串前缀相关，字符串又特别多，比较容易想到trie树，trie树的设计思想就是尽可能利用共同前缀，节省存储空间：当我们的trie树构建完成之后，实际上已经得到了最优解的组合情况，注意在构建树的时候，在每个节点，记录节点child的个数num_i；

遍历整个trie树，最优解的值为:\sum_{i\in {tree node}}num_i/K

代码

code