蓝桥杯备考day2

1.1 map及其函数

• map 提供一对一的数据处理能力，由于这个特性，它完成有可 能在我们处理一对一数据的时候，在编程上提供快速通道。map 中的第一 个值称为关键字(key)，每个关键字只能在 map 中出现一次，第二个称为该 关键字的值(value)，可以重复。

// 定义，以 string, int 对为例
#include <map>
map<string, int> mp; // 底层是红黑树，元素可比较大小，key 的结构体要重载 < 运算// 1- 插入
mp.insert(make_pair("zhs", 18)); // 插入一个键值对，若原先存在该 key，则无法插入和覆盖
mp.insert(pair<string,int>("zhs", 18)); // 插入一个键值对，若原先存在该 key，则无法插入和覆盖
mp["zhs"] = 18; // 甚至可以类似数组下标去访问 key 对应的 value，若原先不存在该 key，则创建，若原先存在，则覆盖以前该关键字对应的值
mp.emplace("zhs", 18); // 插入效果跟 insert 效果完全一样// 2- 删除mp.erase(key); // 删除值为 key 的元素
mp.erase(iter); // 删除迭代器 iter 指向的元素，例如mp.erase(mp.begin());
mp.erase(iter1, iter2); // 删除区间 [iter1, iter2) 的所有元素，例如 mp.erase(mp.begin(), mp.end());
mp.clear(); // 清空集合// 3- 求大小
int siz = mp.size(); // 求集合大小
bool flag = mp.empty(); // 集合判空// 4-查询
if(mp.find(key) != mp.end()) // find 函数返回一个指向被查找到元素的迭代器cout << mp[key] << endl;
if(mp.count(key)) // count 返回某个值元素的个数cout << mp[key] << endl;
auto iter = mp.lower_bound(key); // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
auto iter = mp.upper_bound(key); // 求 key 的上界，返回大于某个值元素的迭代器// 5-遍历
map<string, int>::iterator iter; // 正向遍历for(iter=mp.begin(); iter!=mp.end(); iter++)
{cout << iter->first << " " << iter->second << endl;// 或者cout << (*iter).first << " " << (*iter).second << endl;
}map<int>::reverse_iterator riter; // 反向遍历
for(riter=mp.rbegin(); riter!=mp.rend(); riter++)
{// 遍历的同时修改iter->second += 10;cout << iter->first << " " << iter->second << endl;
}
for (auto x : mp){ // C++ 11 auto 遍历cout << x.first << " " << x.second << endl;
}
for (auto& x : mp){ // C++ 11 auto 遍历x.second += 10; // 遍历并修改cout << x.first << " " << x.second << endl;
}// 6- 求最值
map<string, int>::iterator it = mp.begin(); // 最小值
cout << *it << endl;
map<string, int>::iterator it = mp.end(); // 最大值
cout << *(--it) << endl;
/*
1. map 和 set 一样，其中的元素必须支持 < 运算符
2. 在插入时，使用 insert 和 用数组方式去插入，在原先存在要插入的键值
时是有区别的，insert不会插入，用数组方式插入则会直接覆盖原先数据
3. map 的迭代器支持 ++、--、==、!=、(*iter).first、
(*iter).second、iter->first、 iter->second 等操作
4. map 的迭代器不支持 +、-、 +=、-= 等算术操作符，也不支持 >、<、
>=、<= 等比较操作符
*/

1.2 map的插入和遍历

//map的插入和遍历
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
int main(){int n,age;string s;cin>>n;for(int i=0;i<n;i++){cin>>s>>age;mp[s]=age;}map<string,int>::iterator it;//遍历mapfor(it=mp.begin();it!=mp.end();it++){cout<<it->first<<" "<<it->second<<endl;}return 0;
}

1.3 set及其函数

• set 的含义是集合，它是一个 有序的容器，里面的元素都是排序好的，支持插入、删除、查找等操作，就像一个集合。所有的操作的都是严格在O(logn)时间之内完成，效率非常高。 set 和 multiset 的区别是：set插入的 元素不能相同，但是multiset 可以相同。

