蓝桥杯备赛笔记(一)

这里的笔记是关于蓝桥杯关键知识点的记录,有别于基础语法,很多内容只要求会用就行,无需深入掌握。

文章目录

  • 前言
  • 一、编程基础
    • 1.1 C++基础格式和版本选择
    • 1.2 输入输出
        • cin和cout:
    • 1.3 string
        • 以下是字符串的一些简介:
        • 字符串的基本操作:
  • 二、竞赛常用库函数
    • 2.1 排序
        • sort函数:
        • 使用传入第三个参数自定义比较函数:
        • 使用lambda自定义比较函数:
    • 2.2 最值查找
        • min和max函数:
        • min_element和max_element:
        • nth_element函数:
    • 2.3 二分查找
        • 整数二分查找模板
        • 浮点二分查找模板
        • 二分答案模板
        • 跳石头题目
  • 总结


前言

持续更新,千里之行始于足下


一、编程基础

1.1 C++基础格式和版本选择

这里只需要记住使用一个万能头文件即可:

#include <bits/stdc++.h> //什么都能用这个头文件
using namespace std;

基本数据类型:

int x = 3; //整数x
double d = 3.14; //浮点数(小数)
char ch = 'A'; //字符常量'A'
char s[] = "Hello"; //字符串
bool b = true; //布尔值,即真假值b。非0为真,0为假

1.2 输入输出

cin和cout:
#include <bits/stdc++.h> //万能头文件
using namespace std; //全局引用std,std里面包含了cin,cout和endl等等东西
int main(){double a,b;cin >> a >> b;//cin会自动判断变量类型cout << fixed << setprecision(3) <<a << '' << b << '\n';//fixed << setprecision(3)的意思是保留浮点数后面3位return 0;//记住最后return 0
}

fixed << setprecision(3) 意思是保留浮点数后3位

在字符或字符串中直接使用cin:

#include <bits/stdc++.h>
using namespace std;
int main(){char ch;cin >> ch;cout << ch;return 0;
}

以上代码中: 输入:a b 输出:a

#include <bits/stdc++.h>
using namespace std;
int main(){char s[10];cin >> s;cout << s;return 0;
}

以上代码中: 输入:hi nihao 输出:hi
注意!!cin无论是在字符或字符串中输入空格或者换行符就会结束

#include <bits/stdc++.h>
using namespace std;
int main(){string s;getline(cin, s);cout << s;return 0;
}

以上代码中: 输入:hi nihao 输出:hi nihao
所以我们可以结合使用string和getline来消除掉这个cin的缺点

取消同步流:
由于cin和cout自动判断变量的关系,它们的读写效率要比scanf和printf更低。
当数据量大的时候,可能导致程序运行超时,我们可以通过取消同步流来加速cin和cout,加速后效率就差不多了。

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); //取消同步流

1.3 string

使用string需要在头文件包含该库 #include<string>

以下是字符串的一些简介:
  1. 字符串管理:string封装了字符串的存储和管理。它自动处理字符串的内存分配和释放,避免了手动管理内存的麻烦。
  2. 动态大小调整:string可以根据需要自动调整字符串的大小,在添加或删除字符时,string会自动调整内部的存储容量,确保足够的空间来容纳字符串。
  3. 安全性:它提供了越界访问检查,以避免访问超出字符串范围的字符。
  4. 迭代器支持:string支持迭代器,可以使用迭代器遍历字符串中的字符,进行字符级别的操作。
  5. 兼容性:string是C++标准库的一部分,因此广泛使用。

string的声明和初始化:

#include <bits/stdc++.h>
#include <string>
int main(){//声明并初始化一个字符串std::string str1;//使用字符串字面量初始化字符串std::string str2 = "hello, world!";//使用另一个std::string 对象来初始化字符串std::string str3 = str2;//使用部分字符串初始化字符串std::string str4 = str2.substr(0, 5);//substr(起始位置,长度)//使用字符数组初始化字符串const char* charArray = "Hello";std::string str5(charArray);//使用重复的字符初始化字符串std::string str6(5, 'A');//"AAAAA"重复5次A
}

在C++中,std::string类提供了一个成员函数c_str(),用于返回一个指向以空字符结尾的C风格字符串(即const char*类型)

字符串的基本操作:

1、获取字符串长度:

std::string str = "Hello, world!";
int length = str.length(); //或者 int length = str.size();
std::cout << "Length: " << length << std::endl;

