贝壳找房2021届校招开发类试卷
时长:120分钟 总分:100分
122浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 6 |
1.
牛牛的航路
牛牛当上了牛客国的国王，在牛客国一共有
个城市，这
个城市之间原有
条航路，但是由于城市航路规划，需要删除一些航路，使剩下的航路刚好能让这
个城市联通，并且剩下的航路总载客量最大。牛客国的计数方式比较特别，他们喜欢用组合数
来计数。所以两个城市之间航路的载客量也是用
表示的。作为国师你能告诉牛牛剩下的航路的总载客量是多少呢，由于数可能很大请对
取模后告诉牛牛。
输入描述：
个城市，这个城市之间原有条航路，但是由于城市航路规划，需要删除一些航路，使剩下的航路刚好能让这个城市联通，并且剩下的航路总载客量最大。牛客国的计数方式比较特别，他们喜欢用组合数来计数。所以两个城市之间航路的载客量也是用表示的。作为国师你能告诉牛牛剩下的航路的总载客量是多少呢，由于数可能很大请对取模后告诉牛牛。 第一行为两个整数
和
，表示城市数量和原有航路条数。
和，表示城市数量和原有航路条数。接下来有
行，每行有四个整数
，表示一条航路之间的两个城市编号和航路载客量
中的
和
。
行，每行有四个整数，表示一条航路之间的两个城市编号和航路载客量中的和。
取模，若剩下的航路不能让所有城市联通输出
。输出样例
5
2.
最大子段或
给出一个正整数序列
，求一个子区间使得这个区间内的数或起来尽可能的大。
或运算指数字按二进制位进行以下运算：
运算规则：
一个序列的子区间指这个序列中连续的一段数字。
牛牛并不关心这个最大值是多少，他只关心所有满足条件的子区间里，最短的子区间长度是多少。 输入描述： 第一行一个正整数
，代表这个序列的长度。
接下来一行空格分隔的正整数
，用来描述这个序列。
输入样例：
3
1 2 3 输出描述：
仅一行一个正整数代表答案。输出样例
1
，求一个子区间使得这个区间内的数或起来尽可能的大。或运算指数字按二进制位进行以下运算：
运算规则：
一个序列的子区间指这个序列中连续的一段数字。
牛牛并不关心这个最大值是多少，他只关心所有满足条件的子区间里，最短的子区间长度是多少。 输入描述： 第一行一个正整数
，代表这个序列的长度。 接下来一行空格分隔的正整数
，用来描述这个序列。输入样例：
3
1 2 3 输出描述：
仅一行一个正整数代表答案。输出样例
1
3.
线性魔塔
牛牛在玩一个线性魔塔游戏，地图是一条[-n,n]的直线段。
怪物在[-n,-1],[1,n]的每个位置都有分布。同向的怪物互相遮挡，比如如果要攻击位置为3的怪物，必须在攻击之前击杀位置为1和2的怪物,如果要攻击-2位置的怪物，也必须先击杀位置-1的怪物。
每一个怪物需要消耗勇者
的生命值，杀死某个怪物后会给勇者恢复
的血量。
勇者的生命值在非正的时候被认为牺牲，勇者的生命值没有上限。
牛牛想知道，勇士初始时拥有多少生命值，可以用策略杀完所有怪物。
输入描述： 第一行输入一个整数n，如题目中所示。
随后一行，输入2n个整数
，分别表示按[-n,-1],[1,n]的顺序，杀死怪物消耗的勇者的生命值。
输出样例
7
怪物在[-n,-1],[1,n]的每个位置都有分布。同向的怪物互相遮挡，比如如果要攻击位置为3的怪物，必须在攻击之前击杀位置为1和2的怪物,如果要攻击-2位置的怪物，也必须先击杀位置-1的怪物。
每一个怪物需要消耗勇者
的生命值，杀死某个怪物后会给勇者恢复的血量。勇者的生命值在非正的时候被认为牺牲，勇者的生命值没有上限。
牛牛想知道，勇士初始时拥有多少生命值，可以用策略杀完所有怪物。
输入描述： 第一行输入一个整数n，如题目中所示。
随后一行，输入2n个整数
，分别表示按[-n,-1],[1,n]的顺序，杀死怪物消耗的勇者的生命值。随后一行，输入2n个整数
，分别表示按[-n,-1],[1,n]的顺序，杀死怪物后勇者恢复的生命值。
，分别表示按[-n,-1],[1,n]的顺序，杀死怪物后勇者恢复的生命值。对于
的数据有
。
对于
的数据有
。
对于
的数据有
。
对于
的数据有
。
对于
的数据有
输入样例：
2
6 5 8 9
1 20 1 0 输出描述：
的数据有。对于
的数据有。对于
的数据有。对于
的数据有。对于
的数据有输出一行一个整数，表示答案。
4.
涂色II
牛牛管理着一片农场，在这片农场的一侧有着 
块栅栏排成一排，为了给单调的牧场生活增添一份乐趣，牛牛决定为这 
块栅栏涂色。
现在，牛牛在牧场中一共找到了
种不同颜料，每种颜料都有自己的推荐方案，如：第 
种颜料罐上写着，在这种颜料后如果紧跟 
这 
种颜料中的一个，整体色调就会显得不那么美丽。
那么，在满足上述前提下，牛牛最终完成的美丽的涂色一共会有多少种方案？
由于答案可能很大，所以只需要求出对
取模后的结果。
输入描述：
本题为多组测试数据，第一行输入一个正整数 
，代表测试数据组数。
对于每组测试数据，第一行输入三个正整数
，代表栅栏总数，颜料总数以及每种颜料后不能紧跟的颜料种类数。
接下去
行，每行输入 
个正整数，
，代表该种颜料后不能紧跟这 
种颜色。输入样例：
1
2 2 1
1
1 输出描述：
对于每组测试数据，输出一行一个数字表示牛牛的涂色方案。输出样例
2
块栅栏排成一排，为了给单调的牧场生活增添一份乐趣，牛牛决定为这 块栅栏涂色。现在，牛牛在牧场中一共找到了
种不同颜料，每种颜料都有自己的推荐方案，如：第 种颜料罐上写着，在这种颜料后如果紧跟 这 种颜料中的一个，整体色调就会显得不那么美丽。那么，在满足上述前提下，牛牛最终完成的美丽的涂色一共会有多少种方案？
由于答案可能很大，所以只需要求出对
取模后的结果。
输入描述：
本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。对于每组测试数据，第一行输入三个正整数
，代表栅栏总数，颜料总数以及每种颜料后不能紧跟的颜料种类数。接下去
行，每行输入 个正整数，，代表该种颜料后不能紧跟这 种颜色。输入样例：
1
2 2 1
1
1 输出描述：
对于每组测试数据，输出一行一个数字表示牛牛的涂色方案。输出样例
2
5.
牛牛的近亲数
牛牛在研究数字，他非常喜欢各数位之间数字差异小的数。所以他定义了一种“近亲数”，他规定一个正整数中如果最大数字<=最小数字*2，那么这个正整数数就叫做近亲数。
举个例子，1,9,11,968,874都是近亲数，10,625,407,33542都不是近亲数。
牛牛想知道闭区间[L,R]中共有多少个近亲数，你能告诉牛牛吗？
输入描述：
第一行一个正整数T代表查询次数。
接下来两行每行两个正整数L,R，代表要查询的区间。
输入样例： 3 1 9 21 21 13 20 输出描述： 输出T行，每行一个整数，代表闭区间[L,R]中近亲数的个数。输出样例 9 1 0
6.
n个数的和
初始有两个长度均为 
的数组 
和 
.
牛牛想在其中选出
个数求和，选数的规则如下：
1. 每个
数组中的数只能被选择一次，而每个 
数组中的数可以被选择无数次。
2. 想要选择
数组中的数，就必须先选择 
数组中相同下标的数。例如：想要选择 
，就必须先选择 
.
在上述规则下，最终选出的
个数求和的最大值是多少？
输入描述：
第一行输入一个正整数 
，代表测试数据组数。
对于每组测试数据，第一行输入两个正整数
，依次代表需要找 
个数求和以及
数组的长度。
接下去
行，每行两个正整数 
.输入样例：
1
6 3
6 0
1 6
4 3 输出描述：
对于每组测试数据，一行输出一个正整数代表答案。输出样例
31
的数组 和 .牛牛想在其中选出
个数求和，选数的规则如下：1. 每个
数组中的数只能被选择一次，而每个 数组中的数可以被选择无数次。2. 想要选择
数组中的数，就必须先选择 数组中相同下标的数。例如：想要选择 ，就必须先选择 .在上述规则下，最终选出的
个数求和的最大值是多少？
输入描述：
第一行输入一个正整数 ，代表测试数据组数。对于每组测试数据，第一行输入两个正整数
，依次代表需要找 个数求和以及 数组的长度。接下去
行，每行两个正整数 .输入样例：
1
6 3
6 0
1 6
4 3 输出描述：
对于每组测试数据，一行输出一个正整数代表答案。输出样例
31