第一题：
题目描述
有 n 个葫芦娃一起玩Hulu杀，他们被分为好人和坏人两个阵营，打乱之后围成一圈，按顺时针序编号为 0 ~ n-1。然后随机选定一个葫芦娃，从他/她开始由 1 到 m 顺时针报数，数到 m 的人被杀，下一个人继续从 1 开始报数，如此循环直到剩下最后一个人，这个人所属阵营获得胜利。我们用一个整型数组 a[i] 表示玩家 i 所属的阵营，a[i]=1 表示 i 是好人，a[i]=0 表示 i 是坏人；正整型数组 w[i] 表示玩家 i 被选为起始位置的权重，即玩家 i 有 w[i]/sum(w[i]) 的概率做起始位置。求好人获胜的概率，四舍五入到小数点后五位数字（不足五位需要补零）。

输入
第一行为 2 个空格分开的整数，分别表示 n 和 m
第二行为 n 个空格分开的整数，表示 a[i]
第三行为 n 个空格分开的整数，表示 w[i]
输入范围 0 < m < n <= 1000，0 < sum(w[i]) <= 10000000

输出
输出一个浮点数，表示好人获胜的概率

输入样例
3 2
0 0 1
2 1 1

输出样例
0.50000

【试题解析】
这道题目表面上是求概率，其实核心是一个 Josephus 问题 (https://en.wikipedia.org/wiki/Josephus)。通过解 Josephus 问题，我们可以得到从 0 号开始最终剩下的人的编号，假设是 x。根据圆环的对称性，推出从 i 号开始最后剩下的人的编号一定是 (x + i) % n。因此我们只需要求出这个偏移值 x，将指示好/坏人的数组 a 偏移 x 后与权重数组 w 相乘，再除以总权重即可。Josephus 问题有两种解法：一是通过数组或者链表模拟整个过程，复杂度是 O(n^2)；另一种是找出递推公式 f(n, m) = (f(n-1, m) + m) % n 求解，复杂度是 O(n)。题目中我们限制了 n <= 1000，因此两种方法都可以拿到满分。此题主要考察了编程基础以及灵活运的能力。

第二题：
题目描述：
Hulu有一些列的视频文件，每个文件都有对应的码率，为整数。输入长度为 n 的视频码率数组 arr ，现在定义两个文件区段之间最大码率为：
p[i][j] = max(arr[i], arr[i+1], … , arr[j]), 0 <= i <= j <= n-1.
针对所有满足条件 0 <= i <= j <= n-1 的 (i,j) 对，求 p[i][j] 的总和。

输入
第一行为 n，表示数组的长度。第二行为空格分开的 n 个码率（整数）。
输入满足：1 <= n <= 1000000， 1 <= arr[i] <= 1000000

输出
输出一个数字，即 p[i][j] 的总和，如果总和超过 1000000007 ，则返回对1000000007取模的结果
输入样例
3
1 2 2

输出样例
11
解释：满足要求的 p[0][0] = 1, p[0][1] = 2, p[0][2] = 2, p[1][1] = 2, p[1][2] = 2, p[2][2] = 2. 结果为 11。

【试题解析】
Solution 1: O(n^2)
选择 i 作为子数组左侧起点，j 从 i 到 n-1，遍历时，可同时获得该子数组的最大值。将最大值累加，时间复杂度 O(n^2)，空间复杂度 O(1)

Solution 2: O(nlogn)
设置dp数组，dp[i][j] 表示从 i 作为起始位置，长度为 1<<j 的子数组。j 不超过 logn。于是数组大小为 O(nlogn)
针对每个位置的数 i , 如果它作为某些子数组的max元素，那么意味着：
arr[x], arr[x+1], …, arr[i], arr[i+1], …, arr[y]
其中 max(arr[x], …, arr[i-1]) < arr[i], max(arr[i+1], …, arr[y]) < arr[i])
那么 i 作为子数组最大值时，一共会出现在 (i-x+1)(y-i+1) 种子数组里。恭喜的最大值和为 (i-x+1)(y-i+1)*arr[i]
基于此思路，针对每个 arr[i]，就只需要找出左侧和右侧大于 arr[i] 的坐标位置即可。
针对左侧查找，可以基于 dp 数组来做，二分查找 [0, i-1]，如果右半部分最大值大于arr[i] ，递归查找右半侧，否则左半侧。时间复杂度 O(logn)
最终时间复杂度O(nlogn)，空间复杂度O(nlogn)

