贝壳找房2021届校招算法卷3
时长:120分钟 总分:100分
108浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 4 |
1.
存活情况
牛牛和牛妹在感叹现代科技日新月异的同时，也不忘关注着环保事业。
今天，牛牛和牛妹一同来到了戈壁滩种树，他们决定在同一排种下一共
棵小树，已知每棵小树的存活率相同，现在，牛牛和牛妹想要知道，在这 
棵树中，恰好有 
棵树存活时，最终这排小树形成的风景线会有多少种不同的情况。
由于最终答案可能很多，所以只需要输出对
取模后的结果。
输入描述：
本题为多组测试数据，第一行输入一个正整数 
，代表测试数据组数。
对于每组测试数据，一行输入两个正整数
，分别代表种下的树的数量以及最终恰好有 
棵树存活。输入样例：
1
2 1 输出描述：
对于每组测试数据，一行输出一个整数代表一共多少种情况。输出样例
2
今天，牛牛和牛妹一同来到了戈壁滩种树，他们决定在同一排种下一共
棵小树，已知每棵小树的存活率相同，现在，牛牛和牛妹想要知道，在这 棵树中，恰好有 棵树存活时，最终这排小树形成的风景线会有多少种不同的情况。由于最终答案可能很多，所以只需要输出对
取模后的结果。
输入描述：
本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。对于每组测试数据，一行输入两个正整数
，分别代表种下的树的数量以及最终恰好有 棵树存活。输入样例：
1
2 1 输出描述：
对于每组测试数据，一行输出一个整数代表一共多少种情况。输出样例
2
2.
牛牛的小木棍
牛牛有
对黑色的木棍，长度分别为
，
对白色的木棍，长度分别为
，牛牛可以每次取走一对黑色的木棍和一对白色的木棍组成一个对边颜色相同，临边颜色不同的矩形，并计算出这个矩形的面积。每对木棍只能使用一次且不能将这对木棍拆开，牛牛能知道他能得到的所有矩形的总面积最大为多少。
输入描述：
第一行，一个整数
。
第二行，
个整数
。
第三行，
个整数
。输入样例：
5
1 5 2 4 3
3 1 1 2 1 输出描述：
输出一行一个整数表示牛牛能得到的所有矩形的总面积最大为多少。输出样例
29
对黑色的木棍，长度分别为，对白色的木棍，长度分别为，牛牛可以每次取走一对黑色的木棍和一对白色的木棍组成一个对边颜色相同，临边颜色不同的矩形，并计算出这个矩形的面积。每对木棍只能使用一次且不能将这对木棍拆开，牛牛能知道他能得到的所有矩形的总面积最大为多少。
输入描述：
第一行，一个整数。第二行，
个整数。第三行，
个整数。输入样例：
5
1 5 2 4 3
3 1 1 2 1 输出描述：
输出一行一个整数表示牛牛能得到的所有矩形的总面积最大为多少。输出样例
29
3.
牛牛打气球
有n个气球，每个气球都有一个坚韧度，牛牛有一把全屏武器，可以使每一个气球的坚韧度都下降b（坚韧度不会为负数），特别的：每次释放武器的时候，牛牛可以选择一个气球，使得这个气球多承受a点伤害。
牛牛想知道，最少释放几次武器，可以使得所有气球的坚韧度都变成0呢？
输入描述： 第一行三个整数n,a,b。第二行n个空格隔开的整数，第
个数表示第i个气球的坚韧度。
。其余所有整数都在
范围内。输入样例：
3 1 2
1 4 5 输出描述：
一个整数表示答案。输出样例
2
4.
世界杯
牛牛要参加一场程序猿世界杯，一共有
名选手参加比赛，选手们依次编号从
到
，比赛采用单淘汰制，即第一轮
进行比赛，第一轮的决胜者再与相连的选手进行比赛，每轮都会淘汰一半的选手，进行
之后能决出冠军。牛牛的编号为
，但是牛牛知道了各个选手与其他选手比赛时的胜率。牛牛想知道他能夺冠的概率是多少呢，牛牛给你各个选手之间若进行比赛时的胜率，请你告诉牛牛他夺冠可能的概率是多少呢
输入描述：
第一行为两个整数名选手参加比赛，选手们依次编号从到，比赛采用单淘汰制，即第一轮进行比赛，第一轮的决胜者再与相连的选手进行比赛，每轮都会淘汰一半的选手，进行之后能决出冠军。牛牛的编号为，但是牛牛知道了各个选手与其他选手比赛时的胜率。牛牛想知道他能夺冠的概率是多少呢，牛牛给你各个选手之间若进行比赛时的胜率，请你告诉牛牛他夺冠可能的概率是多少呢 
，表示进行多少轮比赛，以及牛牛的编号。接下来有
行，每行有
个整数，第
行第
个元素
表示第
名选手战胜第
名选手的概率。
输入样例：
2 3
0 10 90 90
90 0 10 10
10 90 0 50
10 90 50 0 输出描述：
输出为一个浮点数表示答案，答案的误差应小于0.000001。输出样例
0.4100000000