GESP第九次认证真题解析|C++四级真题回顾

一、单选题（每题2分，共30分）

第1题 关于下述代码，说法错误的是（ ）。

A.函数multiply的定义应该放到函数main之前。

B.函数声明int multiply(int x, int y);中明确指定了函数multiply()的返回值为整数类型。

C.在main函数中，函数multiply通过multiply(a, b)被调用，其中a和b是定义在main函数中的变量，它们作为实参传递给了multiply函数的形参x和y。

D.运行上述代码，将输出The result is: 20。【答案】A

【考纲知识点】 函数声明与定义、函数调用与参数传递、函数返回值

【解析】

这段C++代码实现了一个简单的乘法函数multiply，并在main函数中调用该函数进行乘法运算，最后输出结果。

各选项分析

选项A：函数multiply的定义不一定要放到函数main之前。在C++中，函数声明可以提前告知编译器函数的存在、返回值类型和参数列表，这样即使函数定义在调用之后，编译器也能正确处理函数调用。本题中int multiply(int x, int y);就是函数声明，有了这个声明，main函数中就可以正常调用multiply函数，所以该选项说法错误。

选项B：函数声明int multiply(int x, int y);明确指定了函数multiply的返回值为整数类型int，该选项说法正确。

选项C：在main函数中，multiply(a, b)调用了multiply函数，其中a和b是main函数中定义的变量，作为实参传递给了multiply函数的形参x和y，该选项说法正确。

选项D：multiply函数实现了两个整数的乘法运算，a = 4，b = 5，调用multiply(a, b)得到的结果是4 * 5 = 20，最后输出The result is: 20，该选项说法正确。

综上，答案是A。

第2题 执行下述代码将输出（ ）。

A. 2020

B. 2010

C. 1010

D.编译错误

【答案】B

【考纲知识点】 变量作用域、函数调用与输出

【解析】

代码分析

1.首先定义了一个全局变量x并初始化为10。

2.在func函数中，又定义了一个局部变量x并初始化为20。在func函数内部，std::cout << x;输出的是局部变量x的值，即20。因为在函数内部，局部变量会覆盖同名的全局变量，所以这里输出的是20。

3.在main函数中调用func函数后，接着执行std::cout << x;。此时，这里的x是全局变量x，因为在main函数中没有定义与全局变量x同名的局部变量，所以输出的是全局变量x的值，即10。

综上，最终的输出结果是2010，答案选B。

第3题 执行下述代码后，变量a的值为（ ）。

A. 10

B. 20

C.随机值

D.编译错误

【答案】

【考纲知识点】 指针的概念与使用、变量的内存操作

【解析】

代码分析

inta =10; //定义一个整型变量a，并初始化为10int*p =&a; //定义一个整型指针p，并将变量a的地址赋值给p，此时p指向变量a*p=20; //通过指针p解引用操作，将指针p所指向的变量（即a）的值修改为20

1.int a = 10;：定义了一个整型变量a，并将其初始值设为10。

2.int* p = &a;：定义了一个整型指针p，使用取地址运算符&获取变量a的地址，并将该地址赋值给指针p。这样，指针p就指向了变量a。

3.*p = 20;：使用解引用运算符*对指针p进行解引用操作，解引用后得到的是指针p所指向的变量，也就是变量a。然后将20赋值给解引用后的结果，相当于直接修改了变量a的值。

所以，执行完上述代码后，变量a的值变为20，答案选B。

第4题 以下哪种参数传递方式可以避免拷贝大型对象？

A.只能用值传递

B.只能用引用传递

C.只能用指针传递

D.引用传递和指针传递均可

【答案】D

【考纲知识点】 函数参数传递的不同方式

【解析】

值传递：在值传递方式中，函数调用时会将实参的值复制一份传递给形参，对于大型对象，这种拷贝操作会消耗较多的时间和内存空间。

引用传递：引用传递是将实参的引用（本质上是实参的别名）传递给函数，函数中对形参的操作实际上就是对实参的操作，不会发生对象的拷贝，从而避免了拷贝大型对象带来的开销。