// 1- 定义
#include <set>
set<int> s; // 元素必须可比较大小，元素类型必须要支持 < 运算，结构体需要重载 <// 2- 插入
s.insert(key); // 插入// 3- 删除
s.erase(key); // 删除值为 key 的元素
s.erase(iter); // 删除迭代器 iter 指向的元素，例如
s.erase(s.begin());
s.erase(iter1, iter2); // 删除区间 [iter1, iter2) 的所有元素，例如 s.erase(s.begin(), s.end());
s.clear(); // 清空集合// 4- 求大小
int siz = s.size(); // 求集合大小
bool flag = s.empty(); // 集合判空// 5-查询
if(s.find(key) != s.end()) // find 函数返回一个指向被查找到元素的迭代器cout << "exist" << endl;
if(s.count(key) == 1) // count 返回某个值元素的个数cout << "exist" << endl;
set<int>::iterator iter = s.lower_bound(key); // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
set<int>::iterator iter = s.upper_bound(key); // 求 key 的上界，返回大于某个值元素的迭代器
// auto 类型推断关键字 在NOI 系列比赛中也可以使用了
auto iter = s.lower_bound(key); // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
auto iter = s.upper_bound(key); // 求 key 的上界，返回大于某个值元素的迭代器// 6-遍历
set<int>::iterator iter; // 正向遍历
for(iter=s.begin(); iter!=s.end(); iter++)
{cout<<*iter<<endl;
}
set<int>::reverse_iterator riter; // 反向遍历，不重要
for(riter=s.rbegin(); riter!=s.rend(); riter++)
{cout<<*riter<<endl;
}// 7- 求最值
set<int>::iterator it = s.begin(); // 最小值
cout << *it << endl;
set<int>::iterator it = s.end(); // 最大值
cout << *(--it) << endl;
/*
注意：
1. set 和优先队列一样，其中的元素必须支持 < 运算符
2. set 的迭代器支持 ++、--、==、!=、*iter 等操作
3. set 的迭代器不支持 +、-、 +=、-= 等算术操作符，也不支持 >、<、
>=、<= 等比较操作符
*/

1.4 set的插入和遍历

#include<bits/stdc++.h>
using namespace std;
int main(){set<int> s;//set可以自动去重和排序，默认升序int n,t;cin >> n;for(int i=1;i<=n;i++){cin >> t;s.insert(t);//set没有push_back操作}set<int>::iterator it;//set需要使用迭代器遍历数据for(it=s.begin();it!=s.end();it++){//set支持双向迭代器cout << *it << " ";}
}

1.5 ASCII码值、字母大小写转换、’0‘~’9‘

// 数字转字符: 'A'(65) 'a'(97) '0'(48)
char A = char(65);
char a = char(97);
char c = 'a' + 2; // 'c' = 'a' + 2
char seven = '0' + 7; // '7' = '0' + 7
// 字符转数字
int a = 'a'; // a: 97
int A = 'A'; // A：65
int t = 't' - 'a'; // 计算字母间差值
int seven = '7' - '0';

1.6 常见字符串函数与reverse

