TODO：编写属于自己的模板，探索属于自己的编码习惯并记录
#cppreference是个好东西
1. to_string <string>库 c++11
2. string加法（+）必须保证每个加法运算符（+）的两侧的运算对象至少有一个是string
如 s1="sdf"+s2 正确
s1="htyru"+"qwe" 错误
3. 过多的连续条件判断可以用数组存储，如：
string num[10]={
"zero","one","two","three","four",
"five","six","seven","eight","nine"
};
4. string可以直接用< > <= >= 按照字典序比较，也可以自定义比较准则
5. 善用函数封装
6. <cctype>库里有tolower isalnum isdigit之类的用于判断和处理单个字符的有用函数
isalpha isalnum isupper islower
isdigit isxdigit isspace isblank
isgraph isprint iscntrl ispunct
7. unordered_map 遍历 用auto或者迭代器遍历
8. printf("<格式化字符串>", <参量表>); format 标签属性是 %[flags][width][.precision][length]specifier
https://www.runoob.com/cprogramming/c-function-printf.html
https://learn.microsoft.com/zh-cn/cpp/c-runtime-library/format-specification-syntax-printf-and-wprintf-functions?view=msvc-170
flags标识: 0 - + 空格 #
width宽度: (number) *
.precision精度: .number .*
length长度: h l ll L
specifier格式字符: d o x X f e E g G c s p u lu llu a A
printf输出整数固定长度前导零可选两种写法：%03d(flags为0，width为3)或者%.3d(.precision为.3)
sprintf可以将格式化的字符串写入指定c风格字符串，
如
int a=10,b=20;
char str[10];
sprintf(str,"a=%d,b=%d",a,b);
int sprintf(char *str, const char *format, ...) 发送格式化输出到 str 所指向的字符串。
输出 long long使用%lld
输出 double和float都用%f printf里没有%lf一说
输入 double用%lf float用%f
https://blog.csdn.net/weixin_43889841/article/details/104106209
9. 考试中建议放到最后写的题：
1.复杂的长的模拟题
2.计算几何的题
3.复杂的数据结构
10. scanf对字符类型有%c和%s两种格式(printf同理)，其中%c用来输入单个字符，%s用来输入一个字符串并存在字符数组
里。
scanf不能读入并存进string，但是printf可以利用string的成员函数c_str()将string字符串转换成c风格字符串来输
出string字符串
%c格式能够识别空格跟换行符并将其输入，而%s通过换行符或空格来识别一个字符串的结束。
%c不消耗前导空白字符，其余常见占位符都消耗前导空白字符
&a、&b、&c 中的 & 是地址运算符，分别获得这三个变量的内存地址。
如果是数组（如：字符数组），则直接使用数组名作为变量的内存地址用作输入参数。
#include <stdio.h>
int main()
{
int a,b,c;
scanf("%d, %d, %d",&a,&b,&c);
printf("%d, %d, %d\n",a,b,c);
char a,b,c;
scanf("%c%c%c",&a,&b,&c);
printf("%c,%c,%c\n", a,b,c);
char str1[20];
scanf("%s", str1);
printf("%s\n", str1);
return(0);
}
11. for(auto a : b)时，a用&引用即for(auto &a : b)将不涉及复制，运行会更快；
12. bool operator< (const Record& t)const{
return minutes < t.minutes;
}
1.运算符重载：operator关键字https://www.runoob.com/cplusplus/cpp-overloading.html
2.const用法：https://www.runoob.com/w3cnote/cpp-const-keyword.html
1.（第一个const）const参数传递：C.
自定义类型的参数传递，需要临时对象复制参数，对于临时对象的构造，需要调用构造函数，比较浪费时间，因
此我们采取 const 外加引用传递的方法。
2.（第二个const）const修饰成员函数：const修饰类成员函数，其目的是防止成员函数修改被调用对象的值，如
果我们不想修改一个调用对象的值，所有的成员函数都应当声明为 const 成员函数。
3.等等
STL中的各种排序算法默认使用小于号<，所以如果main函数中没有用到大于号>，只是用到STL中的小于号<，那么只重载小于号就够用了
除非使用到大于号，那么在需要让大于号含义变化的前提下，就必须重载大于号
13. 用vector数组存struct结构体时，如果要push_back进新元素，记得使用{成员变量1，成员变量2，...}初始化一个临
时的struct对象
{}花括号的作用是创建一个临时的struct结构体对象，并将该对象的成员变量初始化为花括号内提供的值。这种语法被称为
聚合初始化（aggregate initialization），它允许在创建对象的同时进行成员变量的初始化。
如果去掉{}花括号，push_back()将无法正确执行，因为push_back函数期望一个struct结构体对象作为参数，而没有
提供合适的初始化值。
所以，如果去掉{}花括号，会导致编译错误或未定义的行为，因为没有正确初始化struct结构体对象的成员变量，这
可能会影响代码的逻辑和正确性。
14. 一定要记得开c++11 编译器编译命令添加-std=c++11
15. 凡是遇到需要求一段区间内的总和或者一段时间内的总和，一般转化为求两个前缀和做减法，这样就只需要考虑一种
边界即可，否则需要考虑两种边界
16. string有一个构造函数，可以将输入的char数组转化为string，可以看作某种隐式转换
17. <cmath>
round(x)四舍五入
ceil(x)向上取整
floor(x)向下取整
18. 哨兵技巧
A sentinel is a dummy object that allows us to simplify boundary conditions.
哨兵是用来简化边界问题的虚设对象
所谓“哨兵”就是用一个特殊值来作为数组的边界，使用“哨兵”可以少用一条判断语句，所以可以提高程序的效率。
比如设置一个虚拟头结点dummy，操作完之后返回的时dummy->next
19. set与map
关于set/map，multi，unordered_的选取：
只存键还是要存键值对？
只存键——set；；存键值对——map
键能否允许重复存在？
允许重复存在——加multi前缀；；不允许重复存在——不加multi前缀
主要目的是排序还是查找？
排序——不加unordered；；查找——加unordered
20. 枚举的区间范围比较大的时候一般用二分来求
21. long long习惯先'typedef long long LL;'
22. unsigned int 0 ~ 4294967295
int -2147483648 ~ 2147483647(-2^31~2^31-1)(≈2*10^9)
unsigned long 0 ~ 4294967295
long -2147483648 ~ 2147483647
long long -9223372036854775808 ~ 9223372036854775807(-2^63~2^63-1) (≈9*10^18)
unsigned long long的最大值：18446744073709551615 //20位
double (2.22507e-308)~(1.79769e+308) 精度最多小数点后16位，能保证15位有效数字
float (1.17549e-038)~(3.40282e+038) 精度最多小数点后7位，能保证6位有效数字
23. 秦九韶算法将一元n次多项式计算次数大大降低，从朴素算法乘法O(n^2)加法O(n)降低到乘法O(n)加法O(n)
也可用于进位制换算
int res=0;
for(auto a : n){//递推
res=res*x+a;
}
进位制换算（秦九韶）：
10进制 => r进制 模r，除r，倒着读
r进制 => 10进制 从高位开始：res*r+当前位数值
24. long long作乘法会溢出，需要先转成double类型
(double)(a * b)和(double) a * b不等价，前者先计算乘法，可能会溢出
25. string to int ===> stoi()函数 <string>
int to string ===> to_string()函数 <string>
string to c风格字符串 ===> c_str()函数 <string>
c风格字符串 to int/float/long等 ===> atoi()/atof()/atol()等函数 <cstdlib>
26. 读取一行
getline(cin,s,delim); s字符串 delim终止符号<string>
cin.getline(char*,cnt,delim) char*字符串 cnt字符串大小 delim终止符号 <istream>
https://blog.csdn.net/weixin_41042404/article/details/80934191
- 按整行读到string ，推荐用 getline(cin, string) (读到回车为止丢弃结尾回车)<string> 库函数？
- 按整行读到char[] ，推荐用 cin.getline(char*,cnt) (同上)<istream> cin的成员方法？
- 读单个字符串，推荐用 cin>> (不丢弃回车，scanf同)
- 读到某个特殊字符为止，上述按行读getline两种方法增加“终止符号delim”参数
- cin>>之后接getline(cin,s)或者cin.getline(c,100,’\n’)会少读取一行
因为cin>>读取结束后留了一个回车在缓冲区，需要清除缓冲区的回车
可用cin.ignore()或者getchar()等方法清除
推荐用cin.ignore()
https://www.acwing.com/solution/content/10357/
27. 从字符串中读取
sscanf(butter,format,...) <cstdio>
butter 读取来源空终止字符串
format 读取格式
... 参数
28. 数组复制过来加引号技巧：
巧妙使用替换将,替换为','
29. 编译运行之前检查以下是否已经进行所有读入操作，避免出现没有读入数据而引起的无限循环等情况
如：忘记cin最开头的n
30.lower_bound(first,last,val)在 [first, last) 区域内查找第一个大于等于 val 的元素
如果想利用它查找第一个小于等于val的元素，可以尝试使用以下方法：
将原数组乘以一个负号，然后再从小到大排序，然后使用lower_bound()查找，查找完之后再负负得正得到答案
31. <sstream>stringstream 字符串string流类
1）与getline配合，从一行带空格的字符串中提取一个个词
string s;
getline(cin,s);//"asdf jhg hgf"
stringstream ssin(s);//类对象初始化
//stringstream ssin;
//ssin << s;
string a,b,c;
ssin >> a >> b >> c;//a="asdf" b="jhg" c="hgf"
cout << a << endl << b << endl << c;
也可以使用类似while(ssin>>t[i])的方式循环读取
2）多个字符串拼接
stringstream sstream;
// 将多个字符串放入 sstream 中
sstream << "first" << " " << "string,";
sstream << " second string";
cout << "strResult is: " << sstream.str() << endl;//输出：strResult is: first string, second string
// 清空 sstream
sstream.str("");
sstream << "third string";
cout << "After clear, strResult is: " << sstream.str() << endl;//输出：After clear, strResult is: third string
3）（多次）数据类型转换
stringstream sstream;
int first, second;
// 插入字符串
sstream << "456";
// 转换为int类型
sstream >> first;
cout << first << endl;//输出：456
// 在进行多次类型转换前，必须先运行clear()
sstream.clear();
// 插入bool值
sstream << true;
// 转换为int类型
sstream >> second;//输出：1
cout << second << endl;
4）待补充
32. &引用
引用可以看做是数据的一个别名，通过这个别名和原来的名字都能够找到这份数据
引用的定义方式类似于指针，只是用&取代了*
引用的格式：type &name = data;
引用必须在定义的同时初始化，并且以后也要从一而终，不能再引用其它数据，这有点类似于常量（const 变量）。
注意，引用在定义时需要添加&，在使用时不能添加&，使用时添加&表示取地址。除了这两种用法，&还可以表示位运算中的与运算。
由于引用 r 和原始变量 a 都是指向同一地址，所以通过引用也可以修改原始变量中所存储的数据
如果读者不希望通过引用来修改原始的数据，那么可以在定义时添加 const 限制，形式为：const type &name = value;也可以是：type const &name = value;这种引用方式为常引用
在定义或声明函数时，我们可以将函数的形参指定为引用的形式，这样在调用函数时就会将实参和形参绑定在一起，让它们都指代同一份数据。
如此一来，如果在函数体中修改了形参的数据，那么实参的数据也会被修改，从而拥有“在函数内部影响函数外部数据”的效果。
待补充……
33. 存在并列的排名方式 代码技巧：
1）排序之后二分查找大于等于对应成绩/小于等于对应成绩的第一个所在的位置，就是并列的排名
2）排序之后从头开始一个一个赋予一个排名，和前面不一样的就是所在位置的排名，和前面一样的就是前面那个排名
如：
struct Student{
int grade,rank;
};
vector<Student> g;
for(int i=0;i<g.size();i++){
if(!i||g[i].grade!=g[i-1].grade)
g[i].rank=i+1;
else
g[i].rank=g[i-1].local_rank;
}
34. 使用scanf不能输入string字符串
但是可以先定义一个char数组（不能是char*指针，因为这个指针将是一个野指针）
然后利用%s（消耗前导空白字符，可以通过换行符和空格等识别一个字符串结束）进行scanf读入（char数组变量名前不需要&）
之后利用c字符串 to string的隐式转换将char数组的值赋值给对应string
即可实现基于scanf的string输入
如：
char id[10],name[10];//为什么char*不行？
scanf("%s%s%d",id, name,&grade);//%s能忽略前导零
//string sid=id,sname=name;//c字符串 to string 的隐式转换
printf输出string时，需要利用string类的成员函数c_str()将string转化为const char*参数传给printf，使用%s占位符
如：
printf("%s %s %d\n",s.id.c_str(),s.name.c_str(),s.grade);//string.c_str(),,c_str()是string类的成员函数
35. c_str() <string>
const char *c_str();
c_str()函数返回一个指向正规C字符串的指针常量, 内容与本string串相同。
这是为了与c语言兼容，在c语言中没有string类型，故必须通过string类对象的成员函数c_str()把string 对象转换成c中的字符串样式。
注意：一定要使用strcpy()函数 等来操作方法c_str()返回的指针。
//char* c;
//string s="1234";
//c = s.c_str();
//error: invalid conversion from ‘const char*’ to ‘char*’ [-fpermissive]
char c[20];
string s="1234";
strcpy(c,s.c_str());
c_str()返回的是一个临时指针，不能对其进行操作。
string s = "Hello World!";
printf("%s", s.c_str()); // 输出 "Hello World!"
36. 当输入规模大于10^5时，容易卡常
建议把所有cin cout全部换成scanf printf
一定要“全部”换完，否则会因为cin cout与scanf printf同步而导致运行时间变慢
y总推荐输入规模大于等于10^6用scanf printf，否则用cin cout
不太推荐手动解除同步（关同步流），关了就不能正常使用scanf printf了,而且也没有scanf printf快：
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
快读模板（读大量大量整数时很快）（cugbACM）（其他模板去acwing收藏或者洛谷之类的地方找）
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x) {
int f = 1;
x = 0;
char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
x *= f;
}
int main() {
int a, b;
read(a); read(b);// 这里教如何使用 计算a+b
printf("%d", a + b);
return 0;
}
37. PAT对于STL考查非常多，尤其是string、vector、map、unordered_map，基本每题必用，所以考前多看看STL
38. C++里面存链表，一般使用struct Node存两个信息
struct Node{
int val;
Node* next;
Node() {}//构造函数//不带分号
Node(int _val):val(_val),next(NULL){}//构造函数
};
int main(){
//第一种写法
Node node = Node(1);//定义了Node类型的变量，调用构造函数生成了一个val是1的Node对象，将其赋给变量node
Node* p = &node;//然后定义Node类型指针p，指向变量node
//第二种写法
Node* p = new Node(1);//作用相当于上面两行合并
//new 关键字动态开辟了一段空间，将Node(1)构造的新对象的地址返回，然后赋值给Node类型指针p
}
首元结点、头结点、头指针
1、首元结点：就是指链表中存储第一个数据元素a1的结点。
2、头结点：它是在首元结点之前附设的一个结点，其指针域指向首元结点。
3、头指针：它是指向链表中的第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。
设置头结点有什么优点呢？
1、增加了头结点后，首元结点的地址保存在头结点（就是所说的“前驱”结点）的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理
2、便于空表的和非空表的统一处理；当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度n为0的空表时，L指针为空（判断空表的条件可记为：L==NULL）
- 链表中第一个结点的存储位置叫做头指针.
- 头指针具有标识作用，故常用头指针冠以链表的名字。头指针仅仅是个指针而已。
- 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
- 头结点不是链表所必需的。
- 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
- 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。
链表的遍历：
for(Node* i = head; i; i = i->next){
//for(Node* i = head; i != NULL; i = i->next){
操作;
}
头插法：
Node* u = new Node(4);
u->next = head;
head = u;
链表删除一个节点：跳过对应节点
*(指向待删除节点的指针) = *(指向待删除节点的指针->next);
//等价于：
指向待删除节点的指针->next = 指向待删除节点的指针->next->next;
指向待删除节点的指针->next = 指向待删除节点的指针->next->val;
技巧————虚拟头结点dummy
设置一个虚拟头结点dummy，返回时返回dummy->next
链表空节点(空指针)三种写法：0, NULL, nullptr
39. 图论题一般用数组模拟链表
因为算法竞赛中情景比较特殊，一般需要在1s之内运行通过
图论题中如果有许多点，如果使用struct的话，每次生成一个新节点时，会new一个struct，new的运行时间很慢，且运行时间与调用次数相关（与new的长度的关系没有与调用次数关系大）
比如一个有2*10^5个点的图论题，也就是一共要new2*10^5次，绝对会超时，但是在工程应用上一般来说不会1s之内有这么多访问量
所以一般来说工程应用上使用struct模拟链表，算法竞赛尤其图论题中使用数组模拟链表，就算使用动态数组new一个很长的数组也是只new一次，不会消耗很长时间
40. %s对应的是c风格字符串，string字符串直接用这种方式会乱码，需要用string类的成员函数c_str()，将其转换为c风格字符串，才能正常用printf输出。
41. 定义&别名用法
类型定义别名：
#define long long LL //宏定义 不需要加分号 没有类型检查 没有正确性检查 直接简单粗暴替换
using LL=long long; //在C++11中可以用using 为变量指定别名。
typedef long long LL; //有类型检查，是关键字，在编译时处理，有类型检查功能。它在自己的作用域内给一个已经存在的类型一个别名，但不能在一个函数定义里面使用typedef。
定义常量：
#define pi 3.1415 //宏定义 简单粗暴的文本替换 预处理阶段 没有检查和编译
const int pi = 3.1415; //c++常用 分配空间
宏发生在预处理阶段，属于直接替换，没有分配内存空间，const分配空间；宏没有类型检查，而且不能调试，所以c++中常用const替换。
typedef注意事项：
- typedef可以声明各种类型名，但不能用来定义变量。
- 用typedef只是对已经存在的类型增加一个类型名，而没有创造新的类型。
- 在不同源文件中用到同一类型数据时， 常用typedef声明一些数据类型，把它们单独放在一个头文件中，然后在需要用到它们的文件中用＃include命令把它们包含进来，以提高编程效率。
- 使用typedef有利于程序的通用与移植。
宏定义：
1.基本用法：
#define PI 3.1415926 // 定义一些常量
#define LOG(...) printf(__VA_ARGS__) // 函数取别名
#define max(a, b) (a) > (b) ? (a) : (b) // 进行简单运算
LOG("你好，%s\n", "谢老板不用蟹");
printf("max(10, 8) = %d\n", max(10, 8));
output:
你好，谢老板不用蟹
max(10, 8) = 10
2.封装多行代码（在一行的结尾处加上反斜杠符号 \ 即可
#define PRINT \
{ \
printf("define 1\n"); \
printf("define 2\n"); \
printf("define 3\n"); \
}
PRINT;
output:
define 1
define 2
define 3
42. 判断奇数不要用 n%2==1 ，要使用 n%2!=0 ，因为负数%2不是1，还是用不等于0判断保险
43. 方形二维数组 i表示行号 j表示列号 n表示规模(边长)
右上半部分(右上三角不含主对角线) i<j
左上半部分(左上三角不含次对角线) i+j<n-1
主对角线(四声) i=j
次对角线(二声) i+j=n-1
左下半部分(左下三角不含主对角线) i>j
右下半部分(右下三角不含次对角线) i+j>n-1
两条对角线分出的四个区域 上面的对应条件的交集&&
44. 阶乘、排列数、组合数、逆元、快速幂、费马、卢卡斯、质因数分解、杨辉三角相关（待补充）
求组合数——数学知识（c++） https://www.codetd.com/article/13112108
组合数计算四大算法模板(模板+卢卡斯定理)https://blog.csdn.net/yl_puyu/article/details/109451500
排列和组合问题以及子集生成问题https://zhuanlan.zhihu.com/p/555060019
求组合数（边乘边除，先乘后除）：
- 数据比较大时计算不能采用先乘完再除的做法，会溢出
- 采用的是边乘边除，这里的除法是可以整除的
- 原理是连续的2个数中一定有一个数能被2整除，
- 连续的3个数中一定有一个数能被3整除，以此类推
int C(int a,int b){
int res=1;
for(int i=1;i<=a;i++) res=res*(b-a+i)/i;
return res;
}
45. 全排列：
- dfs
- next_permutation函数：<algorithm>
将按字母表顺序生成给定序列的下一个较大的排列，直到整个序列为降序为止。
使用方法：next_permutation(数组头地址，数组尾地址);
若下一个排列存在，则返回真，如果不存在则返回假，新的排列将覆盖原排列的数据
若求上一个排列，则用prev_permutation
手写next_permutation()https://www.acwing.com/solution/content/25275/
46. 短路运算代替if语句
位运算代替乘除
AcWing84. 求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句 (A?B:C)。
https://www.acwing.com/activity/content/code/content/4526395/ （解法天秀）
47. 给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。（借尸还魂大法）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
*(node) = *(node->next);
//等价于：
//node->val = node->next->val;
//node->next = node->next->next;
//借尸还魂，将当前指针所指节点（当前节点）的值改为下一个节点的值，无需遍历寻找上一个节点（无需修改上一个节点的next指针），也就是不修改指针而直接修改值
}
};
48. 构造函数
类名 (参数列表 可缺省) {操作，如 成员变量1=参数1;}
构造函数三种写法：https://zhuanlan.zhihu.com/p/168787937
构造函数初始化列表：
类名 (参数列表 可缺省) : 成员变量1(参数1), 成员变量2(参数2),成员变量3(参数3) {操作 可有可无}
初始化列表可以用于全部成员变量，也可以只用于部分成员变量。
成员变量的初始化顺序与初始化列表中列出的变量的顺序无关，它只与成员变量在类中声明的顺序有关。
构造函数初始化列表还有一个很重要的作用，那就是初始化 const 成员变量。初始化 const 成员变量的唯一方法就是使用初始化列表。
class VLA{
private:
const int m_len;
int *m_arr;
public:
VLA(int len);
};
//必须使用初始化列表来初始化 m_len
VLA::VLA(int len): m_len(len){
m_arr = new int[len];
}
构造函数的调用是强制性的，一旦在类中定义了构造函数，那么创建对象时就一定要调用，不调用是错误的。
如果有多个重载的构造函数，那么创建对象时提供的实参必须和其中的一个构造函数匹配；
反过来说，创建对象时只有一个构造函数会被调用。
如果不定义就调用默认构造函数
一旦用户定义了任意的构造函数，不管定义了几个，定义成啥样，默认构造函数Student(){}当即失效，除非用户重新自定义一遍
以上两行应该是某种误解，真正理解请看https://blog.csdn.net/bear_n/article/details/72798301，但是先这么用着吧
构造函数必须是 public 属性的，否则创建对象时无法调用。
不管是声明还是定义，构造函数的函数名前面都不能出现返回值类型，即使是 void 也不允许；
构造函数的函数体中不能有 return 语句。
调用没有参数的构造函数也可以省略括号
49. 初始化
C++变量初始化形式及其默认初始值https://blog.csdn.net/qq_37766667/article/details/124258726
一维数组初始化：
1) 可以只给部分元素赋值。
当赋值的元素少于数组总体元素的时候，剩余的元素自动初始化为 0：
对于short、int、long，就是整数 0；
对于char，就是字符 '\0'；
对于float、double，就是小数 0.0。
我们可以通过下面的形式将数组的所有元素初始化为 0：
int nums[10] = {0};
char str[10] = {0};
float scores[10] = {0.0};
由于剩余的元素会自动初始化为 0，所以只需要给第 0 个元素赋值为 0 即可。
2) 只能给元素逐个赋值，不能给数组整体赋值。例如给 10 个元素全部赋值为 1，只能写作：
int a[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
而不能写作：
int a[10] = 1;
3) 如给全部元素赋值，那么在定义数组时可以不给出数组长度。例如：
int a[] = {1, 2, 3, 4, 5};
等价于
int a[5] = {1, 2, 3, 4, 5};
对于二维数组的初始化还要注意以下几点：
1) 可以只对部分元素赋值，未赋值的元素自动取“零”值。例如：
int a[3][3] = {{1}, {2}, {3}};
是对每一行的第一列元素赋值，未赋值的元素的值为 0。赋值后各元素的值为：
1 0 0
2 0 0
3 0 0
再如：
int a[3][3] = {{0,1}, {0,0,2}, {3}};
赋值后各元素的值为：
0 1 0
0 0 2
3 0 0
2) 如果对全部元素赋值，那么第一维的长度可以不给出。例如：
int a[3][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
可以写为：
int a[][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
3) 二维数组可以看作是由一维数组嵌套而成的；如果一个数组的每个元素又是一个数组，那么它就是二维数组。当然，前提是各个元素的类型必须相同。根据这样的分析，一个二维数组也可以分解为多个一维数组，C语言允许这种分解。
例如，二维数组a[3][4]可分解为三个一维数组，它们的数组名分别为 a[0]、a[1]、a[2]。
这三个一维数组可以直接拿来使用。这三个一维数组都有 4 个元素，比如，一维数组 a[0] 的元素为 a[0][0]、a[0][1]、a[0][2]、a[0][3]。
50. new delete
在C语言中，动态分配内存用 malloc() 函数，释放内存用 free() 函数。如下所示：
int *p = (int*) malloc( sizeof(int) * 10 ); //分配10个int型的内存空间
free(p); //释放内存
在C++中，这两个函数仍然可以使用，但是C++又新增了两个关键字，new 和 delete：new 用来动态分配内存，delete 用来释放内存。
用 new 和 delete 分配内存更加简单：
int *p = new int; //分配1个int型的内存空间
delete p; //释放内存
new 操作符会根据后面的数据类型来推断所需空间的大小。
如果希望分配一组连续的数据，可以使用 new[]：
int *p = new int[10]; //分配10个int型的内存空间
delete[] p;
用 new[] 分配的内存需要用 delete[] 释放，它们是一一对应的。
和 malloc() 一样，new 也是在堆区分配内存，必须手动释放，否则只能等到程序运行结束由操作系统回收。
为了避免内存泄露，通常new和delete、new[]和delete[]操作符应该成对出现，并且不要和C语言中malloc()、free()一起混用。
在C++中建议使用new和delete来管理内存，它们可以使用C++的一些新特性，最明显的是可以自动调用构造函数和析构函数
51. 类、结构体
class 默认private
struct 默认public
class 类名{
public：
成员变量；
成员函数；
private:
成员变量；
成员函数；
public:
成员变量；
成员函数；
}可选 直接生成一个对象a，一个对象指针*p，一个对象数组arr[100];
定义类/结构体时，可以在内部定义一个同名类型指针，但不能定义同名类型变量
52. 默认参数 / 缺省值
在C++中，定义函数时可以给形参指定一个默认的值，这样调用函数时如果没有给这个形参赋值（没有对应的实参），那么就使用这个默认的值。
也就是说，调用函数时可以省略有默认值的参数。如果用户指定了参数的值，那么就使用用户指定的值，否则使用参数的默认值。
所谓默认参数，指的是当函数调用中省略了实参时自动使用的一个值，这个值就是给形参指定的默认值。
C++规定，默认参数只能放在形参列表的最后，而且一旦为某个形参指定了默认值，那么它后面的所有形参都必须有默认值。实参和形参的传值是从左到右依次匹配的，默认参数的连续性是保证正确传参的前提。
53. 位运算
-x == ～x+1（-x的补码是x的补码取反+1）
lowbit(x) = x & -x （返回x的最后一位1及其后面所有的0，相当于返回最右边的1对应的值）(非库函数)
求x的第k位数字（位数从0编号）： x >> k & 1
& 全1则1，否则为0 与AND
| 全0则0，否则为1 或OR
~ 所有位取反 非NOT
^ 相同则0，不同则1 异或XOR
>> 消除最右位 除 右移
<< 在最右位补0 乘 左移
54. WA的时候看看有没有数据过大没开long long，记得检查一下所有的if和for和while的判断条件有没有写反/写错/写超/写少，循环变量有没有写冲突，有没有其他变量和循环变量冲突了
TLE看看有没有死循环
Segmentation Fault段错误先检查一下有没有遗漏某些输入，以及检查一下循环的边界条件有没有超限，然后看看有没有数组越界、空指针、野指针、数组过大、是否已经初始化等等，具体可参照 https://www.cnblogs.com/linux-37ge/p/12781176.html 和 https://www.cnblogs.com/wpgraceii/p/10622582.html
55. 关于用vector容器存储struct结构体数据：可以用下标访问，也可以用迭代器访问：当vector存储结构体变量时，可以用下标.成员变量访问 `v[i].member` ，此时v\[i\]存储的是结构体变量，也直接使用迭代器->访问成员变量 `it->member`,此时it的值是结构体变量的地址，相当于结构体变量的指针，可以直接使用->访问成员变量；当vector存储结构体指针变量时，可以用下标->成员变量访问 `v[i]->member`，此时v\[i\]存储的是结构体指针变量 ，如果使用迭代器需要先对迭代器it解引用，然后再用->访问成员变量 `(*it)->member`，此时it的值是结构体指针变量的地址，相当于结构体变量的指针的指针，需要先对其进行一步解引用，变成结构体指针变量之后，才能使用->访问成员变量
56. 数组和结构体初始化：可以在一行里进行初始化（声明，定义，一步完成），但不可以在两行里完成（声明了，然后在后来某处，通过花括号赋值， not ok）
57. 结构体初始化可以采用{成员变量1初始值,成员变量2初始值,……}聚合体按照成员变量声明顺序初始化、构造函数初始化，不依赖顺序的指定初始化{.成员变量=初始值or成员变量:初始值}，初始值可以是某变量
58. 对vector增加元素一定要记得使用push_back()，不要使用下标，会导致指针越界程序崩溃
59. 利用scanf读入单个字符时，为了避免读入莫名其妙的空格回车，可以先定义一个大小为2的char数组，然后使用%s占位符将这一单个字符读入数组，最后取数组第一个元素使用
例如：
char op[2];
int n, m;
scanf("%s",op);
输入：M 123 456
存储结果：op[0]='M' n=123 m=456
60. 输入数据超过100万时才会用scanf，否则和cin差别不大
61. 出现TLE或者SF（Segment Fault）就使用删代码法判断哪个位置出错（来源算法基础课三（二）02:11:00左右）
62. 数组越界之后，什么错误都可能发生，不只是SF、TLE
63. 边界问题：如果过程中涉及到了i-1的下标，那么下标一般从1开始，这样可以少一层判断，也可以少一些越界风险
64. 区间内整数下标数量：以区间(i,j)为例，i,j为整数
如果下标包含边界i,j: j-i+1
如果只包含一边的边界： j-i
如果两个边界都不包含： j-i-1
65. 使用cin>>读入到char[]数组 或 string：读入一个字符串，以空白字符结尾，并忽略该空白字符
例： char op1[10];
cin>>op1; //输入"pageup and pagedown"
cout<<op1; //输出"pageup"
string op2;
cin>>op2; //输入"pageup and pagedown"
cout<<op2; //输出"pageup"
参见：https://blog.csdn.net/Flag_ing/article/details/125209588
66. 条件表达式（三目运算符?:）结合性问题
三元条件操作符?: 右结合性只是说明`int n = ++i == 0 ? 99 : (i == -1 ? 11 : 22);`这个表达式等价于
`int n = ++i == 0 ? 99 : (i == -1 ? 11 : 22);`
而不是
`int n = (++i == 0 ? 99 : i == -1) ? 11 : 22;`
结合性仅仅是定义了多个相同优先级的运算符和与之相关的操作数（操作符）的结合顺序，而并没有规定相同优先级的运算符之间哪个子表达式先运行。
换一种说法，结合性和优先级只是定义表达式的结构，当确定表达式运行时的行为时才需要表达式各部分的运算顺序。
C语言对于条件表达式（三目运算符）的运算顺序规定为：条件表达式首先对条件部分求值，若条件部分为真，则对问号之后冒号之前的部分求值，并将求得的结果作为整个表达式的结果值，否则对冒号之后的部分求值并作为结果值。
所以`int n = ++i == 0 ? 99 : (i == -1 ? 11 : 22);`这个表达式应该理解为
表达式：`int n =( (++i == 0) ? 99 : ((i == -1) ? 11 : 22));`
运算顺序：先运行第一个?:，如果(++i == 0)为真取99，否则运行第二个?:
(https://blog.csdn.net/steedhorse/article/details/5903974)
(https://blog.csdn.net/geekdonie/article/details/17173735)
STL模板
https://www.acwing.com/blog/content/404/
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
s=to_string(data); 将其他类型数据转化为string
insert()
erase()
replace()
swap()
push_back()
pop_back()
find() 返回找到的字符串的下标，返回类型是unsigned int，如果没查到返回unsigned int的最大值string::npos，转成int就是-1
copy()
compare()
等等
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
定义大根堆priority_queue<int> a;
//等同于 priority_queue<int, vector<int>, less<int> > a;
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 压位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