指针传递：指针传递是将实参的地址传递给函数，函数通过指针来访问和操作实参所指向的对象，也不会进行对象的拷贝，同样可以避免拷贝大型对象。

所以引用传递和指针传递均可避免拷贝大型对象，答案是D。

第5题 执行下述代码，将输出（ ）。

A. 12

B. 21

C. 22

D. 11

【答案】A

【考纲知识点】 函数参数传递方式、函数调用与变量作用域

【解析】

代码分析

函数swap的参数传递方式：

函数swap有两个参数，第一个参数a是值传递，第二个参数b是引用传递。

值传递是将实参的值复制一份传递给形参，在函数内部对形参的修改不会影响到实参。引用传递是将实参的引用（即别名）传递给形参，在函数内部对形参的修改会直接影响到实参。

函数调用过程：

在main函数中，定义了两个整型变量x = 1 和y = 2。

调用swap(x, y) 时，x的值被复制给swap函数的形参a，y的引用被传递给swap函数的形参b。

在swap函数内部，执行int temp = a; a = b; b = temp; 语句，交换了a和b的值。由于a是值传递，a的改变不会影响到x；而b是引用传递，b的改变会影响到y，此时y的值变为1。

输出结果：

在main函数中，调用swap函数后，x的值仍然是1，y的值变为1，所以std::cout << x << y; 输出的结果是11。

综上，答案选A。

第6题 下面的描述中，（ ）正确定义一个名为Person的结构体并正确初始化了一个Person结构体的变量p。

A.

B.

C.

D.【答案】C

【考纲知识点】 结构体的定义与使用

【解析】

各选项分析

选项A：该结构体定义中没有定义构造函数，而Person p("Yang", 10);试图使用类似构造函数的方式初始化结构体变量，在没有自定义构造函数的情况下，这种初始化方式是错误的。所以选项A不正确。

选项B：在结构体定义中，string name, 后面的逗号使用错误，应该是分号;来结束成员变量的声明。所以该结构体定义存在语法错误，选项B不正确。

选项C：此结构体定义正确，并且使用初始化列表的方式对结构体变量p进行初始化，按照成员变量的顺序依次赋值，这种初始化方式是符合C++语法规则的。所以选项C正确。

选项D：new运算符用于动态分配内存，返回的是一个指向对象的指针。而Person p 定义的是一个结构体变量，不是指针类型。不能将指针赋值给结构体变量，这种赋值方式存在类型不匹配的错误。所以选项D不正确。

综上，答案选C。

第7题 给定如下代码，

下面描述错误的是（ ）。

A.结构Person内嵌套结构Address

B. Person 有一个Address类型的address成员

C.一个Person类型的变量p的address的初始化可以写成：p.address.street = "123 Main St"; p.address.city = "Anytown";

D.结构的嵌套可以减少命名冲突，因此可以不必控制嵌套层次

【答案】D

【考纲知识点】 结构体嵌套

【解析】

代码分析

struct Person {     std::string name;     int age;     struct Address {         std::string street;         std::string city;     };     Address address;};

此代码定义了一个Person结构体，其中嵌套了一个Address结构体，并且Person结构体有一个Address类型的成员address。

各选项分析

选项A：从代码中可以明显看出，Address结构体定义在Person结构体内部，所以结构Person内嵌套结构Address，该选项描述正确。

选项B：代码中Person结构体包含一个Address类型的成员address，即Address address;，该选项描述正确。

选项C：对于一个Person类型的变量p，可以通过p.address.street和p.address.city来访问和初始化address成员的street和city属性，如p.address.street = "123 Main St"; p.address.city = "Anytown";，该选项描述正确。

选项D：虽然结构体的嵌套在一定程度上可以减少命名冲突，但过多的嵌套会增加代码的复杂度，降低代码的可读性和可维护性。因此，在实际编程中需要控制嵌套层次，避免过度嵌套。所以该选项描述错误。

综上，答案选D。

