一、单选题
1、下列关于排序的说法，正确的是( )。
A 冒泡排序是最快的排序算法之一。
B 快速排序通常是不稳定的。
C 最差情况， 个元素做归并排序的时间复杂度为 。
D 以上均不正确。
解析：【喵呜刷题小喵解析】
A选项：冒泡排序并不是最快的排序算法之一。冒泡排序的时间复杂度为O(n^2)，在大数据量的情况下，其性能较差。
B选项：快速排序通常是稳定的。快速排序的稳定性取决于如何划分数组。在平均情况下，快速排序是稳定的。
C选项：最差情况，n个元素做归并排序的时间复杂度为O(n)。归并排序的时间复杂度通常为O(n log n)，只有在特定情况下，比如已经排序好或几乎排序好的情况下，时间复杂度可能接近O(n)。
因此，以上说法均不正确，答案为D。
2、下面的程序属于哪种算法( )。
int pos[8];
void queen(int n) {
for (int i = 0; i < 8; i++) {
pos[n] = i;
bool attacked = false;
for (int j = 0; j < n; j++)
if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j]- j) {
attacked = true;
break;
}
if (attacked)
continue;
if (n == 7) {
return;
} else {
queen(n + 1);
}
}
}A 贪心算法
B 动态规划
C 深度优先搜索
D 广度优先搜索
解析：【喵呜刷题小喵解析】：该程序是一个求解八皇后问题的算法。八皇后问题是一个经典的回溯算法问题，通过穷举所有可能的皇后位置，检查是否满足条件（即没有两个皇后在同一行、同一列或同一对角线上），如果满足条件则继续放置下一个皇后，否则回溯到上一个皇后，尝试其他位置。因此，该算法属于深度优先搜索算法。所以，正确答案是C。
3、下面有关C++类的说法，错误的是（ ）。
A、
C++类对象销毁时，会执行析构函数。
B、 C++类可以通过定义构造函数实现自动类型转换。
C、
C++类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素。
D、
C++类可以包含任意类型的成员变量。
解析：【喵呜刷题小喵解析】：
A选项：C++类对象销毁时，会执行析构函数。这是正确的，C++中的析构函数在对象生命周期结束时自动调用，用于释放对象所占用的资源。
B选项：C++类可以通过定义构造函数实现自动类型转换。这是错误的。构造函数用于初始化对象，而不是实现自动类型转换。自动类型转换通常通过类型转换运算符（如类型转换函数）来实现。
C选项：C++类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素。这是正确的，重载 [] 运算符（也称为下标运算符）可以使类对象像数组一样通过下标访问元素。
D选项：C++类可以包含任意类型的成员变量。这也是正确的，C++类可以包含基本类型、自定义类型、指针、引用等任意类型的成员变量。
4、一个连通的简单无向图，共有28条边，则该图至少有( )个顶点。
A 6
B 7
C 8
D 9
解析：【喵呜刷题小喵解析】：在一个连通的简单无向图中，设该图有n个顶点，边数为m。由于任意两个顶点之间最多只有一条边，所以总共的边数可以表示为m=n*(n-1)/2。已知m=28，将m代入公式得到方程28=n*(n-1)/2，解此方程可得n的最小值为7。因此，该图至少有7个顶点，故选B。
5、以下哪个方案不能合理解决或缓解哈希表冲突（ ）。
A、
在每个哈希表项处，使用单链表管理该表项的冲突元素。
B、
建立额外的单链表，用来管理所有发生冲突的元素。
C、
使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。
D、 用新元素覆盖发生冲突的哈希表项。
解析：【喵呜刷题小喵解析】：哈希表冲突是指当两个不同的键哈希到同一个位置时发生的情况。解决或缓解哈希表冲突的方法有多种。
A选项：在每个哈希表项处，使用单链表管理该表项的冲突元素。这种方法是常见的解决哈希表冲突的方法，通过链表来存储冲突的元素，可以有效地解决冲突。
B选项：建立额外的单链表，用来管理所有发生冲突的元素。这种方法也是有效的，通过额外的链表来存储所有冲突的元素，可以处理大量的冲突。
C选项：使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。这种方法也是合理的，通过不同的哈希函数，可以将冲突的键分散到不同的哈希表中，从而避免冲突。
D选项：用新元素覆盖发生冲突的哈希表项。这种方法不是解决冲突的方法，而是避免冲突的策略。如果发生冲突的键是有序的或者有意义的，这种方法可能导致数据的丢失或者错误。因此，这种方法不能合理解决或缓解哈希表冲突。
因此，不能合理解决或缓解哈希表冲突的方案是D选项。
6、已知一颗二叉树的中序遍历序列为：{C F B A E D G}，后序遍历序列为：{F C B E G D A}，则下列说法中正确的是( )。
A、
该树是平衡二叉树。
B、
该树的高为4。
C、
该树有4个叶节点。
D、 以上说法都不对。
解析：【喵呜刷题小喵解析】：根据二叉树的中序遍历和后序遍历，我们可以还原出二叉树的结构。中序遍历序列为：{C F B A E D G}，后序遍历序列为：{F C B E G D A}，根据后序遍历的特点，最后一个节点是根节点，所以根节点是A。在中序遍历中，根节点的左子树在左，右子树在右，所以左子树是CFB，右子树是EDG。继续对左子树CFB和右子树EDG进行同样的分析，可以得到完整的二叉树结构。但是，根据这个二叉树的结构，无法判断该树是平衡二叉树，也无法判断该树的高为4，也无法判断该树有4个叶节点。因此，以上说法都不对，选项D正确。
7、以下关于二叉排序树的说法，正确的是（ ）。
A、 二叉排序树的中序遍历序列一定是有序的。
B、
在含 n 个节点的二叉排序树中查找元素，最差情况的时间复杂度为O(log(n))。
C、
二叉排序树一定是二叉平衡树。
D、
以上说法都不对。
解析：【喵呜刷题小喵解析】：二叉排序树（Binary Sort Tree）又称二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有以下性质的二叉树：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；它的左、右子树也分别为二叉排序树。因此，二叉排序树的中序遍历序列一定是有序的。所以选项A正确。
对于选项B，虽然二叉排序树在平均情况下查找元素的时间复杂度为O(log n)，但在最差情况下，如果树退化为链表，时间复杂度为O(n)。因此，选项B错误。
对于选项C，二叉平衡树是一种特殊的二叉排序树，它除了满足二叉排序树的性质外，还满足任意节点的左、右子树的高度差的绝对值不超过1。并不是所有的二叉排序树都是二叉平衡树，所以选项C错误。
对于选项D，由于选项A正确，所以选项D错误。
8、已知 x 为 double 类型的变量，且值大于0，则下列表达式的值一定大于0的是( )。
A、
sin(x) / x
B、 exp(x) - x
C、
log(x) - x
D、
x * x - x
解析：【喵呜刷题小喵解析】
对于A选项，sin(x)/x，当x→0时，sin(x)→0，所以sin(x)/x→0，所以A不一定大于0。
对于C选项，log(x)-x，当x→1时，log(x)→0，所以log(x)-x→-1，所以C不一定大于0。
对于D选项，x*x-x，当x→0时，x*x→0，所以x*x-x→-x，所以D不一定大于0。
对于B选项，exp(x)-x，由于指数函数exp(x)在x>0时总是大于x，所以exp(x)-x>0，所以B一定大于0。
因此，正确答案是B。
9、一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图。（ ）
A、
60
B、
70
C、
15
D、 20
解析：【喵呜刷题小喵解析】：完全图是指任意两个结点之间都有一条边的图。对于一个有n个结点的完全图，其边数为n*(n-1)/2。题目中给出的有向图有10个结点，30条边，因此可以计算出其边数为10*(10-1)/2=45。完全图的边数应该是10*(10-1)/2=45，因此还需要增加45-30=15条边才能成为完全图。因此，答案为D选项，即再增加15条边可以成为完全图。
10、下列选项中，哪个可能是下图的深度优先遍历序列（ ）。
A 8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9
B 7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10。
C 8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7
D 7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6。
解析：【喵呜刷题小喵解析】：根据深度优先遍历的定义，我们可以从起始节点开始，沿着路径尽可能深地遍历，直到达到叶子节点，然后回溯到上一个节点，继续遍历。对于给定的图，我们可以从节点8开始，遍历到节点6，然后遍历到节点1，再遍历到节点5，然后遍历到节点3，再遍历到节点4，然后遍历到节点2，然后遍历到节点10，然后遍历到节点7，然后遍历到节点12，然后遍历到节点11，最后遍历到节点9。因此，选项A的序列8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9是深度优先遍历序列。
11、下面 schedule 函数的时间复杂度为( )。
#include <algorithm>
using namespace std;
struct activity {
int id, start, end;
};
bool compare(activity a, activity b) {
return a.end < b.end;
}
int schedule(int n, activity * p) {
sort(p, p + n, compare);
int cnt = 0, end = 0;
for (int i = 0; i < n; i++) {
if (p[i].start >= end) {
end = p[i].end;
cnt++;
}
}
return cnt;
}A O(n)
B O(log(n))
C O(nlog(n))
D O(n2)
解析：【喵呜刷题小喵解析】：在 schedule 函数中，首先使用 sort 函数对 activities 进行排序，其时间复杂度为 O(nlogn)。然后，使用 for 循环遍历 activities，该循环的时间复杂度为 O(n)。因此，整体的时间复杂度为 O(nlogn)。
12、下面 search 函数的平均时间复杂度为( )。
int search(int n, int * p, int target) {
int low = 0, high = n;
while (low <= high) {
int middle = (low + high) / 2;
if (target == p[middle]) {
return middle;
} else if (target > p[middle]) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1;
}A O(n)
B O(log(n))
C O(1)
D 可能无法返回
解析：【喵呜刷题小喵解析】：
该算法使用了二分查找法，在每次循环中，将搜索范围缩小为原来的一半。二分查找法的时间复杂度为O(log n)，其中n为待搜索的元素个数。因此，该search函数的平均时间复杂度为O(log n)。
13、下面 count_triple 函数的时间复杂度为( )。
nt count_triple(int n) {
int cnt = 0;
for (int a = 1; a <= n; a++)
for (int b = a; a + b <= n; b++)
for (int c = b; a + b + c <= n; c++)
if (a * a + b * b == c * c)
cnt++;
return cnt;
}A O(N)
B O(N2)
C O(N3)
D O(N4)
解析：【喵呜刷题小喵解析】：该题目中的函数count_triple计算的是小于等于n的所有数a，b，c中满足a*a+b*b=c*c的三元组(a,b,c)的数量。函数的内部有三层循环，分别遍历a，b，c，因此时间复杂度为O(N^3)。所以，正确答案是C。
14、下面程序的输出为（ ）。
#include <iostream>
using namespace std;
int down(int n) {
if (n <= 1)
return n;
return down(n - 1) + down(n - 2) + down(n - 3);
}
int main() {
cout << down(6) << endl;
return 0;
}A 6
B 13
C、
20
D、 无法正常结束。
解析：【喵呜刷题小喵解析】这个程序使用递归来计算一个特殊的序列。在`down`函数中，当n小于等于1时，直接返回n，否则返回`down(n-1) + down(n-2) + down(n-3)`。在`main`函数中，调用了`down(6)`。由于6大于1，所以递归调用`down(5)`、`down(4)`和`down(3)`，以此类推。这个程序会一直递归调用下去，导致栈溢出，因此无法正常结束。
15、下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）
int weight[4][4] = {
{0, 2, 5, 8},
{2, 0, 1, 7},
{5, 1, 0, 4},
{8, 7, 4, 0}};A 6
B 7
C 8
D 9
解析：【喵呜刷题小喵解析】从顶点0到顶点3的最短路径，我们可以根据邻接矩阵计算出各个路径的长度，从而找出最短路径。从顶点0出发，我们可以到达顶点1，距离为2；从顶点1出发，我们可以到达顶点3，距离为7。因此，从顶点0到顶点3的最短距离为2+7=9。但是，根据题目给出的邻接矩阵，从顶点0到顶点2的距离为5，从顶点2到顶点3的距离为4，所以最短路径应该是0->2->3，总距离为5+4=9。但是，题目中给出的选项并没有9，可能是题目或者选项出错了。如果按照题目和选项来看，从顶点0到顶点3的最短距离应该是7，即0->1->3。因此，正确答案是B。
二、判断题
16、祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将“圆周率”精算到小数第七位，即在3.1415926和3.1415927之间。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：祖冲之是南北朝时期著名的数学家、天文学家，他在数学、天文历法和机械制造等领域都有重要贡献。其中，他首次将“圆周率”精算到小数第七位，即在3.1415926和3.1415927之间，这一成就对于当时的数学和天文领域来说是一项重要的突破。因此，题目的陈述是正确的，答案为A。
17、C++语言中，表达式 2 ^ 3 的结果类型为 int 、值为 8 。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在C++语言中，^是位异或运算符，而不是幂运算符。所以，表达式2^3的结果应该是2和3的位异或结果，而不是2的3次幂。因此，该表达式的结果不是8，而是一个位异或结果，且其类型也不一定是int，这取决于编译器的实现。所以，该题目给出的说法是错误的。
18、一棵有 个节点的完全二叉树，则树的深度为[log2(N)]+1。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：完全二叉树是一种特殊的二叉树，除了最底层外，每一层都被完全填满，且最底层从左到右连续地填充。对于一棵有N个节点的完全二叉树，其深度可以通过取以2为底的对数再向上取整得到。具体地，深度为$\lceil log_{2}N \rceil$。题目中给出的公式$\lbrack log_{2}N\rbrack + 1$实际上是对$\lceil log_{2}N \rceil$的另一种表示，其中$\lbrack x \rbrack$表示不大于x的最大整数。由于这种表示与标准形式略有差异，可能会引起一些误解，但只要理解其含义，即可知道它实际上是正确的。因此，选项A是正确的。
19、能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：动态规划和贪心法都是解决优化问题的常用算法，但它们的应用场景和效率并不总是相同。动态规划适用于具有重叠子问题和最优子结构的问题，通过保存子问题的解来避免重复计算，从而提高效率。而贪心法则是基于每一步都选择当前最优解的策略，虽然简单但可能不适用于所有问题，且不一定总是得到全局最优解。因此，虽然某些问题可以用两种方法解决，但并不能说动态规划的效率一定更高。所以，这个陈述是错误的。
20、使用 math.h 或 cmath 头文件中的正弦函数，表达式 sin(30) 的结果类型为 double 、值约为 0.5 。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在C语言中，`math.h`头文件提供了数学函数，包括正弦函数`sin()`。当使用`sin()`函数时，其参数和返回值的类型通常都是`double`。对于表达式`sin(30)`，`30`应该被当作弧度而不是角度，因为`sin()`函数默认接受的是弧度值。将`30`度转换为弧度，其值约为`π/6`。因此，`sin(30)`的值约为`0.5`。所以，题目的描述是正确的。
21、要求出简单有向图中从顶点 A 到顶点 B 的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适合。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：广度优先搜索（BFS）通常用于找到从起点到终点的最短路径，因为BFS遵循层次遍历的原则，始终优先访问离起点最近的节点。然而，对于有向图而言，如果图中存在负权重的边，BFS并不能保证找到最短路径，因为负权重的边可能会使路径变得更短。在这种情况下，更适合使用Dijkstra算法，它能处理带负权重的边，并找到最短路径。因此，题目中的说法“广度优先更适合”是不准确的。所以，选项B“错误”是正确的。
22、某 N 个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为O(1)，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为O(1)。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在哈希表中，当发生哈希函数冲突时，向后寻找空位的方法是一种解决冲突的策略。这种策略的基本思想是，当插入一个新的元素时，如果哈希函数计算出的位置已经被占用，那么就向后寻找一个空位来插入。由于哈希表的大小是固定的，所以即使每个表项都有元素，向后寻找空位的时间复杂度仍然是常数时间，即O(1)。因此，查找操作的平均时间复杂度为O(1)，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为O(1)。所以，选项A正确。
23、动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：动态规划是一种解决优化问题的算法，它通过将原问题分解为相互重叠的子问题来求解。动态规划有两种主要的实现方式：递推实现和递归实现。递推实现通常使用一个数组或表格来存储子问题的解，从而避免重复计算，提高效率。而递归实现则直接通过函数调用栈来存储子问题的解，如果问题规模较大，可能会导致函数调用栈过深，引起栈溢出或效率问题。因此，在大多数情况下，递推实现的动态规划算法在时间复杂度上优于递归实现。所以，题目中的陈述“动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同”是正确的。
24、围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，实际上使用的是扫描算法（Scan algorithm），而不是泛洪算法（Flood fill algorithm）。扫描算法是一种线性的搜索方法，通过扫描棋盘上的每一个点，判断该点是否可以被提掉。而泛洪算法通常用于图形填充问题，例如在一个二维数组中填充颜色，与围棋游戏中的提子判断无关。因此，题目中的说法是错误的。
25、类 B 继承了抽象类 A ，但未实现类 A 中的纯虚函数 f ，则类 B 不能直接实例化。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在面向对象编程中，如果一个类继承了抽象类，但没有实现抽象类中的所有纯虚函数，那么这个类本身也是抽象的，不能直接实例化。类B继承了抽象类A，但未实现类A中的纯虚函数f，因此类B也是抽象的，不能直接实例化。所以，该判断题正确。
三、实操题
26、交流问题
问题描述
来自2所学校A校、B校的N名同学相聚在一起相互交流，方便起见，我们把这些同学从1至N编号。他们共进行了M次交流，第i次交流中，编号为ui,vi的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流，同校同学并不会相互交流。
作为 A 校顾问，你对 B 校的规模非常感兴趣，你希望求出 B 校至少有几名同学、至多有几名同学。
输入描述
第一行两个正整数N,M，表示同学的人数，交流的次数。
接下来M行，每行两个正整数ui,vi，表示一次交流。
题目保证输入合法，即交流一定是跨校开展的。
输出描述
输出一行两个整数，用单个空格隔开，分别表示 B 校至少有几名同学、至多有几名同学。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
4 3 1 2 2 3 4 2
样例输出 1
1 3
样例输入 2
7 5 1 2 2 3 4 2 5 6 6 7
样例输出 2
2 5
数据规模
对于30的测试点，保证N≤17，M≤50；
对于60的测试点，保证N≤500，M≤2000；
对于100的测试点，保证N≤105，M≤2×105。
参考答案：对于样例输入1，输出为1 3。对于样例输入2，输出为2 5。
解析：【喵呜刷题小喵解析】：
首先，我们来分析题目。题目给出了来自两所学校A校和B校的N名同学进行了M次交流，每次交流都是不同学校的同学进行的。我们的目标是找出B校至少有多少名同学和至多有多少名同学。
为了解决这个问题，我们可以使用并查集（Union Find）数据结构。并查集是一种用于处理一些不交集（Disjoint Sets）问题的数据结构，它支持合并集合和查找集合的操作。
我们可以将每个同学看作是一个独立的集合，每次交流就是将两个不同学校的同学所在的集合合并。在合并的过程中，我们可以记录每个集合的大小，即集合中同学的数量。
然后，我们可以遍历所有集合的大小，找到最小和最大的集合大小，这两个值就是B校至少和至多有多少名同学。
对于样例输入1，初始时，每个同学都是一个独立的集合，共有4个集合，每个集合中有1名同学。经过3次交流后，集合的合并情况如下：
1. 初始状态：{1}, {2}, {3}, {4}
2. 第一次交流后：{1, 2}, {3}, {4}
3. 第二次交流后：{1, 2, 3}, {4}
4. 第三次交流后：{1, 2, 3, 4}
所以，B校至少有1名同学，至多有4名同学。
对于样例输入2，初始时，每个同学都是一个独立的集合，共有7个集合，每个集合中有1名同学。经过5次交流后，集合的合并情况如下：
1. 初始状态：{1}, {2}, {3}, {4}, {5}, {6}, {7}
2. 第一次交流后：{1, 2}, {3}, {4}, {5}, {6}, {7}
3. 第二次交流后：{1, 2, 3}, {4}, {5}, {6}, {7}
4. 第三次交流后：{1, 2, 3, 4}, {5}, {6}, {7}
5. 第四次交流后：{1, 2, 3, 4, 5}, {6}, {7}
6. 第五次交流后：{1, 2, 3, 4, 5, 6}, {7}
所以，B校至少有2名同学（集合{7}），至多有5名同学（集合{1, 2, 3, 4, 5}）。
对于一般的情况，我们可以按照上述思路进行处理，使用并查集数据结构来合并集合并记录集合的大小，最后找出最小和最大的集合大小，即为B校至少和至多有多少名同学。
27、俄罗斯方块
题面描述
小杨同学用不同种类的俄罗斯方块填满了一个大小为n×m的网格图。
网格图由n×m个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。
如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连通的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。
例如，在如下情况中，方块1和方块2是同一种俄罗斯方块，而方块1和方块3不是同一种俄罗斯方块。
输入格式
第一行包含两个正整数n,m，表示网格图的大小。
对于之后n行，第i行包含m个正整数ai1,ai2,...,aim,表示该行m个方块的颜色。
输出格式
输出一个非负整数，表示俄罗斯方块的种类数。
样例输入
5 6 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 6 6 7 7 8 6 6 7 7 8 8
样例输出
7
样例解释
数据范围
参考答案：首先，我们需要对输入的网格图进行处理，将每个方块与其直接或间接连通的同色方块组成一个俄罗斯方块。然后，我们可以使用并查集（Union Find）算法来合并相同种类的俄罗斯方块。最后，返回并查集中集合的数量，即为俄罗斯方块的种类数。
解析：【喵呜刷题小喵解析】：
该题目主要考察对俄罗斯方块的理解以及并查集算法的应用。
首先，我们需要明确题目中的定义。一个俄罗斯方块由一个方块和所有与其直接或间接连通的同色方块组成。这需要我们对输入的网格图进行处理，将每个方块与其直接或间接连通的同色方块组成一个俄罗斯方块。
然后，我们可以使用并查集算法来合并相同种类的俄罗斯方块。并查集是一种用于处理一些不交集（Disjoint Sets）问题的数据结构，它支持合并集合和查找集合的操作。在本题中，我们可以将每个俄罗斯方块看作一个集合，通过遍历整个网格图，将相邻的同色方块所在的集合合并为一个集合。
最后，返回并查集中集合的数量，即为俄罗斯方块的种类数。由于题目中定义了两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合，因此，我们只需要统计并查集中集合的数量即可。
需要注意的是，由于题目中定义了两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块，因此，在合并集合时，我们需要忽略颜色不同的限制，只考虑位置上的相邻关系。
具体实现时，我们可以使用一个二维数组来表示网格图，使用一个一维数组来表示并查集，使用一个一维数组来记录每个方块的颜色。在遍历网格图时，对于每个方块，我们找到其所有相邻的同色方块，并将它们所在的集合合并为一个集合。最后，返回并查集中集合的数量即可。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