2、拼接字符串(+或append):

std::string str1 = "Hello";
std::string str2 = "world";
std::string result1 = str1 + "," + str2;//使用+运算符
std::string result2 = str1.append(",").append(str2);//使用append函数
std::cout << "Result1 = " << result1 << std::endl;
std::cout << "Result2 = " << result2 << std::endl;

3、字符串查找(find):

std::string str = "Hello, world";
size_t pos = str.find("world"); //查找子字符串位置
if(pos != std::string::npos){ //判断是否不等于-1std::cout << "Substring found at position: " << pos << std::endl;
}
else{std::cout << "Substring not found." << std::endl;
}

4、字符串替换(replace):

std::string str = "Hello, world";
str.replace(7,5, "Universe"); //替换子字符串
//7是子串起始位置,5是要替换掉的长度
std::cout << "Result: " << str << std::endl;

5、提取子字符串(substr):

std::string str = "Hello, world";
std::string subStr = str.substr(7,5); //提取子字符串
std::cout << "Substring: " << subStr << std::endl;

6、字符串比较(compare):

std::string str1 = "Hello";
std::string str2 = "World";
int result = str1.compare(str2);//比较字符串
if(result == 0){std::cout << "String are equal." << std::endl;
} else if(result < 0){std::cout << "String 1 is less than String 2." << std::endl;
} else{std::cout << "String 1 is greater than String 2." << std::endl;
}

string重载了不等号,所以也可以直接使用s1 < s2的方式来比较string的大小,比较的规则是按照字典序大小进行比较。

字典序的比较方法是从小到大一个一个比较,一旦遇到不相等的字符就确定大小关系。

例如:
aaaa < bbbb
azz < baaa

常用的遍历string方法一共有两种:

  1. 循环枚举下标
  2. auto枚举(其中&表示取引用类型,如果对i修改将会改变原来的值)
string s = "Hello";for(int i = 0; i < s.length(); ++i) cout << s[i];//枚举循环遍历一遍string的对象s
cout << '\n';
for(auto i : s)
{cout << i;i = 'a';//此处的修改无效,因为这个i是拷贝出来的,而不是引用s的//所以这里只是赋值到拷贝出来的i里面,而这个i是在局部变量内,这个for循环结束就消亡了
}
cout << '\n';
//此时s = "Hello"
for(auto &i : s)
{cout << i;//此时再遍历输出s字符串还是Helloi = 'a';//此处修改会改变s的字符值
}
cout << '\n';
//此时s= "aaaaa"
cout << s << '\n';

二、竞赛常用库函数

2.1 排序

sort函数:

sort函数包含在头文件<algorithm>中
在使用前需要使用#include <algorithm>或万能头文件#include <bits/stdc++.h>
sort是C++标准库中的一个函数模板,用于对指定范围内的元素进行排序。
sort算法使用的是快速排序或者类似快速排序的改进算法,具有较好的平均时间复杂度,一般为O(nlogn)。
sort的用法:
sort(起始地址, 结束地址的下一位, *比较函数);
比较函数一般默认用的小于号(<)

#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int a[1000];
int n;
//读取数组大小
cin >> n;
//读取元素
for(int i = 1; i <= n; ++i) cin >> a[i];//对数组进行排序
sort(a+1, a+n+1); //[1, n+1) 左闭右开
//   a[1], a[n+1]//输出
for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
return 0;
}

sort(起始地址, 结束地址的下一位, *比较函数);

#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//初始化v
//这里是模板类vector,需要使用万能头文件或#include <vector>
vector<int> v = {5, 1, 3, 9, 11};//对数组进行排序
sort(v.begin(), v.end());//输出
for(int i = 0; i < v.size(); ++i) cout << v[i] << ' ';
//for (auto i : v)cout << i << ' ';//使用auto进行排序也可以
return 0;
}

由于sort默认用小于号进行排序,如果想要自定义比较规则,可以传入第三个参数,这个参数可以是函数或者lambda表达式。

使用传入第三个参数自定义比较函数:
#include <bits/stdc++.h>
using namespace std;
bool cmp(const int &u, const int &v)
{return u > v;
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//初始化vvector<int> v = {5, 1, 3, 9, 11};//对数组进行排序,降序排序sort(v.begin(), v.end(), cmp);//						传入函数名//输出for(int i = 0; i<v.size(); ++i) cout << v[i] << ' ';return 0;
}
使用lambda自定义比较函数:
#include <bits/stdc++.h>
using namespace std;
int main(){//初始化vvector<int> v = {5, 1, 3, 9, 11};//对数组进行排序,降序排序,这里使用lambda表达式sort(v.begin(), v.end(), [](const int &u, const int &v){return u > v;});for(int i = 0; i<v.size(); ++i) cout << v[i] << ' ';return 0;
}