第8题 假设int arr[2][3] = {{1,2,3},{4,5,6}};，则arr[1][2]的值是（ ）。

A. 2

B. 3

C. 5

D. 6

【答案】D

【考纲知识点】 二维数组的定义与访问

【解析】

这里定义了一个2行3列的二维数组arr，并进行了初始化。二维数组可以看作是一个矩阵，其中第一个下标表示行号，第二个下标表示列号，且下标都是从0开始计数的。

所以，arr[1][2]的值是6，答案选D。

第9题 下面（ ）正确定义了二维数组。

A. int arr[3,4];

B. int arr[3][4];

C. int arr(3,4);

D. int a[3-4];

【答案】B

【考纲知识点】 二维数组定义

【解析】

选项A：int arr[3,4]; 这种定义方式是错误的，在C++中，二维数组的定义应该使用[][]形式来指定行数和列数，而不是用逗号分隔。

选项B：int arr[3][4]; 是正确的二维数组定义方式，它定义了一个名为arr的二维数组，有3行4列，符合C++中二维数组的定义语法。

选项C：int arr(3,4); 这种方式不是定义二维数组的正确语法，在C++中，定义数组通常使用方括号[]，而不是圆括号()。

选项D：int a[3 - 4]; 定义了一个一维数组，且数组大小为3 - 4 = -1，这是不符合语法规则的，数组大小必须是一个大于等于0的常量表达式。

故正确答案是B。

第10题 小杨正在爬楼梯，需要爬阶才能到达楼顶。如果每次可以爬个或个台阶，下面代码采用递推算法来计算一共有多少种不同的方法可以爬到楼顶，则横线上应填写（ ）。

A.

B.

C.

D.【答案】B

【考纲知识点】 递推算法

【解析】

问题分析

这是一个经典的爬楼梯问题，其核心思想是：到达第n阶楼梯的方法数等于到达第n - 1 阶楼梯的方法数加上到达第n - 2 阶楼梯的方法数。因为每次只能爬1个或2个台阶，所以要到达第n阶，要么是从第n - 1 阶爬1个台阶上来，要么是从第n - 2 阶爬2个台阶上来。

各选项分析

选项A：

res += f1 + f2;f1 = f2;f2 = res;

res += f1 + f2; 这种累加方式不符合状态转移方程，会导致结果错误。正确的做法是直接将f1和f2的和赋值给res，而不是累加。所以选项A错误。

选项B：

res = f1 + f2;f1 = f2;f2 = res;

首先res = f1 + f2; 计算出到达第i阶楼梯的方法数，然后f1 = f2; 将f2的值赋给f1，更新f1为到达第i - 1 阶楼梯的方法数，最后f2 = res; 将res的值赋给f2，更新f2为到达第i阶楼梯的方法数，为下一次循环做准备。这种方式符合递推算法的状态转移方程，是正确的。所以选项B正确。

选项C：

res += f1 + f2;f2 = res;f1 = f2;

同样，res += f1 + f2; 不符合状态转移方程，而且f2 = res; 和f1 = f2; 的顺序会导致f1和f2的值更新错误。所以选项C错误。

选项D：

res = f1 + f2;f2 = res;f1 = f2;

虽然res = f1 + f2; 计算出了到达第i阶楼梯的方法数，但f2 = res; 和f1 = f2; 的顺序会导致f1和f2的值更新错误，没有正确维护递推关系。所以选项D错误。

综上，答案选B。

第11题 给定如下算法，其时间复杂度为（ ）。

A.O(n²)

B.O(n×2ⁿ)

C.O(1)

D.O(n³)【答案】B

【考纲知识点】 算法复杂度分析

【解析】

这段代码的功能是判断数组arr中是否存在若干元素的和等于目标值target。它通过枚举数组元素所有可能的组合来实现这一功能。

时间复杂度分析

外层循环：

外层循环的条件是i < (1 << n)，其中1 << n 表示将1左移n位，其结果为2ⁿ。所以外层循环会执行2ⁿ次。

内层循环：

