决战蓝桥杯笔记！

语言基础

万能头文件

#include<bits/stdc++.h>

输入与输出

使用scanf()读取字符串可使用正则表达式

char  a[40];
scanf("%[^\n]",a)

使用scanf和cout(默认保留）保留小数点

double a = 3554.554453;
printf("%.3lf\n"); //保留三位小数四舍五入(大致理解为四舍五入，详情参见csdn相关问题)
cout << fixed << setprecision(3) <<a <<'\n';//保留三位小数并不是四舍五入

使用getline()读取字符串

string s ;
getline(cin,s);
cout << s;

取消同步流（加速cin cout） cin和cout的默认读写效率比较低，会导致时间复杂度上升

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) 
//其他代码不变

string的使用

需要在头文件包含如果使用万能头文件可忽略

#include<string>
//需要
//using namespace std;
//否则下面都需要加std::
//比如声明一个字符串
std::string a1;

• 自动处理内存空间分配和释放
• 动态调整大小
• 支持迭代器
• 提供越界访问检查

使用部分字符串初始化字符串也就是取出内容

.substr(起始位置,长度)

std::string str1="hello world";
std::string str=str1.substr(0,5);// str中的内容为:hello

使用字符数组初始化字符串

char * charArray ="Hello";
std::string str(charArry);

使用重复的字符初始化字符串

std::string std(5,'A'); //内容为:AAAAA

输入字符串getline()

std::string s;
std::string str;
cin>>str; //遇到空格或者回车就会结束
getline(cin,s);

输入流成员函数getline()

在< istream >中的getline()函数有两种重载形式：

istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

作用是： 从istream中读取至多n个字符(包含结束标记符)保存在s对应的数组中。即使还没读够n个字符，
如果遇到delim 或 字数达到限制，则读取终止，delim都不会被保存进s对应的数组中。

#include <iostream>
using namespace std;

int main()
{
	char name[256];
	cout << "Please input your name: ";
	cin.getline(name, 256);
	cout << "The result is:   " << name << endl;

	return 0;

}

#include <iostream>
using namespace std;

int main( )
{
   char line[100];
   cout << " Type a line terminated by 't'" << endl;
   cin.getline( line, 100, 't' );
   cout << line << endl;
   
   return 0;
}

普通函数getline()

istream& getline (istream&  is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);
istream& getline (istream&  is, string& str);
istream& getline (istream&& is, string& str);

函数的变量：

is ：表示一个输入流，例如 cin。
str ：string类型的引用，用来存储输入流中的流信息。
delim ：char类型的变量，所设置的截断字符；在不自定义设置的情况下，遇到’\n’，则终止输入

用法和上一种类似，但是读取的istream是作为参数is传进函数的。读取的字符串保存在string类型的str中。

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string name;
	cout << "Please input your name: ";
	getline(cin, name);
	cout << "Welcome to here!" << name << endl;

	return 0;

}

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string name;
	cout << "Please input your name: ";
	getline(std::cin, name, '#');
	cout << "Welcome to here!" << name << endl;

	return 0;
}

以上内容转载至C++中getline()的用法-CSDN博客帮助你更好理解

string的基本操作

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

在使用printf输出是需要将string转化为char类型

c_str()用于返回一个指向空字符结尾的C风格字符串即const char*类型

string str="dsdhijhfdjkvhjkdf";
printf("%s\n",str.c_str());

获取字符串长度length/size() unsigned类型

string str="dsdhijhfdjkvhjkdf";
int length =str.length; //或者int length = str.size();

拼接字符串+/append()

string str="ddsd";
string str2="dsdhijhfdjkvhjkdf";
string str3=str+str2;
string str4=str.append(", ")+str.append(str2); //使用append()函数

字符串查找find()

关于size_t与ssize_t详解-CSDN博客

简介:size_t 是一些C/C++标准在stddef.h中定义的，size_t 类型表示C中任何对象所能达到的最大长度，它是无符号整数。

因为size_t 是无符号的，一定要给这种类型的变量赋正数 。

string str="Hello,World";
size_t pos = str.find("World"); //返货"World"的起始位置"7"
if(pos != srd::string::npos) //srd::string::npos 本质上为 -1
{
   printf("找到了");
}else{
   printf("没找到");
}

字符串拼接replace(起始位置,要替换的长度,内容);

string str="Hello,World";
str.replace(7,5,"Universe");
//结果为:Hallo Unicerse

提取字符串.substr(起始位置,长度)

不要越界

string str="Hello,World";
str.substr(7,5);//内容为World

字符串比较compare(),直接比较

string重载了不等号,所以可以直接使用s1<s2来直接比较string大小

比较规则按照字典序大小比较

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

例如
"aaaa"<"bbbb" 返回 1

"azz"<"ava" 返回 0

"azzzzzzzzzzzzz"< "b"

"lanqiao" == "lanqiao"

string str="Hello";
string str2="World";
int result =str.compare(str2);
if(result==0){
   printf("字符串一样");
}else if(result <0){
   printf("字符串1小于字符串2");
}else{
 printf("字符串1大于字符串2");

}