在[ ]里面不写东西代表把数组内的东西以拷贝的形式放进去,如果在[ ]内加上&后( [&] )就会变成把v里面的变量都以引用(&)类型的格式放进去。

下面是一个本人觉得很妙的操作:

for(int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];

首先,这里我们需要意识到字符串其实就是一个字符数组。在这段代码行中的" \n"[i == n]巧妙的利用了判断符号来确认for循环是否到结尾了,如果到结尾了此时判断会返回1(真),就会自动输出\n换行。如果没到结尾,即i不等于n,此时返回的是0(假),则输出空格。
在这个字符串中下标为0对应的是" “(空格),下标为1对应的是”\n"(回车换行符)

以下是使用了这个操作的题目:
在这里插入图片描述

2.2 最值查找

min和max函数:

min(3, 5) = 3
min({1, 2, 3, 4}) = 1
max(a, b)返回a和b中较大的那个值,只能传入两个值,或传入一个列表。
例如:
max(7, 5) = 7
max({1, 2, 3, 4}) = 4
时间复杂度为O(1),传入参数为数组时时间复杂度为O(n),n为数组大小。
min和max函数是在最值操作时最常用的操作。

min_element和max_element:

min_element(st, ed)返回地址[st, ed)中最小的那个值的下标(迭代器),传入参数为两个地址或迭代器。
max_element(st, ed)返回地址[st, ed)中最大的那个值的下标(迭代器),传入参数为两个地址或迭代器。

时间复杂度均为O(n),n为数组大小(由传入的参数决定)

//初始化v
vector<int> v = {5, 1, 3, 9, 11};//输出最大的元素,*表示解引用,即通过地址(迭代器)得到值
cout << *max_element(v.begin(), v.end()) << '\n';
nth_element函数:

nth_element(st, k, ed)
进行部分排序,返回值为void()
传入参数为三个地址或迭代器。其中第二个参数位置的元素将处于正确位置,其他位置元素的位置可能是任意的,但前面的都比它小,后面的后比它大。时间复杂度O(n)。

//初始化v
vector<int> v = {5, 1, 7, 3, 10, 18, 9};//输出最大的元素,*表示解引用,即通过地址(迭代器)得到值
nth_element(v.begin(), v.begin() + 3, v.end());
//这里v[3]的位置将会位于排序后的位置,其他的任意
for(auto &i : v) cout << i << ' ';

课后题目:
在这里插入图片描述

2.3 二分查找

二分法是一种高效的查找方法,它通过将问题的搜索范围一分为二(两边有明显的区别),迭代地缩小搜索范围,直到找到目标或确定目标不存在。
二分法适用于有序数据集合,并且每次迭代可以将搜索范围缩小一半。
二分法本质也是枚举,但和暴力枚举不同,二分法利用数据结构的单调性减少了很多不必要的枚举,从而极大的提高了效率,一般可以将O(n)的枚举优化到O(logn)。
常见的二分类型有:

  1. 整数二分
  2. 浮点二分
  3. 二分答案(最常见)
