蓝桥杯真题——1.裁纸刀+2.移动
目录
一、题目一题目链接：0裁纸刀 - 蓝桥云课
注：下述题目描述和示例均来自蓝桥云客
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝有一个裁纸刀，每次可以将一张纸沿一条直线裁成两半。
小蓝用一张纸打印出两行三列共 6 个二维码，至少使用九次裁出来，下图给出了一种裁法。
在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁 4 次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。
如果小蓝要用一张纸打印出 20 行 22 列共 440 个二维码，他至少需要裁多少次？
解法一：用脑子解题
题目要求在一张纸上裁出特定数量的二维码区域，且每次裁纸只允许沿一条直线将纸张分成两半。题目给出的是一个 20 行 22 列的纸张矩阵，共包含 440 个二维码区域，要求最少裁刀次数以分割成每个二维码独立的区域。
解题思路
-
行与列的裁剪：
- 我们的目标是将一张纸划分成 20 行和 22 列的单独小块，这就意味着行方向和列方向都需要进行裁剪。
- 行裁剪：要得到 20 行，就需要在纸上裁出 19 条横向的分隔线。
- 列裁剪：要得到 22 列，就需要裁出 21 条纵向的分隔线，但是每次列方向上不能一刀到底，是每一行只能一刀，所以一列上需要行数刀。
-
计算裁剪次数：
- 行裁剪次数：19 次（每次在行间裁出一条分隔线）。
- 列裁剪次数：20 × 21次（每次在每一行列间裁出一条分隔线）。
- 边缘剪次数：根据题意需要 4 次。
- 总的剪次数：19 + 20 × 21 + 4 = 443 将行裁剪和列裁剪次数相加，得到总的裁剪次数。
-
总结裁剪总数：
- 因为每次裁剪都是在纸张上划出一条分隔线，最终的裁剪次数即为满足条件的最小次数。
Java写法：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
// 我们可以看到的是，这里有这一张纸，首先四边都需要裁切那么就是4
// 横着可以一刀到底，那么就需要行数-1次
// 竖着是列之间都需要那么就是行数×（列数 - 1）
System.out.print(4 + (20 - 1) + 20*(22 - 1));
}
}C++写法：
#include <iostream>
using namespace std;
int main()
{
cout << 4 + 20 * 21 + 19;
return 0;
}
AC情况
时间复杂度和空间复杂度
这，emmmmmm，都是O(1)!!!!!!!!!!!!!!!!
二、题目二题目链接：2.移动 - 蓝桥云课
题目描述
小蓝有一个机器人，初始时在坐标 (0,0)。
小蓝可以给机器人发送指令，指令如下：
1. 指令 UU，如果当前机器人在 (x,y)，执行后机器人在 (x−1,y)；
2. 指令 DD，如果当前机器人在 (x,y)，执行后机器人在 (x+1,y)；
3. 指令 LL，如果当前机器人在 (x,y)，执行后机器人在 (x,y−1)；
4. 指令 RR，如果当前机器人在 (x,y)，执行后机器人在 (x,y+1)。
给定指令序列，请问指令全部执行后，机器人在哪个位置？
输入格式
输入一行包含一个字符串，表示指令序列，字符串中只包含 U,D,L,RU,D,L,R 四种字符。
输出格式
输出一行包含两个整数，相邻的整数之间使用一个空格分隔，分别表示机器人的两个坐标值。
样例输入
DDDRRLR
样例输出
3 2
评测用例规模与约定
对于所有评测用例，输入的长度不超过 1000 个字符。
解法一：用脑子解题
题目要求通过一系列指令移动机器人的位置，并输出最终的坐标。每个指令对应一个特定的方向：
- U：向上移动，即
x - 1 - D：向下移动，即
x + 1 - L：向左移动，即
y - 1 - R：向右移动，即
y + 1
机器人从初始位置 (0, 0) 出发，通过这些指令不断更新位置，最终输出执行完所有指令后的坐标。
解题思路
- 读取输入指令：读取一个字符串，其中每个字符为一个指令。
- 初始化坐标：设定初始坐标
(x, y)为(0, 0)。 - 遍历指令：逐个遍历指令字符，根据指令更新
x或y的值。- U：使
x减 1。 - D：使
x加 1。 - L：使
y减 1。 - R：使
y加 1。
- U：使
- 输出结果：遍历完所有指令后，输出最终的
(x, y)坐标。
Java写法：
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 指令U：x-1
// 指令D：x+1
// 指令L：y-1
// 指令R：y+1
String str = sc.next();
// 设置坐标
int x = 0;
int y = 0;
for(char order: str.toCharArray()){
if(order == 'U'){
x--;
}else if(order == 'D'){
x++;
}else if(order == 'L'){
y--;
}else{
y++;
}
}
System.out.println(x +" " +y);
sc.close();
}
}C++写法：
std::string用于存储指令字符串。std::cin和std::cout用于输入和输出，操作简单高效。
#include <iostream>
#include <string>
int main() {
std::string str;
std::cin >> str;
// 设置初始坐标
int x = 0;
int y = 0;
// 遍历每个指令字符
for (char order : str) {
if (order == 'U') {
x--; // 向上移动
} else if (order == 'D') {
x++; // 向下移动
} else if (order == 'L') {
y--; // 向左移动
} else if (order == 'R') {
y++; // 向右移动
}
}
// 输出最终的坐标
std::cout << x << " " << y << std::endl;
return 0;
}
运行时间
时间复杂度和空间复杂度
时间复杂度
- 遍历指令字符串：代码中的
for循环逐个访问字符串中的字符。设指令字符串的长度为 n，则该循环的时间复杂度为 O(n)。
因此，总的时间复杂度为 O(n)。
空间复杂度
- 变量存储：只使用了几个简单的变量
x、y和str，其中str占用 O(n)的空间（用于存储输入的字符串）。
因此，空间复杂度为 O(n)（输入存储需求）
总结
题目一：裁纸刀
题目概述：给定一个大纸张矩阵，需要使用最少的裁剪次数，将其分割为特定数量的小块。每次裁剪只能沿一条直线切开一张纸。
解题思路：为了分割成特定行列数的区域，需要进行边缘裁剪、行裁剪和列裁剪。最终得出最小裁剪次数为 4 + (行数 - 1) + 行数 * (列数 - 1)。
代码实现：文章提供了Java和C++代码，分别计算了边缘裁剪、行裁剪和列裁剪的次数，再将它们相加得到最终答案。
时间与空间复杂度：时间复杂度和空间复杂度均为 O(1) ，因为操作只涉及简单的加法和乘法计算。
题目二：机器人移动
题目概述：给定一系列指令，使得机器人在坐标平面上移动，最终输出机器人的位置。
解题思路：定义初始位置为 (0,0)，每条指令对应一个方向：U向上、D向下、L向左、R向右。依次遍历指令字符串，根据每条指令更新机器人坐标。
代码实现：提供的Java和C++代码依次遍历字符串，通过简单的条件判断更新坐标位置，最终输出机器人的位置。
时间与空间复杂度：时间复杂度为 O(n)，其中 n 是指令字符串的长度；空间复杂度为 O(n)，用于存储输入的字符串。
原文地址：https://blog.csdn.net/DDDDWJDDDD/article/details/143693403
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！