循环枚举下标和auto枚举

涉及内容

【C++】auto关键字(C++11，超详细解析，小白必看系列）_c++ auto-CSDN博客

C++基于范围的for循环详解 - / - 博客园 (cnblogs.com)

C++ 引用（&）的超详细解析（小白必看系列）_c++ &-CSDN博客

string s = "Hello";
for(int i=0;i<s.length();++i)cout <<s[i];
cout<<'\n';
for(auto i ：s){
cout<< i;
i='a';//此处的修改无效，因为这个i是拷贝出来的，而不是引用s的
}
cout<<'\n';//此时s = "Hello"
for(auto &i : s){
cout<< i;
i ='a';//此处修改会改变s的字符值
}
//此时s="aaaaa'
cout <<'\n';

reverse(begin，end);可反转

相关内容：

C++ 迭代器(iterator)超详解+实例演练_c++ iterator-CSDN博客

竞赛常用函数库函数

排序

sort(起始地址，结束地址的下一位，*自定义比较函数【可不写】)；

C++ sort()排序详解-CSDN博客

包含在头文件#include中使用万能头文件不必关心是否引入这个头文件，快速排序，类似快速排序的改进算法。区间是左闭右开

对数组进行排序

int a [1000];
int n;
cin >> n;
for (int i =1 ; i<=n ;i++) cin >> a[i];

sort(a+1，a+n+1); //左闭右开 即不包含 a[n+1] 为 a+1 ~ a+n 

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

迭代器

vector<int> v = {7,8,4,6,98,3,3};
//排序
sort(v.begin(),v.end());
//输出
for(int i=0;i<v.size();++i)cout<<v[i];

自定义比较函数（可以是函数或者lambda表达式）

函数必须为bool类型 const和引用&可以不写

使用函数

bool cmp(const int &u,const int &v){
 return u>v;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); //取消同步流
  vector<int> v = {7,8,4,6,98,3,3};
  sort(v.begin(),v.end(),cmp);  
  for(int i =1; i<=n ; ++i ) cout << a[i] << '';
   
}

使用lambda

C++ 函数 | 菜鸟教程 (runoob.com)

bool cmp(const int &u,const int &v){
 return u>v;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); //取消同步流
  vector<int> v = {7,8,4,6,98,3,3};
  sort(v.begin(),v.end(),[](const int &u,const int &v){
   return u>v;
});  
  for(int i =1; i<=n ; ++i ) cout << a[i] << '';
   
}

结构体(类)的自定义比较函数

C++ 重载运算符和重载函数 | 菜鸟教程 (runoob.com)

C++ 友元函数 | 菜鸟教程 (runoob.com)

C++ 类 & 对象 | 菜鸟教程 (runoob.com)

结构体(类)可以将小于号重载后进行排序

struct Node{
   int u,v;
    const bool operator < (const Node &m){
       //以u为第一关键字，v为第二关键字
       return u==m.u ? v<m.v :u<m.u;
   
   }
}

min()和max()函数

只能传入两个值或者一个列表

int a=3,b=4;
min(a,b); //结果为3
int c[] ={1,2,3,4};
max(c); //结果为 4

min_element()和max_element()

min_element(st,ed);返回地址[st,ed)中最小的那个值的地址（迭代器）,传入参数为两个地址或者迭代器

max_element()相似将不再演示

vecror<int> v ={5,6,7,5,6,7};
cout << *max_element(v.begin,v.end());

nth_element(first,nth,last,comp)函数

• first：指向序列起始位置的迭代器。
• nth：指向目标位置的迭代器，函数会将第 n 个元素放置在正确的位置。
• last：指向序列末尾的迭代器（不包含）。
• comp：可选参数，用于自定义比较函数（默认为 operator<）。

进行部分排序，返回值为void

它的主要作用是将序列中的第 n 个元素放置在排序后它应该处于的位置，同时保证该元素左边的所有元素都不大于它，右边的所有元素都不小于它。但它不保证左右两侧的完全排序。

二分法

整数二分

浮点二分

二分答案

全排列

next_permutation()

next_permutation 是C++标准模板库（STL）中的一个函数，定义在 头文件中,它用于生成给定序列的下一个字典序排列。如果可以生成下一个排列，则函数返回 true，否则返回 false。当序列已经是最大字典序排列时，例如降序排列，函数将返回 false。

prev_permutation()

prev_permutation() 是C++标准库中的一个函数，定义在 头文件中。它用于生成当前排列的前一个排列（按字典序），如果存在这样的排列，则返回 true 并更新排列到前一个排列；如果没有更小的排列（即当前排列已经是第一个排列），则返回 false 并保持排列不变。

这个函数非常有用，特别是在需要遍历所有可能排列的情况下，可以与 next_permutation() 结合使用来双向遍历排列。

memset()

memset() 函数用于将内存中的某一块填充为一个特定的值。它定义在 头文件中，主要用于初始化数组或重置大块内存。

swap()

swap() 用来交换两个变量的值。不同类型的变量有不同的 swap 实现，通常位于各自的命名空间或头文件中，如 <utility> 对于基本类型和类对象。