内层循环的条件是j < n，它会执行n次。

嵌套循环的总执行次数：

由于内层循环嵌套在外层循环内部，对于外层循环的每一次迭代，内层循环都会完整地执行n次。因此，嵌套循环的总执行次数为外层循环执行次数与内层循环执行次数的乘积，即n×2ⁿ。

所以，答案选B。

第12题 下面关于排序稳定性的描述，正确的是（ ）。

A.稳定性指算法的时间复杂度恒定

B.稳定排序保证相同元素的相对顺序不变

C.选择排序是稳定排序

D.插入排序不是稳定排序

【答案】B

【考纲知识点】 排序算法的稳定性

【解析】

各选项分析

选项A：排序算法的稳定性与时间复杂度并无关联。稳定性是指在排序过程中，相等元素的相对顺序是否保持不变；而时间复杂度描述的是算法执行时间随输入规模增长的变化趋势。所以选项A错误。

选项B：稳定排序的定义就是在排序操作中，保证相同元素的相对顺序不变。例如，在一个待排序序列中，如果有两个相等的元素a和b，且a在b之前，那么经过稳定排序后，a仍然会在b之前。所以选项B正确。

选项C：选择排序不是稳定排序。选择排序的基本思想是每次从未排序部分选择最小（或最大）的元素，与未排序部分的第一个元素交换位置。在交换过程中，可能会改变相等元素的相对顺序。例如，序列[5, 8, 5, 2]，第一次选择最小元素2与第一个元素5交换位置后，两个5的相对顺序就发生了改变。所以选项C错误。

选项D：插入排序是稳定排序。插入排序的工作原理是将未排序数据插入到已排序序列的合适位置。在插入过程中，如果遇到相等元素，插入排序会将新元素插入到相等元素的后面，从而保证相等元素的相对顺序不变。所以选项D错误。

综上，答案选B。

第13题 对数组arr[]={5, 3, 8, 1}进行升序排序，执行第一轮冒泡排序后数组arr中的内容为（ ）。

A. 3, 5, 1, 8

B. 3, 1, 5, 8

C. 3, 5, 8, 1

D. 5, 3, 8, 1

【答案】A

【考纲知识点】 冒泡排序算法的基本原理和执行过程

【解析】

冒泡排序的基本思想是重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

对于升序排序的冒泡排序，在每一轮中，会从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。

给定数组arr[] = {5, 3, 8, 1}，进行第一轮冒泡排序的过程如下：

比较第1个元素5和第2个元素3，因为5 > 3，所以交换它们的位置，数组变为{3, 5, 8, 1}。

比较第2个元素5和第3个元素8，因为5 < 8，所以不交换它们的位置，数组仍然是{3, 5, 8, 1}。

比较第3个元素8和第4个元素1，因为8 > 1，所以交换它们的位置，数组变为{3, 5, 1, 8}。

经过第一轮冒泡排序后，数组arr中的内容为{3, 5, 1, 8}，所以答案选A。

第14题 运行下面的代码，将出现（ ）。

A.屏幕上输出Caught: Runtime error occurred.

B.屏幕上输出Caught an unknown exception.

C.程序调用std::terminate()

D.编译错误

【答案】A

【考纲知识点】 异常处理机制

【解析】

代码分析

函数hmean：该函数接受两个双精度浮点数a和b作为参数，计算它们的调和平均数。如果a等于-b，则抛出一个runtime_error类型的异常，异常信息为"Runtime error occurred."。

main函数：

定义了两个双精度浮点数x = 10 和y = -10。

在try块中调用hmean(x, y) 函数，由于x等于-y，hmean函数会抛出runtime_error异常。

异常抛出后，程序会跳出try块，寻找匹配的catch块进行处理。

第一个catch块catch (const runtime_error& e) 用于捕获runtime_error类型的异常，当捕获到该异常时，会输出异常信息。

第二个catch (...) 块用于捕获其他未知类型的异常。

由于hmean函数抛出的是runtime_error类型的异常，程序会进入第一个catch块进行处理，输出Caught: Runtime error occurred.。

