公开课-语法部分
1.语句和字符串
在c/c++中，一个语句一般是以分号结尾。
语句有以下几种：
①表达式语句：
作用大多数为给变量赋值。
a=3;
b/=2;
②函数调用语句
作用为调用函数。函数可以是库函数，也可以是自己定义的函数。
printf(“123”); //库函数，作用为打印字符串
dfs(1,-1); //自己定义的函数

③控制语句
条件：if(a<b)....
循环：while(t--)....
转向：break;
④复合语句
a=1,b=2; //用逗号隔开的语句为复合语句
while(x<3){x++;printf(“%d\n”,&x);} //大括号里为复合语句

⑤空语句
for(i=n-1;a[i]==0;i--); //这里的分号即为空语句，代表for循环中什么也没有执行。

2.顺序、选择、循环三种结构
顺序结构：
语句;

例如：
//交换a和b的值
t=a;
a=b;
b=t;

选择结构：
if(判断条件){
语句;
}
例如：
//维护最大值
if(max<a[i])max=a[i];

循环结构：
while(判断条件){
语句;
}
例如：
//将x转为二进制存入数组
while(x>0){
a[cnt++]=x/2;
x%=2;
}

3.变量、数组和结构体
变量为可以变化的量。例如：
int x; //整形变量
string str; //字符串变量
注意：在java中变量分为基础型和引用型两种。引用型变量类似c/c++中的指针，调用函数可以保留在函数中改变的值。而基础型则不可以。

多个同类型变量列为一个表，称为数组。例如：
double a[100]; //定义一个100个double型变量组成的数组，从a[0]到a[99]。

请注意，数组定义的下标是从0到n-1的，如果定义的a[n]那么没有a[n]这个变量，只有a[0]到a[n-1]。

结构体是自己定义的变量类型。结构体也可以开数组，或者结构体中使用结构体。例如：
struct node{
char c;
int cnt;
node *child[36]; //这里是指针，相当于java中的引用型变量。
};

4.函数和递归
函数为一些语句的集合，可以调用函数来执行这些语句。 函数有两种，带返回值的和无返回值的。 例如：
int add(int a,int b){ //求a和b之和
return a+b;
}
无返回值的大多数用于对全局变量进行操作，例如：
int visited[1010]=0;
void dfs(int x){ //深度优先搜索，遍历x的所有连通点。
visited[x]=1;
for(int i=0;i<g[x].size();i++){
if(!visited[g[x][i]]){
dfs(g[x][i]);
}
}
}

函数也是必须先声明再使用，所以我们一般把函数写在main函数的上面。
递归指函数调用自己。例如求斐波那契数列可以用如下函数：
int f(int n){ //第0项和第1项是1的斐波那契数列，求第n项
if(n<2)return 1;
return f(n-1)+f(n-2);
}
不过我们一般不会使用这个方法去求斐波那契数列，因为它的复杂度是O(2n)。大多数情况下使用启发式搜索或者递推的方式来求。

请务必注意函数变量的作用范围！如果函数使用了和全局变量同名的变量，那么全局变量将在函数里没有任何作用。所以尽量避免同名变量的定义。
函数可以作用到的有：
1.函数内部的变量。
2.函数上方的全局变量
函数作用不到的有：
1.其他函数的非全局变量。
2.函数下方的全局变量（这种情况一般都会报错，除非函数内部定义了一个同名局部变量）。

公开课-stl部分
1.pair
二元组。可以看成是如下定义：
struct pair{
int first,second;
};
一般pair型变量定义的方式是：
pair<int,int>p;
pair<double,double>a[222];
pair数组默认排序的依据是：优先按first升序进行排序。若first相等则按second升序进行排序。
2.vector
可变长度的数组。
主要用法如下：
vector<int>a; //vector的定义
a.push_back(x); //在a的最后新增一个数x
a[i]; //调用a的下标i对应的数
sort(a.begin(),a.end()); //对a数组（升序）排序</int>

重点！！！
使用vector建图的技巧：
要求：
第一行输入n和m，代表点数 和边数。 接下来的m行，每行输入两个数x和y，代表x和y有一条无向（有向）边
【样例输入】
4 5
1 2
2 3
4 2
1 4
3 4
建图的代码（请务必理解记忆，如果不能理解那么就当模板记下来）：
vector<int>a[100010]; //建议vector数组开大点
int n,m;
cin>>n>>m; //n代表顶点数量，m代表边数量
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x); //如果是有向边，该行省略
}</int>

