蓝桥杯第 2 场算法双周赛 第2题 铺地板【算法赛】c++ 数学思维
题目
铺地板
https://www.lanqiao.cn/problems/5887/learning/?contest_id=145
问题描述
小蓝家要装修了，小蓝爸爸买来了很多块（你可以理解为数量无限）2×32×3 规格的地砖，小蓝家的地板是 n×m 规格的，小蓝想问你，能否用这些 2×32×3 的地砖铺满地板。
铺满地板：对于地板的每个区域，都有且只有一块地砖覆盖，地砖可以旋转，但不能切割。
例如：对于 7×67×6 的地板，一种铺地板方式是：
当然，也存在其他别的铺法。
小蓝家是个多层小别墅，每一层的规格不一样，所以他会多次询问你不同规格的地板。
注意：请仔细读题，不要弄混地板和地砖。
输入格式
第一行输入一个整数 T，代表询问数量。
接下来 T 行，每行两个正整数 ni,mi，代表小蓝询问的地板规格。
输出格式
对于每次询问，如果 2×32×3 的地砖可以铺满地板，输出 Yes，否则输出 No。
样例输入
4
7 6
2 2
12 8
1 12
样例输出
Yes
No
Yes
No
说明
- 对于第一组询问，题干中存在正确铺法。
- 对于第二组询问，不存在任何铺法可以铺满。
作为一个程序员，应该有 666666 分的勇气。如果你觉得这是一个简单得很 66 的结论，但是你不知道如何证明，不妨提交一发试一试。
祝大家 1024 快乐。
评测数据范围
1≤T≤104,1≤n,m≤104。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Java | 2s | 128M |
| Python3 | 3s | 128M |
| PyPy3 | 3s | 128M |
思路和解题方法
#include <iostream>和using namespace std;：这两行代码包含了所需的头文件和命名空间。#include <iostream>用于输入输出操作，using namespace std;允许直接使用标准库中的函数和对象，而无需使用std::前缀。
string canCoverFloor(int n, int m)：这部分代码定义了一个函数canCoverFloor，它接受两个整型参数n和m，分别表示地板的行数和列数。
int area = n * m;：在函数内部，首先计算地板的面积，即行数乘以列数，并将结果存储在变量area中。
int tile_area = 6;：然后定义了一个变量tile_area，表示地砖的面积，这里假设地砖的大小为2x3，因此地砖的面积为6。
if (area % tile_area == 0 && n >= 2 && m >= 2)：接下来，使用条件语句判断地板是否可以被地砖完全覆盖。条件包括两部分：首先，地板面积必须能够整除地砖面积，即area % tile_area == 0；其次，行数和列数都必须大于等于2，即n >= 2 && m >= 2。
return "Yes";和return "No";：如果满足条件，则返回字符串"Yes"；否则返回字符串"No"。
int main()：这部分代码定义了主函数main，是程序的入口点。
int T;：首先声明一个整型变量T，用于存储询问数量。
cin >> T;：然后使用输入流cin读取用户输入的询问数量，并将其存储在变量T中。
for (int i = 0; i < T; i++)：使用for循环来处理每个询问。循环条件是i < T，即循环执行T次。
int n, m;：在每次循环中，声明两个整型变量n和m，用于存储地板的行数和列数。
cin >> n >> m;：使用输入流cin读取地板的行数和列数，并将它们存储在相应的变量中。
string result = canCoverFloor(n, m);：调用函数canCoverFloor(n, m)判断地板是否可以被地砖完全覆盖，并将结果存储在字符串变量result中。
cout << result << endl;：使用输出流cout将结果输出到控制台，并在末尾添加换行符endl。
return 0;：循环结束后，返回0表示程序正常结束。
复杂度
时间复杂度:
O(T)
时间复杂度主要取决于循环的执行次数T，即O(T)。
空间复杂度：
O(1)
整个程序的空间复杂度为O(1)，即常数级别的空间开销。
c++ 代码
#include <iostream>
using namespace std;
string canCoverFloor(int n, int m) {
int area = n * m; // 计算地板面积
int tile_area = 6; // 地砖面积为2x3=6
if (area % tile_area == 0 && n >= 2 && m >= 2) { // 如果地板可以被地砖完全覆盖且行列数都大于等于2
return "Yes";
} else {
return "No";
}
}
int main() {
int T;
cin >> T; // 询问数量
for (int i = 0; i < T; i++) {
int n, m;
cin >> n >> m;
string result = canCoverFloor(n, m); // 调用函数判断地板是否可以被地砖完全覆盖
cout << result << endl; // 输出结果
}
return 0;
}
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。