所以，答案选A。

第15题 下面哪种方式不能实现将字符串"Happy Spring!"输出重定向到文件log.txt（ ）。

A.

B.

C.

D.【答案】C

【考纲知识点】 文件操作以及输出重定向

【解析】

选项分析

选项A

freopen("log.txt", "w", stdout);cout << "Happy Spring!" << endl;fclose(stdout);

freopen函数用于将标准输出流stdout重定向到指定的文件log.txt。之后使用cout输出的内容都会被写入到log.txt文件中，最后使用fclose(stdout)关闭文件。所以该选项可以实现将字符串输出到文件。

选项B

std::ofstream outFile("log.txt");outFile << "Happy Spring!" << endl;outFile.close();

std::ofstream是C++中用于文件输出的流类，通过创建outFile对象并打开log.txt文件，使用outFile输出字符串到文件，最后关闭文件。因此该选项也能实现将字符串输出到文件。

选项C

std::ofstream outFile("log.txt");cout << "Happy Spring!" << endl;outFile.close();

虽然创建了outFile对象并打开了log.txt文件，但后续使用的是cout进行输出，cout是标准输出流，默认输出到控制台，并没有将输出重定向到文件，所以字符串不会被写入到log.txt文件中。故该选项不能实现将字符串输出到文件。

选项D

ofstream log_file("log.txt");streambuf* org_cout = cout.rdbuf();cout.rdbuf(log_file.rdbuf());cout << "Happy Spring!" << endl;cout.rdbuf(org_cout);

此选项通过cout.rdbuf()函数将cout的缓冲区替换为log_file的缓冲区，从而实现将cout的输出重定向到文件log.txt。输出完成后，再将cout的缓冲区恢复为原来的缓冲区。所以该选项可以实现将字符串输出到文件。

综上，答案选C。

二、判断题（每题2分，共20分）

第1题 函数是C++中的核心概念，用于封装可重用的代码块。

【答案】 正确

【考纲知识点】 函数的基本概念

【解析】

在C++中，函数是一种重要的编程结构，它将一段具有特定功能的代码封装起来，形成一个独立的单元。通过给函数定义一个名称，在程序的其他地方可以方便地调用这个函数，实现代码的复用。这样不仅提高了代码的可读性和可维护性，还使得程序的结构更加清晰，便于开发人员对复杂程序进行模块化设计和管理。所以“函数是C++中的核心概念，用于封装可重用的代码块”这一描述是准确的。

第2题 在C++中，函数的返回类型可以省略，默认为int。

【答案】 错误

【考纲知识点】 函数定义的基本语法

【解析】

在C++中，函数的返回类型不能省略。如果函数没有返回值，需要使用void关键字明确指定其返回类型为void。如果不指定返回类型，编译器会报错，而不是默认为int。

第3题 结构体的成员默认是public访问权限。

【答案】 正确

【考纲知识点】 结构体的访问权限

【解析】

在C++中，结构体和类相似，都可以包含成员变量和成员函数。不同的是，结构体的成员默认访问权限是public，即结构体的成员可以在结构体外部直接访问，除非显式地使用private或protected关键字来修改成员的访问权限。而类的成员默认访问权限是private。

第4题 假设整数数组arr[4]= {0, 1, 2, 3};的第一个元素在内存中的地址为0x7ffee4065820,经过int* p = arr; p += 1;后，指针p的值是1。

【答案】 错误

【考纲知识点】 指针的运算

【解析】

在C++中，当对指针进行算术运算时，其移动的字节数取决于指针所指向的数据类型。在本题中，arr是一个int类型的数组，int* p = arr将指针p指向数组arr的首元素。当执行p += 1时，指针p会按照int类型的大小向后移动一个元素的位置。在大多数系统中，int类型通常占4个字节，所以p的值会增加4，而不是1。此时p的值应该是0x7ffee4065820 + 4 = 0x7ffee4065824，它指向数组arr的第二个元素1的地址，而不是值为1。

