爱奇艺2018秋季校招算法工程师（第二场）
时长:120分钟 总分:100分
142浏览 0人已完成答题
题型介绍
| 题型 | 单选题 | 填空题 |
|---|---|---|
| 数量 | 10 | 3 |
9.
有一个算法的递推关系式为：T(n) = 9 T(n / 3) + n，则该...
有一个算法的递推关系式为：T(n) = 9 T(n / 3) + n，则该算法的时间复杂度为（）(^符号是幂的意思)
11.
青草游戏
牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。 输入描述： 输入包括t+1行。 第一行包括一个整数t(1 ≤ t ≤ 100),表示情况数. 接下来t行每行一个n(1 ≤ n ≤ 10^9),表示青草份数输入样例： 3 1 2 3 输出描述： 对于每一个n,如果牛牛胜利输出"niu",如果羊羊胜利输出"yang"。输出样例 niu yang niu
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。 输入描述： 输入包括t+1行。 第一行包括一个整数t(1 ≤ t ≤ 100),表示情况数. 接下来t行每行一个n(1 ≤ n ≤ 10^9),表示青草份数输入样例： 3 1 2 3 输出描述： 对于每一个n,如果牛牛胜利输出"niu",如果羊羊胜利输出"yang"。输出样例 niu yang niu
12.
无聊的牛牛和羊羊
牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。每个小时牛牛和羊羊随机选择两个不同的朋友A和B.(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。现在你需要计算让所有朋友变得无聊所需要的时间的期望值。
输入描述：
输入包括两个整数n 和 m(1 &le n, m &le 50)输入样例：
2 1 输出描述：
输出一个实数,表示需要时间的期望值,四舍五入保留一位小数。输出样例
1.5
13.
幸运子序列
牛牛得到一个长度为n的整数序列V,牛牛定义一段连续子序列的幸运值为这段子序列中最大值和次大值的异或值(次大值是严格的次大)。牛牛现在需要求出序列V的所有连续子序列中幸运值最大是多少。请你帮帮牛牛吧。
输入描述：
第一行一个整数n,即序列的长度。(2<= n <= 100000)
第二行n个数，依次表示这个序列每个数值V[i], (1 &le V[i] &le 10^8)且保证V[1]到V[n]中至少存在不同的两个值.输入样例：
5
5 2 1 4 3 输出描述：
输出一个整数,即最大的幸运值输出样例
7