整数二分查找模板
//找到升序数组a中的x第一次出现的位置
int l = 0, r = 1e9;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while(l + 1 != r)//l,r相邻的话退出
{int mid = (l + r) / 2;//如果a为升序,说明mid偏大了,需要减小mid,就只能将r变小,即r = midif(a[mid] >= x) r = mid;else l = mid;//否则l = mid,始终保持在所属区域
}
cout << r << '\n';
浮点二分查找模板
//计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e-6;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while(r - l >= eps)//eps是一个极小量,设置为1e-6比较适合
{double mid = (l + r) / 2;//f(x)单调递增,f(mid) >= 0,说明mid偏大了,需要减小mid,就只能将r变小,即r = midif(f(mid) >= 0) r = mid;else l = mid;
}
//最后返回l,r差别不大
cout << r << '\n';
二分答案模板
bool check(int mid)
{bool res = true;//其他内容return res;
}
int main()
{int l = 0, r = 1e9;while(l + 1 != r){int mid = (l + r) / 2;//具体写法需要根据题意修改if(check[mid] >= x) l = mid;else r = mid;
}
cout << l << '\n';//具体输出的内容需要根据题意判断
跳石头题目

在这里插入图片描述
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 9;
int a[N];
int L,n,m;
int check(int mid){int res = 0,lst = 0;for(int i = 1; i <= n; ++i){//将i移除if(a[i] - a[lst] < mid) res++;else lst = i;}//将lst移除if(L - a[lst] < mid) res++;return res;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  cin >> L >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];int l = 0,r = 1e9 + 5;while(l + 1 != r){int mid = (l + r) >> 1;// >> 1等价于/2。使用这个的原因是因为位运算比除法运算更快,且可以避免溢出if(check(mid) <= m) l = mid;else r = mid;}cout << l << '\n';return 0;
}

解题思路:

这里我们要先假设最短跳跃距离的最大值是从0~L


总结

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/480955.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【HarmonyOS NEXT】ACL 受限权限申请

关键词&#xff1a;受限开放权限、ACL、鸿蒙 在鸿蒙应用开发过程中&#xff0c;部分权限被受到限制&#xff08;如悬浮窗开发、读取联系人数据、读取公共目录音频文件等权限&#xff09;&#xff0c;但是在我们的应用开发过程中又不得不使用该权限时可向华为申请受限权限&#…

《安富莱嵌入式周报》第346期:开源2GHz带宽,12bit分辨率,3.2Gsps采样率示波,开源固件安全分析器, 开源口袋电源,开源健康测量,FreeCAD

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 视频&#xff1a; https://www.bilibili.com/video/BV1TYBhYKECK/ 《安富莱嵌入式周报》第346期&#xff1a;开源2GHz带…

Unity3d C# 摄像头检测敌方单位(目标层级)并在画面中标注(含源码)

前言 需要实现的功能是通过一个专门的检测摄像头将出现在摄像头画面内的敌方单位检测出来&#xff0c;并通过框选的UI框在画面中标记出来。检测摄像头支持自动检测和手动控制检测&#xff0c;同时需要实现锁定模式&#xff0c;检测到一个敌方单位直接锁定到对象上等功能。 效…

【计算机网络】核心部分复习

目录 交换机 v.s. 路由器OSI七层更实用的TCP/IP四层TCPUDP 交换机 v.s. 路由器 交换机-MAC地址 链接设备和设备 路由器- IP地址 链接局域网和局域网 OSI七层 物理层&#xff1a;传输设备。原始电信号比特流。数据链路层&#xff1a;代表是交换机。物理地址寻址&#xff0c;交…

从0在自己机器上部署AlphaFold 3

本文介绍如何在自己本地机器上安装AlphaFold 3。 在10月份&#xff0c;Google DeepMind的首席执行官Demis Hassabis和高级研究科学家John M. Jumper所领导的团队&#xff0c;利用AI技术成功预测了几乎所有已知蛋白质的结构&#xff0c;开发出备受赞誉的AlphaFold&#xff0c;并…

大米中的虫子检测-检测储藏的大米中是否有虫子 支持YOLO,VOC,COCO格式标注,4070张图片的数据集

大米中的虫子检测-检测储藏的大米中是否有虫子 支持YOLO&#xff0c;VOC&#xff0c;COCO格式标注&#xff0c;4070张图片的数据集 数据集分割 4070总图像数 训练组 87&#xff05; 3551图片 有效集 9&#xff05; 362图片 测试集 4% 157图片 预处理 自动定向…

hdlbits系列verilog解答(Exams/m2014 q4a)-86

文章目录 一、问题描述二、verilog源码三、仿真结果一、问题描述 本节学习如何下图中的锁存器电路。 注意图中电路是锁存器,因此quartus会警告说推导出一个锁存器。 模块声明 module top_module ( input d, input ena, output q); 思路: 锁存器是一种对脉冲电平敏感的存储…

关于node全栈项目打包发布linux项目问题总集

1.用pm2部署nest 说明&#xff1a;如果一开始将nest直接打包放到linux服务器上用pm2执行则会报错&#xff0c;这是因为tsconfig.build.tsbuildinfo文件的路径以及相关依赖问题。 报错会为&#xff1a;什么东西找不到.... 所以建议以下为步骤一步一步配置 将整个nest添加压缩包直…

脉冲动画效果

js实现脉冲动画效果&#xff1a; 鼠标点击时&#xff0c;添加动画类&#xff0c;进而实现动画效果&#xff0c;鼠标离开时&#xff0c;移除动画类&#xff0c;回归静态图效果。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UT…

ollama部署bge-m3,并实现与dify平台对接

概述 这几天为了写技术博客,各种组件可谓是装了卸,卸了装,只想复现一些东西,确保你们看到的东西都是可以复现的。 (看在我这么认真的份上,求个关注啊,拜托各位观众老爷了。) 这不,为了实验在windows上docker里运行pytorch,把docker重装了。 dify也得重装: Dify基…

清远榉之乡托养机构探讨:自闭症的本质辨析

当人们谈及自闭症时&#xff0c;常常会产生一个疑问&#xff1a;自闭症是精神类疾病吗&#xff1f;今天&#xff0c;清远榉之乡托养机构就来为大家解开这个疑惑。 榉之乡大龄自闭症托养机构在江苏、广东、江西等地都有分校&#xff0c;一直致力于为大龄自闭症患者提供专业的支持…

Linux自动化部署方法(Linux Automated Deployment Method)

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 本人主要分享计算机核心技…

【Web】0基础学Web—html基本骨架、语义化标签、非语义化标签、列表、表格、表单

0基础学Web—html基本骨架、语义化标签、非语义化标签、列表、表格、表单 html基本骨架语义化标签图片属性a链接 非语义化标签特殊符号标签 列表无序列表结果展示 有序列表结果展示 定义列表结果展示 表格table属性tr属性结果展示 表单单标签form属性input属性selecttextareabu…

ADAM优化算法与学习率调度器:深度学习中的关键工具

深度学习模型的训练效果离不开优化算法和学习率的选择。ADAM&#xff08;Adaptive Moment Estimation&#xff09;作为深度学习领域中广泛应用的优化算法之一&#xff0c;以其高效性和鲁棒性成为许多任务的默认选择。而学习率调度器则是优化算法的“助推器”&#xff0c;帮助训…

飞塔防火墙只允许国内IP访问

飞塔防火墙只允许国内IP访问 方法1 新增地址对象&#xff0c;注意里面已经细分为中国内地、中国香港、中国澳门和中国台湾 方法2 手动新增国内IP的对象组&#xff0c;目前好像一共有8632个&#xff0c;每个对象最多支持600个IP段

C语言进阶7:程序环境与预处理

本章重点 程序的翻译环境程序的执行环境详解&#xff1a;C语言程序的编译 链接预定义符号介绍预处理指令 #define宏和函数的对比预处理操作符#和##的介绍命令定义预处理指令 #include预处理指令 #undef条件编译 1.程序的翻译环境和执行环境 在ANSIC的任何一种实现中&#x…

【数据资产】数据资产管理体系概述

导读&#xff1a;数据资产管理是对企业或组织内部产生的海量数据进行全面、系统、规范的管理&#xff0c;包括数据的收集、存储、处理、分析、利用和保护等环节&#xff0c;旨在挖掘数据价值&#xff0c;提升数据质量&#xff0c;确保数据安全&#xff0c;从而支持业务决策&…

(Python)前缀和

前缀和&#xff1a; 前缀和预先计算并存储一系列连续元素的总和&#xff0c;是一种优化技巧&#xff0c;提高算法效率。记录一个数组中各下标位置之前的所有元素的总和&#xff0c;本文对应下标的总和中不含对应下标元素本身。若有需要也可以对应下标记录的总和包含下标本身元…

HCIA笔记6--路由基础

0. 概念 自治系统&#xff1a;一个统一管理的大型网络&#xff0c;由路由器组成的集合。 路由器隔离广播域&#xff0c;交换机隔离冲突域。 1.路由器工作原理 路由器根据路由表进行转发数据包&#xff1b; 路由表中没有路由&#xff0c;直接丢弃该数据包路由表中只有一条路…

群晖无法删除容器和套件显示报错无法执行此操作,可能是因为网络连接不稳定或系统正忙,请稍后再试 手把手图文教程解决办法

一&#xff0c;背景 安装了一个docker容器handbreak&#xff0c;设定了自动重启&#xff0c;结果一直停止一直重启&#xff0c;无法删除也无法充值&#xff0c;就很坑&#xff5e;&#xff5e; 显示报错无法执行此操作&#xff0c;可能是因为网络连接不稳定或系统正忙&#x…