// 最常用的操作
str.size();//返回字符串长度
str.length();//返回字符串长度
str.empty();//检查 str 是否为空，为空返回 1，否则返回 0
str[n];//存取 str 第 n + 1 个字符
str.at(n);//存取 str 第 n + 1 个字符（如果溢出会抛出异常）// 反转
reverse(str.begin(), str.end());// 查找
str.find("ab");//返回字符串 ab 在 str 的位置
str.find("ab", 2);//在 str[2]~str[n-1] 范围内查找并返回字符串 ab在 str 的位置
str.rfind("ab", 2);//在 str[0]~str[2] 范围内查找并返回字符串 ab在 str 的位置
if(str.find("ab")!=string::npos)
{ cout << "下标为:" << str.find("ab"); 
}// 子串
str.substr(3); // 返回 [3] 及以后的子串
str.substr(2, 4); // 返回 str[2]~str[2+(4-1)] 子串(即从[2]开始4个字符组成的字符串)
str.substring(5, 10); // 返回 str[5]~str[9] 子串(不包含结尾)// 插入
str.insert(2, "sz");//从 [2] 位置开始添加字符串 "sz"，并返回形成的新字符串
str.insert(2, "abcd", 3);//从 [2] 位置开始添加字符串 "abcd" 的前3 个字符，并返回形成的新字符串
str.insert(2, "abcd", 1, 3);//从 [2] 位置开始添加字符串 "abcd" 的前 [2]~[2+(3-1)] 个字符，并返回形成的新字符串// 删除
str.erase(3);//删除 [3] 及以后的字符，并返回新字符串
str.erase(3, 5);//删除从 [3] 开始的 5 个字符，并返回新字符串// 替换
str.replace(2, 4, "sz");//返回把 [2]~[2+(4-1)] 的内容替换为 "sz"后的新字符串
str.replace(2, 4, "abcd", 3);//返回把 [2]~[2+(4-1)] 的内容替换为"abcd" 的前3个字符后的新字符串// 追加
str = str + "abc";
str.push_back('a');//在 str 末尾添加字符'a'
str.append("abc");//在 str 末尾添加字符串"abc"

1.7 stringstream

• stringstream 主要是用在字串分割，可以先用 clear() 以及 str() 将字 符串读入并进行分割，再用 >> 把内容输出，例如：

string s;
stringstream ss;
int a, b, c;
getline(cin, s);
ss.clear();
ss.str(s);
ss >> a >> b >> c;

1.8 字典序

• 什么是字典序：所谓字典序就是以ASCII码排序。
• 比如两个字符串 abcd 和 abdd 比较大小。 从第一个字符开始逐位比 较，第一个字符不相等，谁的ASCII码值小谁的字典序就小。若第一个相 等，继续逐位比较后续字符。比较到字母c < 字母d，所以第一个字符串 abcd 字典序较小。
• 再比如 hist 和 history 比较大小。若逐位比较都相等，但其中一 个没有后续的字符了，则较短的串 hist 字典序较小。
• 使用 sort() 可以对字符串进行字典序排序，字符按ASCII码值由小 到大排列

string str = "agfdvdsgds";
sort(str.begin(),str.end());

1.9 结构体排序

• 结构体是 自定义类型 ，它就像一个 能装不同数据类型 的“包裹”。当你声明 一个结构体后，需要赋予这个结构体一个名字（即 结构体名 ）。而 定义具 体变量时，也可以定义结构体数组 。这相当于告诉计算机，你一口气定义 了许多“包裹”，每一个“包裹”里面都可以装入许多不同或相同数据类型的变 量。

1. **结构体的声明：**使用结构体前，需要先声明一个结构体类型，再进行定义和使用。结构体 类型的声明格式为：

   struct 结构体类型名{ //其中，sruct是关键字，在c++中表示结构体数据类型 成员变量1; //多个成员变量可以具有不同的数据类型数据类型 成员变量2;......
   };
   

   声明之后，就可以定义结构体变量了，格式如下：

   结构体类型名 变量名；（struct 可省略）
   

   例如 我们需要表示一个学生的信息，首先我们声明学生的结构体：

   struct student{ //student表示结构体的类型名string name;char sex;int age;float height,score;
   };

   然后定义一个具体的学生：

   student zhangsan;//声明一个student的结构体变量叫zhangsan
   

   当然我们如果需要很多学生，可以声明为结构体数组：

   student a[1001];//创建结构体数组a
   //a数组中的每一个元素都是一个结构体类型student的变量
   

   另外 为方便起见，我们一般直接在声明结构体的同时定义变量，格式如下：

   struct 结构体类型名{ //其中，sruct是关键字，在c++中表示结构体数据类型成员变量1； //多个成员变量可以具有不同的数据类型数据类型成员变量2；......
   }结构体变量表;
   

   比如：

   struct student{string name;char sex;int age;float height,score;
   }a[1001];
   