第5题 二维数组作为函数参数时，必须显式指定所有维度的大小。

【答案】 错误

【考纲知识点】 二维数组作为函数参数的传递规则

【解析】

在C++里，二维数组作为函数参数时，不需要显式指定所有维度的大小，但必须指定除第一维之外其他维度的大小。这是因为在函数调用时，编译器需要知道每一行的元素个数，以便正确地进行内存寻址和数据访问。

例如，下面是一个正确的示例：

#include<iostream>//函数定义，指定第二维大小voidprintArray(intarr[][3],introws){    for(inti =0;i <rows;++i){        for(intj =0;j <3;++j){            std::cout<<arr[i][j]<<" ";        }        std::cout<<std::endl;    }}intmain(){    intarr[2][3]={{1,2,3},{4,5,6}};    printArray(arr,2);    return0;}

在这个例子中，函数printArray的参数arr只指定了第二维的大小为3，第一维大小由调用函数时传入的rows参数来确定。所以，“二维数组作为函数参数时，必须显式指定所有维度的大小”这种说法是错误的。

第6题 递推是一种通过已知的初始值和递推公式，逐步求解目标值的算法。

【答案】 正确

【考纲知识点】 递推算法的基本概念

【解析】

递推算法的核心就是利用已知的初始条件，借助递推关系（也就是递推公式），逐步计算出后续的值，最终得到目标值。例如，在斐波那契数列中，初始值为F(0)=0，F(1)=1，递推公式为F(n)=F(n-1)+F(n-2)(n≥2)。通过这个初始值和递推公式，就可以从n=2开始，逐步计算出后续的斐波那契数。所以，“递推是一种通过已知的初始值和递推公式，逐步求解目标值的算法”这一描述是准确的。

第7题 考虑最坏情况下冒泡排序算法的时间复杂度，T(n)为待排序数字的数目为n的复杂度，则其递推关系式为T(n)=T(n-1)+n，T(0)=1。

【答案】 错误

【考纲知识点】 冒泡排序算法的时间复杂度分析以及递推关系式的建立

【解析】

冒泡排序最坏情况分析

在最坏情况下，冒泡排序需要对一个长度为n的数组进行n-1轮比较和交换操作。每一轮中，需要比较的次数逐渐减少。对于长度为n的数组，第一轮需要比较n-1次，第二轮需要比较n-2次，以此类推，最后一轮需要比较1次。

递推关系式分析

如果要建立递推关系式，对于长度为n的数组进行冒泡排序，可看作先对长度为 n-1的数组进行冒泡排序（其复杂度为T(n-1)），然后再进行n-1次比较和可能的交换操作。所以递推关系式应该是T(n)=T(n-1)+(n-1)，而不是T(n)=T(n-1)+n。

初始条件分析

当n=0时，数组为空，不需要进行任何排序操作，所以T(0)=0，而不是T(0)=1。

综上所述，题目中的说法是错误的。

第8题 插入排序在最好情况（已有序）下的时间复杂度是O(n²)。

【答案】 错误

【考纲知识点】 插入排序算法复杂度分析

【解析】

插入排序的基本思想是将未排序数据插入到已排序序列的合适位置。

在最好情况下，即待排序数组已经是有序的。对于插入排序，每插入一个新元素时，只需要和已排序部分的最后一个元素比较一次，因为数组已经有序，新元素总是大于等于已排序部分的最后一个元素，所以不需要进行元素的移动操作。

对于一个包含n个元素的数组，插入排序在最好情况下需要进行n-1次比较操作，其时间复杂度为O(n)，而不是O(n²)。所以该说法错误。

第9题 对数组arr[]={4, 3, 1, 5, 2}进行升序排序，执行第一轮选择排序后数组arr中的内容是{1, 4, 3, 5, 2}。

【答案】 错误

【考纲知识点】 选择排序算法的执行过程

【解析】

选择排序的基本思想是每一轮从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到全部待排序的数据元素排完。