reverse()

reverse() 是用来反转指定范围内的元素顺序，定义在 <algorithm> 头文件中。

unique()

**注意：**使用unique()需要首先对其排序。

unique() 移除连续**(相邻)**重复的元素，保持唯一性，但不会改变容器大小。它返回一个指向新的逻辑末尾的迭代器（即最后一个不重复元素之后的位置）。定义在 <algorithm> 中。

.erase()

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 2, 3, 3, 3, 4};
    auto it = std::unique(v.begin(), v.end());
    v.erase(it, v.end()); // 删除多余的元素
    for (auto &i : v) std::cout << i << " "; // 输出: 1 2 3 4
    return 0;
}

注意：unique() 只能移除相邻的重复项。如果需要移除非相邻的重复项，则需要先对序列进行排序或使用其他方法。

pair

在C++中，pair 是标准库中的一个模板类，定义于 <utility> 头文件中。它用于将两个不同类型的值组合在一起，形成一个复合类型。pair 常用于需要返回两个值的函数，或在容器（如 map 或 unordered_map）中存储键值对。

定义和初始化

你可以通过以下方式定义和初始化一个 pair：

#include <utility> // 包含pair的定义
#include <iostream>

int main() {
    std::pair<int, double> p1; // 默认构造，值为0和0.0
    std::pair<int, double> p2(10, 3.14); // 使用指定值初始化
    auto p3 = std::make_pair(5, 2.71); // 使用make_pair辅助函数创建pair

    std::cout << "p2: " << p2.first << ", " << p2.second << std::endl;
    std::cout << "p3: " << p3.first << ", " << p3.second << std::endl;

    return 0;
}

成员变量

• first: 访问 pair 中的第一个对象。
• second: 访问 pair 中的第二个对象。

常用操作

比较操作

pair 支持比较操作符 (==, !=, <, <=, >, >=)。比较时首先比较第一个元素，如果相同再比较第二个元素。

tie解包

使用 std::tie 可以方便地解包 pair 的值：

int a, b;
std::pair<int, int> p(1, 2);
std::tie(a, b) = p; // a=1, b=2

获取元素

除了直接访问 first 和 second，还可以使用 std::get 函数来获取元素：

auto p = std::make_pair(10, "test");
int num = std::get<0>(p); // 获取第一个元素
std::string text = std::get<1>(p); // 获取第二个元素

应用场景

• 作为函数返回值：当一个函数需要返回多个值时，可以使用 pair 来封装这些值。
• 在容器中使用：如 std::map 和 std::unordered_map，它们使用 pair 来存储键值对。
• 算法参数：某些标准库算法接受 pair 作为参数或返回值。

通过 pair，C++ 提供了一种简便的方法来处理和组织成对的数据，使其在多种编程情境下都非常有用。

std::make_pair 是C++标准库中的一个辅助函数模板，定义在 <utility> 头文件中。它用于创建一个 std::pair 对象，而不需要显式指定 pair 的类型参数。make_pair 通过自动推导传递给它的参数类型来简化 pair 的创建过程。

使用 std::make_pair

使用 std::make_pair 可以让你更方便地创建 pair 对象，尤其是在你希望避免手动指定模板参数时。它特别适用于需要返回 pair 的函数或当你想要将不同类型的数据组合在一起时。

基本用法

#include <utility> // 包含 std::make_pair 和 std::pair
#include <iostream>

int main() {
    auto p = std::make_pair(10, "Hello"); // 自动推断类型为 pair<int, const char*>
  
    std::cout << "First: " << p.first << ", Second: " << p.second << std::endl;

    return 0;
}

在这个例子中，std::make_pair 自动推断了 pair 的类型（第一个元素是 int 类型，第二个是 const char* 类型），并创建了一个相应的 pair 实例。

与直接初始化对比

对比直接初始化 pair 的方式：

std::pair<int, const char*> p_direct(10, "Hello");

虽然这两种方法都可以创建相同的 pair，但使用 std::make_pair 更加简洁，特别是在类型可以被推导出来的情况下。

在容器中使用

std::make_pair 经常用于向关联容器（如 map 或 unordered_map）插入数据时，因为这些容器的 insert 方法通常接受 pair 类型的参数：

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<int, std::string> myMap;
    myMap.insert(std::make_pair(1, "One"));
    myMap.insert(std::make_pair(2, "Two"));

    for (const auto& elem : myMap) {
        std::cout << elem.first << ": " << elem.second << std::endl;
    }

    return 0;
}

这段代码展示了如何使用 std::make_pair 向 map 中添加键值对。

总结

• 便捷性：std::make_pair 提供了一种简便的方式来创建 std::pair，无需显式指定模板参数。
• 自动类型推导：能够根据传入的参数自动推导出 pair 的类型，使得代码更加简洁和易于维护。
• 广泛的应用场景：不仅限于直接使用，在许多STL算法和容器操作中都非常有用，比如在 map、unordered_map 等关联容器的操作中。

通过 std::make_pair，你可以更高效且优雅地处理需要成对数据的情况。

stack