2. .结构体的使用

• 将结构体变量视为一个整体进行操作，例如：

  swap(a[1], a[2]);
  

• 使用符号“.”对结构体变量的成员进行操作，“.”的含义可以理解为中文 的“的”，格式为：

  结构体名.成员变量名
  

  比如：

  student a;//李四
  cin >> a.name;//输入赋值李四的名字
  a.age = 23;//直接赋值给李四的年龄为23
  

3. 结构体的初始化

• 集合形式，比如：

  student a = {"tuotuo",'F',12,168,100};
  

• 逐一赋值，比如：

  student a;
  cin >> a.name >> a.sex;
  a.age = 12;
  

4. 结构体中的sort()函数

• 现在给你一个结构体，现在有这样一个要求：按照年龄从小到大输出。 那我们就照结构体中成员变量age（也就是年龄）进行从小到大的排序，代 码如下：

    #include<bits/stdc++.h>using namespace std;struct student {  string name;  int age;  float height;  };  bool cmp(const student& a, const student& b) {  return a.age < b.age;  }  int main() {  student a[10] = {  {"Alice", 20, 165.5},  {"Bob", 22, 180.0},  {"Charlie", 19, 170.2},  {"David", 21, 175.0},  {"Eve", 20, 160.0},  {"Frank", 23, 185.0},  {"Grace", 18, 155.0},  {"Henry", 22, 182.0},  {"Isabella", 21, 168.0},  {"Jack", 19, 172.0}  };  // 打印排序前的学生信息  for (int i = 0; i < 10; i++) {  cout << "Name: " << a[i].name << ", Age: " << a[i].age << ", Height: " << a[i].height << endl;  }  // 使用 sort 函数对数组进行排序  sort(a, a + 10, cmp);  // 打印排序后的学生信息  cout << "Sorted by age:" << endl;  for (int i = 0; i < 10; i++) {  cout << "Name: " << a[i].name << ", Age: " << a[i].age << ", Height: " << a[i].height << endl;  }  return 0;  }

1.10 浮点数比较

• 因为C/C++内置的double类型也是由相应的二进制存储的，所以double在 计算的时候是会可能丢失精度的，最后进行浮点数比较的时候要注意做一 个 fabs

  //比较两个浮点数是否相等
  bool compareDouble(double a,double b)
  {
  double eps = 1e-6 //注意精度，默认是1e-6，有时候精度要求不高可
  以降低精度要求
  if(fabs(a-b)<eps) return true;
  return false;
  }
  

1.11 调试中常见错误

1. 注意 数据范围!!!定义单个变量能用 long long 就不要用 int ，能定义为 double 就不要用 float 。
2. maxn 、 minn (最大值、最小值)或者 cnt (计数器)忘记 赋初始值。
3. 忘记删除用来检查代码的语句，比如添加了多余的打印操作。
4. 没理解题目的意思，就开始做题。要结合样例去理解题目。
5. 注意题目数据范围很大的时候， 考虑优化。
6. 数组开太大。比如: int arr[10000][10000] ，则 arr 的空间大小约为 400M，远超题目的空间限制。
7. 边界条件考虑不充分。
8. 变量命名与c++自带的名称冲突(因此，慎用万能头文件)。如:int time; int max; int min等等。
9. 写了初始化函数 ，没有调用。
10. 使用函数时， 参数传错。
11. 用了一个新的知识点，但自己不太清楚，就用了。要注意，写的代码最好是你完全能明白的。
12. if里面的判断条件没想清楚，还继续往下写。
13. 循环里面条件写反，比如: for(int i = n;i > 0;i+ +)
14. 双重循环里面 i 和 j写反，或者两个循环变量都写成 i。
15. 字符串 string 中，遍历 string 的操作最好用 for(int i = 0;i < s.size(); i++) ，不要用小于等于 i<= s.size() - 1