对于数组arr[] = {4, 3, 1, 5, 2}进行升序排序的第一轮操作如下：从数组的第一个元素开始，遍历整个数组，找出最小的元素。在这个数组中，最小的元素是1，它位于数组的第3个位置（索引为2）。然后将这个最小元素1与数组的第一个元素4进行交换。交换后，数组就变为{1, 3, 4, 5, 2}。

所以，执行第一轮选择排序后数组arr中的内容是{1, 3, 4, 5, 2}，而不是{1, 4, 3, 5, 2}。题目说法错误。

第10题 未捕获异常会调用std::terminate终止程序。

【答案】 正确

【考纲知识点】C++异常处理机制中未捕获异常的处理

【解析】

在C++里，当程序抛出一个异常时，会尝试寻找与之匹配的catch块来处理这个异常。若在整个调用栈中都没有找到合适的catch块，也就是该异常未被捕获，那么程序会调用std::terminate函数。std::terminate函数的默认行为是终止程序的执行，并且通常会输出一些错误信息或者调用预先设置的终止处理函数（如果有的话）。所以，“未捕获异常会调用std::terminate终止程序” 这一表述是正确的。 

三、编程题（每题25分，共50分）

编程题1

• 试题名称：荒地开垦

• 时间限制：1.0 s

• 内存限制：512.0 MB

题面描述

小杨有一大片荒地，可以表示为一个n行m列的网格图。

小杨想要开垦这块荒地，但荒地中一些位置存在杂物，对于一块不存在杂物的荒地，该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。

小杨可以选择至多一个位置，清除该位置的杂物，移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下，最多能够开垦多少块荒地。

输入格式

第一行包含两个正整数n,m，含义如题面所示。

之后n行，每行包含一个长度为m且仅包含字符.和#的字符串。如果为.，代表该位置为荒地，如果为#，代表该位置为杂物。

输出格式

输出一个整数，代表在清除至多一个位置的杂物的情况下，最多能够开垦的荒地块数。

样例

输入样例1

3 5......#..#.....

输出样例1

11

样例解释

移除第二行从左数第二块空地的杂物后：

.........#.....

第一行从左数前4块荒地，第二行从左数前3块荒地，第三行从左数前4块荒地，均可开垦，4+3+4=11。

数据范围

对于全部数据，保证有1 ≤n,m ≤1000。

代码解释

这段代码是为了解决“荒地开垦”问题，其核心思路是先统计原本就可以开垦的荒地数量，接着考虑移除至多一个杂物后能新增的可开垦荒地数量，最后把两者相加得出最多可开垦的荒地数量。

代码结构及功能

1.全局变量与常量定义：

const int N = 1005;：定义一个常量N，作为数组的最大容量。

char mat[N][N];：用于存储荒地网格图，'.'代表荒地，'#'代表杂物。

int a[N][N];：用来记录移除每个杂物位置后能新增的可开垦荒地数量。

const int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};：表示上下左右四个方向的偏移量，方便检查相邻格子。

2.主函数main：

输入读取：

nt n, m, ans = 0;

scanf("%d%d", &n, &m);assert(1 <= n && n <= 1000);assert(1 <= m && m <= 1000);for (int i = 1; i <= n; i ++)    scanf("%s", mat[i] + 1);

读取荒地网格图的行数n和列数m，并使用assert确保输入在有效范围内。然后逐行读取网格图。

遍历网格图：

for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++) {  int num = 0, p = -1;for (int k = 0; k < 4; k ++)if (mat[i+ d[k][0]][j+ d[k][1]] == '#')  num ++, p = k;if (mat[i][j] == '.' && num == 1)           a[i+ d[p][0]][j+ d[p][1]] ++;elseif (mat[i][j] == '.' && num == 0)     ans ++;elseif (mat[i][j] == '#' && num == 0)     a[i][j] ++;}

针对每个格子，统计其相邻的杂物数量num。若当前格子是荒地且相邻杂物数量为1，就将移除该杂物位置后能新增的可开垦荒地数量加1；若当前格子是荒地且相邻无杂物，将原本可开垦的荒地数量ans加1；若当前格子是杂物且相邻无杂物，也将移除该位置杂物后能新增的可开垦荒地数量加1。