3.stack/queue/ deque/priority_queue
stack，即栈。
stack<int>s; //栈的定义
s.push(x); //将x压入栈顶
int tp=s.top(); //拿到栈顶元素（但不出栈）
s.pop(); //栈顶元素出栈
s.empty(); //返回一个bool型，若栈为空返回ture，否则返回false</int>

queue，即队列。
queue<int>s; //队列的定义
s.push(x); //x入队
int tp=s.front(); //拿到队首元素（即将出队的元素），但不出队
s.pop(); //队首出队</int>

deque，即双端队列，也叫双向队列。deque的功能包含了栈和队列的功能，强烈建议大家掌握并熟练使用。
deque<int>s;
s.push_back(x); //队列末尾插入x
s.push_front(x); //队列开头插入x
s.pop_back(); //队列末尾弹出
s.pop_front(); //队列开头弹出
int ed=s.back(); //获取队列末尾的值，但不弹出
int op=s.front(); //获取队列开头的值，但不弹出</int>

priority_queue，即优先队列。作用和最大（小）堆一样，可以O(logn) 复杂度插入一个数/弹出一个当前所有数最大（小）值

priority<int>q; //优先队列的定义
priority_queue<int,vector<int>,greater<int>>q; //弹出最小值的优先队列的定义
q.push(x); //x压入优先队列
int max=q.top(); //返回最大值，但不弹出
q.pop(); //弹出最大值</int></int></int>

结构体优先队列的使用：
两种方法：
1.重载小于号
struct node{
//...
bool operator<(const node& a)const{...}
};
priority<node>q;</node>

2.重写仿函数
struct node{
//结构体
};
struct cmp{
bool operator()(node a,node b){...}
};
priority<node,vector<node>,cmp>q;</node>

第一种方法适用于只需要一种优先队列。 如果需要多种优先队列，则用第二种方法（可以用多种cmp定义不同的优先队列）。

4.set/multiset
set:集合。每种元素最多出现一次。可以O(logn) 插入/删除/查询。
set<int>s; //定义一个set
s.insert(1); //往set里添加一个1
s.erase(1); //将set里的1删除
if(s.count(x)).... //判断set里是否有x。由于set无重复，所以count的值只有可能1或0</int>

set:集合。每种元素最多出现不限次数。可以O(logn) 插入/删除/查询。
set<int>s; //定义一个set
s.insert(1); //往set里添加一个1
s.erase(1); //将set里的1删除
if(s.count(x)).... //判断set里是否有x。由于set无重复，所以count的值只有可能1或0</int>

5.map
map提供一对一的哈希。map的调用/赋值均为O(logn) 复杂度。
map<int,int>m; //前一个为key，后一个为value。
m[1]=2; //将键值为1的value赋值为2。
m[99999999]=3; //将键值为99999999的value赋值为3

6.迭代器
迭代器有多种用法：容器的遍历，二分等
set的遍历：
set<int>s;
for(set<int>::iterator it = s.begin();it!=s.end();it++){
cout<<(it);
}
map的遍历：
map<string,char>m;
for(map<string,char>::iterator it = m.begin();it!=m.end();it++){
cout<<(it).first<<endl; //输出key
cout<<(*it).second<<endl; //输出value
}</int></int>

第一章贪心和枚举
1.1 贪心
贪心指每一步都做出当前最优的选择。一般解决的问题有如下特点：局部最优能导致全局最优。
典型的贪心问题：
1.纸币面额有1元、2元、10元、100元。问凑出正好x元最少要多少张纸币。
【思路】
显然是尽量取面额大的，因为有整除关系，多张面额小的一定可以被一张面额大的代替。
（如果没有整除关系怎么办？）
2.纸币面额有a[1]元，a[2]元......a[n]元。问至少凑出x元最少需要多少张纸币？（或者问，x张纸币最多可以凑多少元）
【思路】
显然的贪心算法。每次尽量取面额大的即可。

1.2 枚举
1.2.1 朴素枚举
传统的for循环（嵌套）。一般考察知识点的题目用枚举也可以获得部分分。
例如：《夹缝中求和》（来源牛客IOI周赛普及组20-D）
https://ac.nowcoder.com/acm/contest/8997/D