Solution 3
思路和2是一致的，针对每个元素查找左侧和右侧大于他的index，那么针对左侧查找，其实可以用一个递减栈来维护截止目前进入栈的值。
针对 arr[i], 如果栈顶元素小于 arr[i] 则不断弹出，直到空或者栈顶大于 arr[i]，那么该位置就是 arr[i] 的左侧大于他，且最近的第一个元素。
针对右侧也是类似。
于是时间复杂度是 O(n)，空间复杂度 O(n)

第三题：
题目描述：
有一个葫芦娃进了一个正方形矩阵迷宫，迷宫中0代表路，1代表墙，葫芦娃可以上下左右在迷宫内的路上移动（不允许斜着走）。葫芦娃初始在左上角的起点，请问最少需要移除多少块墙（将1转换为0），才可以让葫芦娃移动到右下角的终点（起点和终点都为0）。

输入
第一行为一个整数n，代表迷宫的边长。
第二行开始，以空格分割的整数，每一行代表迷宫中的一行。
输入满足：2 <= n <= 5000。

输出
一个整数，表示最少移除多少墙壁可以使葫芦娃逃出迷宫
输入样例
3
0 1 1
0 1 1
0 1 0
输出样例
1

【试题解析】
这题其实类似与很多01矩阵的题目，如岛的数量，能否走出迷宫等一系列问题，本质上都是bfs一层层寻找。这一题的思路用bfs也不难想出，只需要通过一次次bfs扫描，把每一次遇到的墙当作下一次的出发点，即可得出最少移除多少墙可以到达终点。这题难度本身不高，但是代码量比较大，考察的是同学们的代码熟练度。

第四题：
题目描述：
Hulu有很多直播资源需要付费订阅观看，世界杯期间，Hulu决定把部分比赛内容开放给普通用户免费观看。已知某频道将要连续播放的n场比赛列表，其中有的比赛有重播。工程师需要把该频道的n场比赛剪切成k个小片段，每个片段包括若干场比赛，然后把片段推荐给用户观看。剪切不能改变比赛列表的顺序，也不能将一场比赛从中间切断。研究发现，用户观看的片段中不同的比赛场次越多，用户越感兴趣。假设兴趣值为片段中不同的比赛出现次数，该频道的兴趣值为各个片段的兴趣值之和。工程师需要通过巧妙的剪切最大化该频道的兴趣值。

输入
第一行输入两个以空格分隔的整数n和k（1 <= n <= 5000, 1 <= k <= 100, k <=n），分别表示比赛场次和剪切片段数。
第二行输入以空格分隔的
n个整数，a1,a2, … , an （1 <= ai <= n）, 分别表示每场比赛的id。

输出
输出一个整数，表示最大的兴趣值。
输入样例
3 2
2 1 1
输出样例
3

【试题解析】
不难想到一个动态规划的算法，dp[i][j] 表示前 i 场比赛被剪切成 j 段的最大兴趣值，w[p][i] 表示从第 p 场比赛到第 i 场比赛的片段中不同比赛出现次数。状态转移方程为：
dp[i][j] = Max1<=p<i(dp[p-1][j-1] + w[p][i])
如果遍历 i， j 和 p 求解，时间复杂度为 O(n2k)。
当比赛被剪切成 j 段时，遍历 i，可以用一棵线段树维护兴趣值 dp[p-1][j-1] + w[p][i] 的最大值，对于第 i 场比赛 a[i]，假设其上一次出现的位置为 q，线段树在区间 [q + 1, i] 上的值加1。线段树操作的时间复杂度为 O(log(n))，总的时间复杂度为 O(nklog(n))。