找出最大新增可开垦荒地数量：

int mx = 0;for (int i = 1; i <= n; i ++)for (int j = 0; j <= m; j ++)  mx = max(mx, a[i][j]);

遍历数组a，找出移除某个杂物位置后能新增的最大可开垦荒地数量mx。

输出结果：

cout << ans + mx << endl;

原本可开垦的荒地数量ans和最大新增可开垦荒地数量mx相加把，输出最多可开垦的荒地数量。

复杂度分析

时间复杂度：代码中有三层嵌套循环，整体时间复杂度为O(n×m)，其中 n是行数，m是列数。

空间复杂度：使用了两个二维数组mat和a，空间复杂度为O(n×m)。

参考程序

编程题2

时间限制：1.0 s

内存限制：512.0 MB

二阶矩阵

题目描述

小A有一个n行m列的矩阵A。

小A认为一个2×2的矩阵D是好的，当且仅当D_1,1×D_2,2=D_1,2×D_2,1。其中D_i,j表示矩阵D的第i行第j列的元素。

小A想知道A中有多少个好的子矩阵。

输入格式

第一行，两个正整数n,m。

接下来n行，每行m个整数A_i,1，A_i,2，A_i,m。

输出格式

一行，一个整数，表示A中好的子矩阵的数量。

样例

输入样例1

3 41 2 1 02 4 2 10 3 3 0

输出样例1

2

样例解释

样例中的好的子矩阵如下：

数据范围

对于所有测试点，保证1 ≤ n ≤ 500, 1 ≤ m ≤ 500, -100 ≤ A_i,j≤ 100。

代码解释

这段代码的主要目的是计算一个n行m列矩阵A中好的2×2子矩阵的数量。根据题目定义，一个2×2的矩阵D是好的，当且仅当D_1,1×D_2,2=D_1,2×D_2,1。

代码结构及功能

1.全局变量与常量定义：

const int N = 505;：定义一个常量N，作为数组的最大容量，考虑到数据范围1 ≤ n ≤ 500, 1 ≤ m ≤ 500，这里设置为505以避免越界。

int n, m;：分别表示矩阵的行数和列数。

int a[N][N];：二维数组，用于存储输入的矩阵A。

int ans;：用于记录好的2×2子矩阵的数量。

2.主函数main：

输入读取：

scanf("%d%d", &n, &m);assert(1 <= n && n <= 500 && 1 <= m && m <= 500);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {  scanf("%d", &a[i][j]);  assert(-100 <= a[i][j] && a[i][j] <= 100); }

首先读取矩阵的行数n和列数m，并使用assert确保输入在有效范围内。然后逐行逐列读取矩阵A的元素，同样使用assert保证元素的值在[-100,100]之间。

遍历矩阵查找好的子矩阵：

for (int i = 1; i < n; i++)

   for (int j = 1; j < m; j++)if (a[i][j] * a[i+1][j+1] == a[i+1][j] * a[i][j+ 1])  ans++;

通过两层嵌套循环遍历矩阵 A，对于每个可能的2×2子矩阵的左上角元素(i,j)(1≤i<n且1≤j<m)，检查该子矩阵是否满足好矩阵的条件，即左上角元素与右下角元素的乘积等于右上角元素与左下角元素的乘积。如果满足条件，则将计数器ans加1。

输出结果：

printf("%d\n", ans);

最后输出好的2×2子矩阵的数量。

复杂度分析

时间复杂度：代码中有两层嵌套循环，对于每个可能的2×2子矩阵都进行了一次检查，因此时间复杂度为O(n×m)，其中n是矩阵的行数，m是矩阵的列数。

空间复杂度：使用了一个二维数组 a来存储矩阵，因此空间复杂度为 O(n×m)。

参考程序

策划：GESP技术委员会副主席 刘晓庆

技术支持：GESP技术委员会委员 陈珊