我的主页

图灵

洛谷

普及组笔记**:**

目录:

1. 递归
2. 深搜
3. 广搜
4. 链表

递归**:**

定义：

函数的自我调用。

思路：

在n个相同连续的小问题中，能用函数解决当前问题，就用此函数解决上一个问题、下一个问题。

例题：

1、倒序输出10以内的自然数

2、递归求等差数列

3、递归求等比数列

深搜（​dfs​）：

思路：

不断向下进行搜索，直到不满足条件时，返回上一层。

Code：

#include <bits/stdc++.h>

using namespace std;

void dfs(参数){

** **if(终止条件){

** **return ;

** **}

** **执行语句

** **dfs(参数);

}

int main(){

** **dfs(参数);

** **return 0;

}

例题**:**

1.[NOIP2002 普及组] 产生数]

2.八皇后 Checker Challenge

3.kkksc03考前临时抱佛脚

广搜（​bfs​）：

思路：

将当前位置可达到的所有位置入栈，并遍历栈。

Code：

#include <bits/stdc++.h>

using namespace std;

struct Node{

** **int pos,cnt;

};

queue q;

void bfs(int pos,int cnt){

** **Node h,t;

** **t={pos,cnt};

** **q.push(t);

** **while(!q.empty()){

** **h=q.top();

** **q.pop();

** **pos=h.pos;

** **cnt=h.cnt;

** **for(int i=1;i<=4;i++){

** **npos=……;

** **ncnt=……;

** **if(满足条件){

** **cout<<npos<<" "<<ncnt<<endl;

** **return ;

** **}

** **if(入栈条件){

** **q.push(npos,ncnt);

** **}

** **}

** **}

}

int main(){

** **bfs(pos,cnt);

** **return 0;

}

例题：

1.细胞数量

2.填涂颜色

3.Lake Counting S

二分：

定义：

顾名思义，每次取中间的那个值。

​Code​：

bool check(int x){

** **return 条件;

}

int main(){

** **while(l<=r){

** **int mid=l+r>>1;

** **if(check(mid)){

** **cout<<mid;

** **break;

** **}

** **}

}

链表**:**

特点**:**

插入、删除速度快，O(1)。 访问速度慢，O(n);

插入：

在i后面插入x。

Code:

单向链表**:**

struct Node{

** int nxt; **

};

lst[x].nxt=lst[i].nxt;

lst[i].nxt=x;

双向链表：

struct Node{

** int nxt,pre; **

};

lst[x].nxt=lst[i].nxt;

lst[lst[i].nxt].pre=x;

lst[lst[lst[i].nxt].pre].pre=i;

lst[i].nxt=x;

删除：

在将i后面的x删掉。

单向链表：

struct Node{

** int nxt; **

};

lst[i].nxt=lst[lst[i].nxt].x=nxt;

双向链表：

struct Node{

** int nxt,pre; **

};

lst[lst[lst[i].nxt].nxt].pre=i;

lst[i].nxt=lst[lst[i].nxt].nxt;

例题：

1.单向链表

2.词链

3.[BJWC2014] 珠链

模拟：

例题：

1.聊天流量

2.数轴旅游

3.渣朱君的反向前缀和

lambda函数**:**

定义**:**

函数里的函数。

Code:

int main(){

** **auto 函数名=[&] (参数){

** **执行语句;

** **};

}

增强for循环：

思路：

将数组中的每一个数都赋值给一个变量，并遍历这个变量。

​Code​：

for(auto i : 数组){

** **//将数组中的数赋值给i，并遍历

}

重载运算符：

思路：

重新定义运算符。

​Code​：

friend auto operator 符号 ( 变量1，变量2){

** **return 条件;

}

好题

• [USACO10OPEN] Time Travel S

https://i.loli.net/2018/05/23/5b0538cce7f77.jpg