【2022】贝壳找房秋招前端工程师笔试卷2
时长:120分钟 总分:90分
133浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 4 |
1.
中位特征值
给你一棵以T为根，有n个节点的树。（n为奇数）每个点有一个价值V，并且每个点有一个特征值P。每个点的特征值P为：以这个点为根的子树的所有点（包括根）的价值的和。现在牛牛想知道这n个点对应的特征值的中位数是多少，你能告诉牛牛吗？
输入描述：
输入样例：
1 3
1 10 100
1 2
2 3 输出描述：
输出一行，共一个正整数，代表n个点特征值的中位数是多少。输出样例
110
第一行两个正整数，分别代表T和n。
接下来一行共n个正整数，分别代表编号为i的点的价值V[i]。
接下来n-1行，每行两个正整数u,v，代表u和v之间有一条边相连。
2.
牛牛拉票
牛客网即将通过投票选举新一代的牛王。
牛牛暗地里打听到，只要他的票数不少于L，那就一定会当选。
于是他开始拼命的进行拉票，已知开始时他有S张票，第二天，他的票数会变为
，第三天他的票数会变为
，以此类推
对于每组测试数据，输入四个整数，表示L, D, S, C
输入样例： 2 1 2 1 1 6 2 2 1 输出描述： 输出共有T行
对于每组数据，若牛牛的票数不少于L，则输出YES，否则输出NO
输出样例 YES NO
牛牛暗地里打听到，只要他的票数不少于L，那就一定会当选。
于是他开始拼命的进行拉票，已知开始时他有S张票，第二天，他的票数会变为
，第三天他的票数会变为，以此类推 现在他想知道第D天，他的票数是否不少于L票
输入描述：
第一行一个整数T，表示测试数据组数对于每组测试数据，输入四个整数，表示L, D, S, C
输入样例： 2 1 2 1 1 6 2 2 1 输出描述： 输出共有T行
对于每组数据，若牛牛的票数不少于L，则输出YES，否则输出NO
输出样例 YES NO
3.
对角填数
已知一个 
的矩形填数结果如下：
那么，对于任意一个
的矩形，规则为，先填好对角线，再往右上填好，再到最左下，再往右上，再左下......，每个数字出现一次，且不大于边长的乘积，需把
数字不重不漏的填入矩形，能否快速输出其填数结果？
输入描述：
本题为多组测试数据，第一行输入一个正整数 
，代表测试数据的组数。
接下去
行，每行输入一个正整数 
，代表矩形边长。输入样例：
2
3
6 输出描述：
对于每组测试数据，输出一个 
行 
列的矩形，代表填数结果。输出样例
1 4 7
8 2 5
6 9 3
1 7 13 19 25 31
32 2 8 14 20 26
27 33 3 9 15 21
22 28 34 4 10 16
17 23 29 35 5 11
12 18 24 30 36 6
的矩形填数结果如下：那么，对于任意一个
的矩形，规则为，先填好对角线，再往右上填好，再到最左下，再往右上，再左下......，每个数字出现一次，且不大于边长的乘积，需把数字不重不漏的填入矩形，能否快速输出其填数结果？
输入描述：
本题为多组测试数据，第一行输入一个正整数 ，代表测试数据的组数。接下去
行，每行输入一个正整数 ，代表矩形边长。输入样例：
2
3
6 输出描述：
对于每组测试数据，输出一个 行 列的矩形，代表填数结果。输出样例
1 4 7
8 2 5
6 9 3
1 7 13 19 25 31
32 2 8 14 20 26
27 33 3 9 15 21
22 28 34 4 10 16
17 23 29 35 5 11
12 18 24 30 36 6
4.
移动括号
给定一个长度为
(
一定是偶数) 的仅含有 "(" 和 ")" 的括号序列，其中，"(" 有 
个，")" 也有 
个。
牛牛可以进行若干次操作，每一次操作，选择一个下标
，然后将该下标位置上的括号移动到整个序列的开头或者末尾。
那么，牛牛最少需要操作多少次，可以将该括号序列转化成一个常规括号序列？
"()" 是一个常规括号序列；
若
是一个常规括号序列，那么 "(" +
+ ")" 也是一个常规括号序列；
若
是一个常规括号序列，
也是一个常规括号序列，那么 
也是一个常规括号序列。
输入描述：
本题为多组测试数据，第一行输入一个正整数 
，代表测试数据的组数。
对于每组测试数据，第一行输入一个正整数
，代表括号序列的长度。
第二行输入一个长度为
的满足题意的括号序列。输入样例：
3
6
()()()
6
)))(((
18
))(((())()()()())( 输出描述：
对于每组测试数据，一行输出一个整数，代表需要的最小操作次数。输出样例
0
3
2
(一定是偶数) 的仅含有 "(" 和 ")" 的括号序列，其中，"(" 有 个，")" 也有 个。牛牛可以进行若干次操作，每一次操作，选择一个下标
，然后将该下标位置上的括号移动到整个序列的开头或者末尾。那么，牛牛最少需要操作多少次，可以将该括号序列转化成一个常规括号序列？
"()" 是一个常规括号序列；
若
是一个常规括号序列，那么 "(" + + ")" 也是一个常规括号序列；若
是一个常规括号序列， 也是一个常规括号序列，那么 也是一个常规括号序列。
输入描述：
本题为多组测试数据，第一行输入一个正整数 ，代表测试数据的组数。对于每组测试数据，第一行输入一个正整数
，代表括号序列的长度。第二行输入一个长度为
的满足题意的括号序列。输入样例：
3
6
()()()
6
)))(((
18
))(((())()()()())( 输出描述：
对于每组测试数据，一行输出一个整数，代表需要的最小操作次数。输出样例
0
3
2