腾讯音乐娱乐（TME）2021暑期实习生招聘技术类笔试（II）
时长:120分钟 总分:3分
76浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 3 |
1.
军营选择
牛牛是一名新晋营长，需要选择军营建造地点，已知一共有 
个候选地，编号为 
，有 
条道路，使得这 
个候选地之间两两可以到达。
军营选择规则如下：
对于其中一个候选地
而言，如果将该地以及其直接相连的道路全都删除，就可以得到若干个连通块，用 
记录下其中的最大连通块中的候选地数量。
对于所有的满足
的候选地 
而言，都是最佳军营建造地。
由于最佳地点可能不止一个，所以牛牛想要通过一些操作将该地点唯一化：
首先，牛牛会封闭一条已经存在的道路，接着，构建一条新道路，在这两个操作之后，这
条道路依然可以使 
个地点两两相通，同时，最佳地点只有一个。
但是，牛牛只擅长指挥军队，并不精通此法，所以，请你给出任意一种可以达成要求的合法方案。 输入描述： 本题为多组测试数据，第一行输入一个正整数
，代表测试数据组数。
对于每组测试数据，第一行输入一个正整数
，代表军营候选地的数量。
接下去
行，每行两个正整数 
，代表候选地 
之间存在一条道路 (无向边)。
数据保证，每组测试数据给出的道路一定可以使
个候选地两两相通，同时，所有测试数据的 
之和不会超过 
.输入样例：
2
3
1 2
1 3
4
1 2
1 3
4 3 输出描述：
对于每组测试数据，输出两行，第一行输出两个正整数 
，代表封闭原道路 
，这条道路必须存在。
第二行输出两个正整数
，代表增加一条道路 
，这条道路必须在原道路中不存在或者已经被封闭。
由于是无向边，所以输出
等价于 
.
如果存在多种解，任意输出一种即可，只需要保证满足题意。输出样例 1 2 2 1 3 4 4 1
个候选地，编号为 ，有 条道路，使得这 个候选地之间两两可以到达。军营选择规则如下：
对于其中一个候选地
而言，如果将该地以及其直接相连的道路全都删除，就可以得到若干个连通块，用 记录下其中的最大连通块中的候选地数量。对于所有的满足
的候选地 而言，都是最佳军营建造地。由于最佳地点可能不止一个，所以牛牛想要通过一些操作将该地点唯一化：
首先，牛牛会封闭一条已经存在的道路，接着，构建一条新道路，在这两个操作之后，这
条道路依然可以使 个地点两两相通，同时，最佳地点只有一个。但是，牛牛只擅长指挥军队，并不精通此法，所以，请你给出任意一种可以达成要求的合法方案。 输入描述： 本题为多组测试数据，第一行输入一个正整数
，代表测试数据组数。对于每组测试数据，第一行输入一个正整数
，代表军营候选地的数量。接下去
行，每行两个正整数 ，代表候选地 之间存在一条道路 (无向边)。数据保证，每组测试数据给出的道路一定可以使
个候选地两两相通，同时，所有测试数据的 之和不会超过 .输入样例：
2
3
1 2
1 3
4
1 2
1 3
4 3 输出描述：
对于每组测试数据，输出两行，第一行输出两个正整数 ，代表封闭原道路 ，这条道路必须存在。第二行输出两个正整数
，代表增加一条道路 ，这条道路必须在原道路中不存在或者已经被封闭。由于是无向边，所以输出
等价于 .如果存在多种解，任意输出一种即可，只需要保证满足题意。输出样例 1 2 2 1 3 4 4 1
2.
狡猾的雇主
一位雇主想要招聘一个工人，有
个人前来应聘，这位雇主让每个人写下期望的薪资，然后再进行选择。
个人前来应聘，这位雇主让每个人写下期望的薪资，然后再进行选择。 因为这个雇主十分狡猾，ta会选择期望薪资最低的人，但是这个人可能不是唯一的，为了避免纠纷，ta会选择在没有和其他人提出的期望薪资相同的情况下期望薪资最低的人录用。
求这个最低薪资，如果没有合适的人，则输出
输入描述：
第一行一个整数
第二行
个整数表示
个人提出的期望薪资
个整数表示个人提出的期望薪资保证所有输入的数为正整数且不超过
输入样例：
3
3 2 1 输出描述：
一行一个整数表示答案输出样例
1
3.
三国鼎立
在
的棋盘格状土地上盘踞着三个国家的若干股势力，上下左右相邻的属于同一个国家的土地被认为是同一股势力。现在想知道，土地上总共有多少股势力？
的棋盘格状土地上盘踞着三个国家的若干股势力，上下左右相邻的属于同一个国家的土地被认为是同一股势力。现在想知道，土地上总共有多少股势力？ 数据范围： 
要求：空间复杂度
， 时间复杂度 
输入描述：
第一行两个正整数，土地宽要求：空间复杂度
， 时间复杂度 
，长
；接下来一个
个矩阵，今包含
，表示土地上的国家分布。输入样例： 4 4 1122 1222 3111 3333 输出描述： 一个正整数，势力股数。输出样例 4
