八月份杭州X02笔记整理~（2/3）
2023-08-20 14:44:38
发布于：浙江
11阅读
0回复
0点赞
Day5 下午 第十课 深度优先搜索
模板
#include<bits/stdc++.h>
using namespace std;
struct node{int x, y;};
node pre[100][100];
char mp[100][100];
int vis[100][100];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
bool ok = false;
void printvis(){
cout << "_______________________________" << endl;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cout << vis[i][j];
}
cout << endl;
}
cout << "_______________________________" << endl;
}
void printmp(){
cout << "_______________________________" << endl;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cout << mp[i][j];
}
cout << endl;
}
cout << "_______________________________" << endl;
}
void dfs(int x,int y){
if(ok == true){
return ;
}
for(int i = 0;i < 4;i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[tx][ty] == 0
&& mp[ty][tx] == '.'){
if(tx == n && ty == m){
ok = true;
return ;
}
vis[tx][ty] = vis[x][y] + 1;
pre[tx][ty] = node{x,y};
mp[tx][ty] = '@';
printmp();
printvis();
getchar();
dfs(tx,ty);
vis[tx][ty] = 0;
pre[tx][ty] = node{0,0};
mp[tx][ty] = '.';
}
}
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> mp[i][j];
}
}
vis[1][1] = 0;
dfs(1,1);
return 0;
}
Day6 下午 第十二课 广度优先搜索
实验性代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 10;
struct node{int x,int y,step;};
node que[MAXN];
int f = 0,r = 0; // front 前端 rear 后端
char mp[MAXN][MAXN]; // 图
int vis[MAXN][MAXN]; // 标记
node pre[MAXN][MAXN]; // 前源点
int n,m;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void printmp(){
cout << "_______________________________\n";
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cout << mp[i][j];
}
cout << endl;
}
cout << "_______________________________\n";
}
void printvis(){
cout << "_______________________________\n";
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cout << vis[i][j];
}
cout << endl;
}
cout << "_______________________________\n";
}
void printpath(int x,int y){
if(x == 0 && y == 0){
return ;
}
printpath(pre[x][y].x,pre[x][y].y);
cout << "(" << x << "," << y << ")";
}
void bfs(int x,int y){
while(f < r){
node tmp = que[f++]; //取一个发散源 准备发散
for(int i = 0;i < 4;i++){
int tx = tmp.x + dx[i];
int ty = tmp.y + dy[i];
if(tx >= 1&&tx <= n&&ty >= 1&&ty <= m&& mp[tx][ty] == '.'){
mp[tx][ty] = '@';
vis[tx][ty] = vis[tmp.x][tmp.y] + 1;
pre[tx][ty] = node{tmp.x,tmp.y,tmp.step + 1};
printmp();
printvis();
getchar();
que[r++] = node{tx,ty,tmp.step + 1};
}
}
}
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> mp[i][j];
}
}
//准备第一个或第一组的起始点
que[r++] = node{1,1,0};
vis[1][1] = 0;
mp[1][1] = '@';
bfs(1,1); // Breadth First Search
printpath(6,10);
return 0;
}
Day7 上午 第十三课 树与二叉树
Part 1 背景
Part 2 树的存储
实验性代码（孩子表示法）
#include <iostream>
#include <vector>
using namespace std;
const int N = 100;
vector<int > tree[N]; // tree[i]
int n, m;
int main() {
cin >> n >> m; // n 个结点 m 条边
for (int i = 1; i <= m; i ++) {
int r, s;
cin >> r >> s;
tree[r].push_back(s);
}
for (int i = 1; i <= n; i ++) {
printf("父节点 %d：", i);
for (int j = 0; j < tree[i].size(); j ++) {
cout << tree[i][j] << ' ';
}
if (tree[i].size() == 0) {
cout << "叶子";
}
cout << endl;
}
return 0;
}
Part 3 二叉树
二叉树的五大性质：
【性质 1】在二叉树的第 i 层上最多有 2^i − 1 个结点（i >= 1）。第 1 层最多 1 个结点，第 2 层最多 2 个结点，第 3 层最多 4 个结点……
【性质 2】深度为 k 的二叉树至多有 2^k − 1 个结点（k >= 1）
【性质 3】任意一棵二叉树，若其叶子结点 (度为 0 结点) 的数量为 n0，度为 2 的结点数量为 n2，则：n0 与 n2 一定满足：n0 = n2 + 1 。
【性质 4】具有 n (n ≥ 0) 个结点的完全二叉树的深度为 ⌊log2(n)⌋ + 1。⌊ ⌋ 表示下取整。
【性质 5】 若将一棵有 n 个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1，2，…，n，则：
- 若结点编号 i = 1 ，则结点 i 为根，无父结点；
- 若 i > 1 ，则 i 的父结点编号为 i / 2；
- 针对编号为 i 的结点：
3.1 其左孩子编号为 2 * i (2 * i ≤ n) ；
3.2 其右孩子编号为 2 * i + 1 (2 * i + 1 ≤ n)；
二叉树的存储
二叉树的遍历
Day7 下午 第十四课 图论
Part 1 图的定义与概念
Part 2 图的存储
邻接矩阵
样例代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 10;
const int INF = 0x3f3f3f3f;
int g[MAXN][MAXN]; // 邻接矩阵
int n,m; // 顶点与边的数量
int main(){
// memset(数组首地址,取最低八位一字节部分,填充的字节);
memset(g,0x3f,sizeof g);
cin >> n >> m;
for(int i = 1;i <= n;i++){
g[i][i] == 0;
}
for(int i = 1;i <= m;i++){
int u,v,w;
cin >> u >> v >> w;
g[u][v] = w;
g[v][u] = w;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(g[i][j] == INF){
cout << "INF";
}
else{
printf("%3d",g[i][j]);
}
}
cout << endl;
}
return 0;
}
邻接表
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 10;
struct node{ // N =顶点数据结构
int v;
int w;
};
vector<node> vex[MAXN]
int n,m;
int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int u,v,w;
cin >> u >> v >> w;
vex[u].push_back(node{v,w});
vex[v].push_back(node{u,w});
}
for(int i = 1;i <= n;i++){
printf("顶点 %d 的邻接：",i);
for(int j = 0;j < vex[i].size();j++){
printf("(%d,%d)",vex[i][j].v,vex[i][j].w);
}
cout << endl;
}
return 0;
}
Part 3 Dijkstra 最短路
实验性代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 10;
const int INF = 0x3f3f3f3f;
struct node{ // 顶点数据结构
int v;
int w;
};
vector<node> vex[MAXN]; // 顶点数组
int n,m; // 顶点与边的数量
int dis[MAXN]; // 1~i的最短距离
int pre[MAXN]; // 顶点的前源点
int vis[MAXN];
void print(int a[],int n,string name){
cout << name << ":";
for(int i = 1;i <= n;i++){
if(a[i] == INF){
printf("INF ");
}
else{
printf("%3d ",a[i]);
}
}
cout << endl;
cout << "______________________________________\n";
}
int main(){
cin >> n >> m;
memset(dis,0x3f,sizeof dis);
for(int i = 1;i <= m;i++){
int u,v,w;
cin >> u >> v >> w;
vex[u].push_back(node{v,w});
vex[v].push_back(node{u,w}); // 无向图
}
// 起点是1
dis[1] = 0;
for(int i = 1;i <= n;i++){
int mii,miv = INF;
// 找到在未标记的点中距离最近的一个
for(int j = 1;j <= n;j++){
if(vis[j] == 1){
continue;
}
if(dis[j] < miv){
miv = dis[j];
mii = j;
}
}
vis[mii] = 1;
for(int j = 0;j < vex[mii].size();j++){
// 起点：mii 终点 vex[mii][i].v
int U = mii;
int V = vex[mii][j].v;
int W = vex[mii][j].w; // U~V的距离
if(dis[V] > dis[U] + W){
dis[V] = dis[U] + W;
pre[V] = U;
}
}
}
print(dis,n,"dis");
print(pre,n,"pre");
return 0;
}
Day 8 上午 第15课 floyd最短路
例题 过关道具
记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;
const int INF = 0x3f3f3f3f;
long long a[MAXN];
long long ret[MAXN];
int n;
long long func(int num){
if(num <= 0){
return INF;
}
if(ret[num]){
return ret[num];
}
ret[num] = INF;
for(int i = 0;i < n;i++){
ret[num] = min(ret[num],func(num-a[i])+1);
}
return ret[num];
}
int main(){
long long num;
cin >> n;
for(int i = 0;i < n;i++){
cin >> a[i];
ret[a[i]] = 1;
}
cin >> num;
if(num == 0){
cout << "0";
return 0;
}
long long k = func(num);
if(k == INF){
cout << "-1";
}
else{
cout << k;
}
return 0;
}
最后一课放不下了，点击跳转第三部分
完结撒花
date 8.20
有帮助，赞一个