给定一个数组a，以及两个正整数x 和y ，求取两个数 ai和 aj （i<j），满足x≤ai+aj≤y的取法有多少种？
注：只要两个取法有一个角标不同，则视为两种不同的取法。
数据范围：1≤len(a)≤100000

这道题是考察双指针O(n)的知识点，但如果在笔试中遇到了这种题没思路，不妨写一个O(n2)的枚举算法。这样也能拿到部分分。
关键代码如下：
int cnt=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++{
if(a[i]+a[i]>=x&&a[i]+a[j]<=y)cnt++;
}
}
1.2.2状压枚举
这类题的典型模型：一共有n个物品，选择部分物品能否达成某个条件。
如果n的范围不超过20，那么则可以使用状压枚举达成O(n2n)解决问题。
状压枚举的核心思想如下：
假设每个物品被选择记为1，没有被选择记为0，那么n个物品则构成了一个长度为n的、仅有0或1组成的字符串，或者看成是一个不大于2n的二进制数。于是我们可以反过来通过枚举二进制数来枚举所有状态。
下面为求取出部分数之和的关键代码：
for(int i=0;i<1<<n;i++){ //i为1到2n的状态压缩值
int p=i; //先将i取出
int sum=0; //用一个变量维护取出的数之和
for(j=0;j<n;j++){ //转为二进制进行操作
sum+=p%2a[i]; //这句话是求取出来的数之和。p%2为对应二进制位
//这里也可以进行其他操作，不一一举例。
p/=2; //求下一个二进制位
}
//这里可以添加想要的操作。
}

第二章递归：搜索算法和分治算法
2.1深度优先搜索
深度优先搜索，一般指通过递归达成“不撞南墙不回头”的搜索。
一般可以用来解决连通块问题、树形dp问题、或者搜索一些状压枚举解决不了的问题。
这里介绍两类深度优先搜索遍历图的代码：
vector<int>g[100010]; //已经存好的图。图的vector存储方式见stl篇
void dfs(int x,int pr){ //无根树的遍历。x指遍历到的节点，pr指上一个节点。
int i;
for(i=0;i<g[x].size();i++){
if(g[x][i]!=pr){
dfs(g[x][i],x);
//你要进行的操作。
}
}
//也可以有返回值，适用树形dp。
}</int>

vector<int>g[100010]; //已经存好的图。图的vector存储方式见stl篇
int visited[100010];
void dfs(int x,int pr){ //无向图的遍历。x指遍历到的节点。
int i;
visited[x]=1;
for(i=0;i<g[x].size();i++){
if(!visited[g[x][i]]){
dfs(g[x][i],x);
//你要进行的操作。
}
}
}</int>

2.2启发式搜索
利用已经搜索到的结果直接剪枝，这样避免重复搜索，大幅提高搜索的速度。
记录是否被搜索过可以用int型数组或者map（map复杂度高一些，但可以离散化记忆）。
还记得最开始提到的斐波那契数列吗？使用启发式搜素即可将普通的递归由O(2n)变成O(n)：

int feb[100];
int f(int n){ //第0项和第1项是1的斐波那契数列，求第n项
if(feb[n])return feb[n]; //关键！！如果已经搜索过了那么直接返回。
if(n<2)return 1;
return feb[n]=f(n-1)+f(n-2); //将没有搜索过的进行赋值
}

第三章栈和队列&搜索算法（bfs）
3.1 栈
栈，即后进先出的线性数据结构。笔试题中可以直接调用stl中的stack。
可以用栈解决的问题：括号匹配问题、表达式求值问题等。
3.2 队列
队列，即先进先出的线性数据结构。笔试题中可以直接调用stl中的queue。
队列最典型的应用：广度优先搜索（bfs）
3.3 广度优先搜索
类似二叉树的层序遍历。一般用来解决单源或多源最短路问题，也可以解决连通块问题（这点同dfs，但dfs解决不了最短路）
图的bfs代码示例：
vector<int>g[100010]; //已经存好的图。
int visited[100010]; //标记数组，用来防止重复遍历
queue<int>q;
q.push(x); //x为搜索的起点。
visited[x]=1;
while(q.empty()){
int temp=q.front(); //当前搜索到的节点
q.pop();
for(int i=0;i<g[temp].size();i++){
if(!visited[g[temp][i]]){
//你要进行的操作
q.push(g[temp][i]);
visited[g[temp][i]]=1;
}
}
}</int></int>

