蛇口水湾2026年寒假D03集训笔记
2026-02-11 13:50:50
发布于：广东
19阅读
0回复
0点赞
第一天：
bool is_prime(int x){
if(x < 2) return false;
for(int i = 2;i*i <= x;i++){
if(x % i == 0) return false;
}
return true;
}
DFS枚举-01枚举
01DFS---是一种处理每个元素有“选”或“不选”两种状态的递归算法
通过深度优先遍历所有可能的选择组合，枚举所有子集，
并根据问题目标（计数、最值、可行性等）统计或优化结果。
O(2^n)
优先考虑 01DFS：
1.元素数量少：n≤20
2.二元选择：每个元素仅有“选”或“不选”两种独立状态（无顺序依赖）
3.目标明确：需统计满足条件的子集数（计数）、求最优子集（最值）、判断是否存在可行子集（可行性）等。
01枚举模板：
#include<iostream>
using namespace std;
void check(){
//是否满足题目条件
}
void dfs(int now){
if(now == 结束条件){
check();//检查
return ;
}
//选取
vis[now] = 1;
dfs(now+1);
//不选取
vis[now] = 0;
dfs(now+1);
}
int main(){
dfs(1);//起点
return 0;
}
DFS枚举-排列枚举
- 多选择枚举：每阶段不止“选/不选”，而是有k(k≥2)种选择（如T76854每个位置选a/b/c，T76855每人选1~a[i]份）。
- 带约束枚举：选择需满足额外条件（如T76858八皇后“行列对角线唯一”）。
- 目标多样：输出所有合法方案（按字典序）、输出前m个解、统计解的总数等。
排列枚举模板：
#include<iostream>
using namespace std;
void check(){
//是否满足题目条件
}
void dfs(int now){
if(now == 结束条件){
check();//检查
return ;
}
for(int i = 1;i <= n;i++){
vis[now] = i;
dfs(now+1);
//vis[now] = 0;---回溯
}
}
int main(){
return 0;
}
第二天：
Meet in the middle 折半搜索
#include<bits/stdc++.h>
using namespace std;
//前半段 1~n/2
void dfs1(int now){
if(now == n/2+1){
check();
return ;
}
//01枚举
vis[now] = 1;
dfs1(now+1);
vis[now] = 0;
dfs1(now+1);
}
//后半段n/2+1~n
void dfs2(int now){
if(now == n+1){
check();
return ;
}
//01枚举
vis[now] = 1;
dfs2(now+1);
vis[now] = 0;
dfs2(now+1);
}
int main(){
//二分合并
//找第一个大于等于 查找值 的位置
lower_bound(数组名+起始索引,数组名+终止索引+1,查找值) - 数组名
//找第一个大于 查找值 的位置
upper_bound(数组名+起始索引,数组名+终止索引+1,查找值) - 数组名
sort() ;//排序
return 0;
}
DFS综合应用
第三天：
连通块&&深度优先搜索
方向数组 - DFS
#include<iostream>
using namespace std;
int dx[8] = {-1,1,0,0,-1,-1,1,1};
int dy[8] = {0,0,-1,1,-1,1,-1,1};
void dfs(int x,int y){
mp[x][y] = 被访问;
for(int i = 0;i < 8;i++){
int nx = x + dx[i];
int ny = y + dy[i];
//在边界范围内 能够走通 未被访问过
if(nx >= 1 && nx <= 行 && ny >= 1 && ny <= 列 && mp[nx][ny] != 障碍物 && !vis[nx][ny]){
dfs(nx,ny);
}
}
}
int main(){
//无向图、有向图
mp[u][v] = 1;
mp[u][v] = mp[v][u] = 1;
return 0;
}
邻接矩阵 - DFS
#include<iostream>
using namespace std;
vector<int> g[长度];
void dfs(int now){
vis[now] = 1;//被访问
for(int i = 0;i < g[now].size();i++){
int y = g[now][i];//now 的第 i 个邻居
if(!vis[y]) dfs(y);//未被访问过，继续放下搜索
}
}
int main(){
//无向图、有向图
g[u].push_back(v);
g[v].push_back(u);
return 0;
}
第四天：
BFS/DFS综合应用
第五天：
广度优先搜索---邻接表
map容器---字典：键值对
map<string,int>
#include<bits/stdc++.h>
using namespace std;
bool vis[210];//访问数组
int step[210];//步数数组
void bfs(int start){
queue<int> q;//1.创建队列
q.push(start);//2.起点入队
vis[start] = 1;//3.起点被访问
step[start] = 0; //4.起点步数为0
//循环取出队首
while(!q.empty()){//如果队列非空
int now = q.front();//取队首
q.pop();//删除队首
//是否到达终点
if(now == 终点){
cout<<step[now];//输出终点的距离
return ;
}
//遍历队首所有的邻居
for(auto y:g[now]){//邻接表
//int y = g[now][i];//新邻居
if(!vis[y] && 未超出边界){//邻居未被访问
vis[y] = 1;
step[y] = step[now] + 1;
q.push(y);//新邻居入队
}
}
}
cout<<-1;//无法到达 (根据题目要求调整)
}
int main(){
bfs(a);//从起点开始广搜
return 0;
}
第六天：
广度优先搜索---迷宫
迷宫问题BFS
#include<iostream>
using namespace std;
struct node{
int x,int y;
};
void bfs(int xx,int yy){
queue<node> q; //1.创建队列
q.push({xx,yy}); //2.起点入队
vis[xx][yy] = 1; //3.起点被访问
step[xx][yy] = 0; //4.起点步数为 0
while(!q.empty()){
node now = q.front();//取队首
q.pop(); //删除队首
//判定是否到达终点
if(now.x == fx && now.y == fy){
cout<<step[fx][fy];//输出终点的步数
return ; //结束广搜
}
//遍历所有的邻居
for(int i = 0;i < 8;i++){
int nx = now.x + dx[i];//新的行
int ny = now.y + dy[i];//新的列
//在边界范围内 未被访问过---不是障碍物
if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && !vis[nx][ny] && mp[nx][ny] != 障碍物){
q.push({nx,ny});
vis[nx][ny] = 1;//邻居被访问
step[nx][ny] = step[now.x][now.y] + 1;//邻居步数 +1
}
}
}
cout<<-1;//无法到达
}
int main(){
return 0;
}
多源最短路
第七天：
树的路径
树的深度
树的宽度：桶标记---记录每一层有多少个节点---找最多的那一层的个数
第八天：
树的子树大小
树的子树个数
#include<bits/stdc++.h>
using namespace std;
int n,u,v;
vector<int> g[200010];
int cnt[200010];//子树的节点数量
int dep[200010];//子树的节点深度
//pos-当前节点 fa-父节点
void dfs(int pos,int fa){
if(是否是叶子节点 但 不是根节点) cnt[pos] = 1;
dep[pos] = dep[fa] + 1;
for(auto son:g[pos]){
if(son == fa) continue;
dfs(son,pos);
cnt[pos] += cnt[son];
}
}
int main(){
cin>>n;
for(int i = 1;i <= 边数;i++){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
return 0;
}
第九天：
拓扑排序的模板
拓扑排序---判环
拓扑排序---反向建图
__int128 128位整数 10^38
#include<bits/stdc++.h>
using namespace std;
int n;
int inD[长度];
vector<int> g[长度];
vector<int> ans;//存放拓扑排序
void TopoSort(){
//1.创建队列
queue<int> q;
//2.入度为0 的点入队
for(int i = 1;i <= n;i++){
if(inD[i] == 0) q.push(i);
}
//3.循环队列
while(!q.empty()){
//4.取出队首并加入到拓扑排序的序列中
int u = q.front();
ans.push_back(u);//把取出的队首传给ans数组
q.pop();
//5.把队首的出边删除
for(auto v:g[u]){
//6.如果新出现入度为 0 的点，入队
if(--inD[v] == 0) q.push(v);
}
}
}
int main(){
cin>>n;
for(int i = 1;i <= 边数;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
inD[v]++;//边的终点入度 + 1
}
TopoSort();
return 0;
}
有帮助，赞一个