第四章动态规划
4.1线性dp
还记得斐波那契数列吗？（是的，我又回来了）
可以用数组来记录前面斐波那契数列的值，以此推出后面的值。
feb[0]=feb[1]=1;
for(int i=2;i<=n;i++){
feb[i]=feb[i-1]+feb[i-2];
}
这即是动态规划的思想：利用已有的结果以及递推方程来推出整体结果。

还有一种变种的线性dp，当数组中某个数选或不选对后面的结果都有影响时，那么可以把选或不选作为两种状态：
例如：求数组中取一些数要求取的数不能出现相邻，求取的数之和的最大值：
int dp[200020][2]; //dp[i][0]代表不取第i个数的最大值，dp[i][1]则代表取其的最大值
for(int i=1;i<=n;i++){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]); //若不取a[i]，那么前一个数取不取都可以
dp[i][1]=dp[i-1][0]+a[i]; //取a[i]必须要求前一个数不能取
}
cout<<max(dp[n][0],dp[n][1]); //最后要返回的是取/不取最后一个数-这两种情况
//的最大值
4.2二维dp
和线性dp比，二维dp多了一维。一般而言，维数的增加可以用来更方便对问题进行描述，但同时也会增加算法的复杂度。
在复杂的dp问题中，一定要明确化每个下标代表什么，需要的时候可以借助注释避免思路乱掉。
4.3背包问题
背包问题的模型特别多，这里介绍两个常见的模型：
1.n个物品，每个物品有重量a[i]和价值b[i]，背包限制总重量w，问放入背包的物品价值最大值多少？要求复杂度O(nw)
简要思路：
设dp[i][j]代表前i个物品中，取总重量为j的物品的价值最大值。
那么有方程：dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+b[i])
解释如下：如果取第i个物品，那么“前i个物品中，取总重量为j的物品”这个状态一定是从“前i-1个物品中，取总重量为j-a[i]的物品”这个状态再取第i个物品达成的。
2.n个物品，每个物品重量a[i]。问能否取部分物品达成总重量正好为w？要求复杂度O(nw)
这道题如果n的范围是20，那么可以直接用状压枚举来解决。但是如果n比较大呢？比如n是100，w是1000的情况。
我们不妨设dp[i]代表重量i能被选到。那么由前i-1个物品能选到的所有情况显然可以直接推出第i个物品的。参考代码如下：
int dp[1010]={1}; //总重量为0默认可以选到，即什么都不选的情况
for(int i=0;i<n;i++){
for(int j=w;j>=0;j--){ //之所以倒序遍历，是为了防止同一个物品被选用多次。
if(dp[j]&&j+a[i]<=w)
dp[j+a[i]]=1; //如果前面能选到j，那么再选第i个物品就能选到j+a[i]
}
}
if(dp[w])cout<<”yes”;
第五章二分/双指针
5.1 二分
二分用于在一个已经排好序的数组里查询某个数/查询第一个大于（不小于）某数的数。
5.1.1 非递归实现
int l=1,r=n,x;
while(l<r){
int mid=l+r>>1; //l和r的平均数（向下取整），等价于(l+r)/2
if(a[mid]<x)l=mid+1; //这里可以根据需求换成小于等于，或者check(mid)，即任意//写的check函数
else r=mid;
}
//搜索完l即为寻找的地方

5.1.1 递归实现
int bs(int l,int r,int x){
int mid=l+r>>1;
if(a[mid]<x)return bs(mid+1,r,x); //注意这里的a数组必须是全局变量。
//同样可以根据需求修改mid里的内容
return bs(l,mid,x);
}
5.2 双指针
双指针指两个变量同时从左遍历到右，看似两个循环嵌套实际上复杂度只有O(n)。
典型例题：
数组中n个数，取出最大值减最小值不超过k的一些数，最多能取多少个？
思路：先将数组排序，然后双指针进行遍历。
关键代码如下：

int i,j=0,ma=0; //用ma维护区间长度的最大值
sort(a,a+n);
for(i=0;i<n;i++){
while(j<n){
if(a[j]-a[j]<=k)ma=max(ma,j-i+1);
else break;
j++;
}
}

第六章简单组合数学&简单数论
6.1分解质因数/判断素数/求因子和/求因子数量
对于任意的正整数而言，其因子一定是两两成对的：若p是x的因子，x/p也一定是x的因子。
所以以上的问题有个共同的解法：O(√x)遍历所有不大于√x的的因子即可。
要注意x的完全平方数的特判。
下面给出求因子和的关键代码：
int i,sum=0;
for(i=1;ii<x;i++){
if(x%i==0)sum+=i+x/i; //既计算了因子i，也计算了因子x/i
}
if(ii==x)sum+=i; //特判完全平方数

6.2欧拉筛
如何快速得到1到n的所有素数？
可以这样快速筛出来：先将所有2的倍数标记为合数，然后把所有3的倍数标记为合数，然后遇到4，刚刚在2的时候就被标记了，跳过；接下来把所有5的倍数标记为合数……
最终所有没被标记的就是素数了。复杂度为O(nlogn)。
还有一种更优秀的筛法：
对于每个数x，对所有小于x的素数p而言，将x*p筛掉。遇到x%p===0则直接跳出。可以证明，每个合数一定会被这种筛法筛一次（假设x的最小因子是p，那么在筛x/p这个数的时候，筛到p的时候就会跳出，这样正好筛到了x），且一定只被筛了一次。所以这个是线性复杂度的，复杂度为O(n)。
线性筛的模板如下：（不强求记，如果能记住原理更好）

void shai()
{
tot=0;
for(int i=2;i<n;i++)
{
//如果未标记则得到一个素数
if(!vis[i])
{
prime[tot++]=i; //将素数保存在prime数组里
}
for(int j=0;j<tot&&prime[j]i<n;j++)
{
vis[iprime[j]]=1;
if(i%prime[j]==0)
{
break;
}
}
}
}

6.3组合数
n个数里取m个数的组合方案数，记为 或者C(n,m)
其公式为
所以用定义求组合数的方式是：
int C(int n,int m){ //大组合数的情况建议把int写成long long，范围更大
int res=1;
for(int i=1;i<=m;i++){
res*=(n-i+1);
res/=i; //如果是大组合数取模，这里的取法要写成乘以逆元。
}
}

第七章常用模板
7.1 快速幂
利用公式，可以直接用底数平方、指数除以2的方式，这样指数降到0只需要log(n)次，因此复杂度仅需O(logn)，比朴素的模拟乘方法的O(n)要优秀很多。
模板如下：
long long power(long long a,long long b,int mod) { //计算a的b次方对mod取模的值
long long res=1;
while(b){
if(b&1)res=resa%mod; //判断b为奇数，等价于b%2==1
b>>=1; //b的二进制右移一位，等价于b/=2
a=aa%mod;
}
return res;
}

7.2 逆元
根据费马小定理，若a和p互素，那么ap-2和a互为逆元。逆元的作用是，模p意义下，除以p和乘以p的逆元是等价的。
求逆元直接调用快速幂即可：
long long inv(long long x,int mod){ //求x的逆元（模mod意义下）
return power(x,mod-2,mod);
}
以上两个模板mod可以写在全局变量里，这样函数就可以少一个参数。
有了逆元以后，组合数的模板就可以改写成这样：
long long C(long long n,long long m,int p){ //计算C(n,m)模p的值
int res=1;
for(int i=1;i<=m;i++){
res=res(n-i+1)%p;
res=resinv(i,p)%p; //除以i，等价于乘以i的逆元
}
}

7.3 gcd/lcm
gcd即最大公约数，可以调用库函数__gcd(x,y)来求（注意有两个下划线），也可以用以下辗转相除法的模板：
long long gcd(long long a,long long b){
return a%b==0?b:gcd(b,a%b);
//这句话等价于 if(a%b==0)return b;
// return a%b;
}

lcm即最小公倍数，可以直接通过gcd求出：
long long lcm(long long a,long long b){
return a/gcd(a,b)b; //最好写成这样，如果写成ab/gcd(a,b)可能导致范围溢出
}

7.4 并查集
并查集为一个树形结构，可以做到O(logn)合并两个集合，O(logn)查询两个数是否在同一个集合。
并查集的模板如下：
int fa[100010];
void init(){ //并查集的初始化
for(int i=1;i<=n;i++)fa[i]=i;
}
int f(int x){ //查询x的祖先，并启发式合并
return fa[x]==x?x:fa[x]=f(fa[x]);
}
void uni(int x,int y){ //将x和y所在集合合并
int p=f(x),q=f(y);
fa[p]=q;
}