第四周题解

news/发布时间2024/7/15 4:43:24

第四周题解

7-1 根据后续和中序遍历输出先序遍历

利用数组保存树的后序遍历和中序遍历,根据后续遍历和中序遍历的特点还原树,并根据先序遍历的顺序,即根左右,利用函数递归输出打印,注意输出格式的正确性。

#include<bits/stdc++.h>
using namespace std;
const int N = 40;
typedef long long LL;
int in[N], last[N];
int n;
void pre(int root, int s, int e) //root:当前子树的根节点;s:中序遍历的起始位置;e:中序遍历的终止位置
{if(s > e) return; //边界int idx = s;while(in[idx] != last[root]) idx++; //找到root位于中序遍历中的下标idxcout << " " << last[root];pre(root - (e - idx) - 1, s, idx - 1);pre(root - 1, idx + 1, e);  //先序遍历:根左右
}
int main()
{cin >> n;for(int i = 0; i < n; i++) cin >> last[i];for(int i = 0; i < n; i++) cin >> in[i];cout << "Preorder:";pre(n - 1, 0, n - 1);
}

7-2 这是二叉搜索树吗?

若是一颗二叉搜索树,则先序遍历的数组中,一定有一个分界点,分界点的一边均小于根节点,另一边均大于根节点(因为此题存在镜像,所以不一定哪一边大于根节点,哪一边小于,所以两种情况都要判断)

是否存在边界点可转化为:第一个大于根节点的下标一定与第一个小于根节点的下标差1。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
bool lflag = true; //两次判断
int pre[N];
int n;
vector<int> ve; //用来存储后序遍历的结果,其大小也用来判断是否遍历完全
void judge(int l, int r)
{int tl = l + 1, tr = r; //根节点为l,从根节点左边开始(tl)遍历,右边界为trif(lflag) //左边小,右边大{while(tl <= r && pre[tl] < pre[l]) tl++;while(tr > l && pre[tr] >= pre[l]) tr--;}else //镜像{while(tl <= r && pre[tl] >= pre[l]) tl++;while(tr > l && pre[tr] < pre[l]) tr--;}if(tl - tr != 1) return; //不满足条件,退出judge(l + 1, tr);judge(tl, r);ve.push_back(pre[l]); //后序遍历:左右根
}
int main()
{cin >> n;for(int i = 0; i < n; i++) cin >> pre[i];judge(0, n - 1);if(ve.size() != n) //不是左小右大,则判断镜像{lflag = false;ve.clear();judge(0, n - 1);}if(ve.size() == n) //遍历完全,满足{cout << "YES" << endl;for(int i = 0; i < ve.size(); i++){if(i)cout << " ";cout << ve[i];}}elsecout << "NO" << endl;
}

7-3 列出叶结点

结构体数组存储树,队列实现树的层序遍历,判断叶节点

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 11;
int tag[N]; //标记已经被用过的节点
int n;
struct Tree
{int l, r;
}t[N]; //树
void Seq(int root)
{bool flag = false;queue<int> q; //队列实现层序遍历(bfs)q.push(root);while(!q.empty()){root = q.front();q.pop();if(t[root].l == -1 && t[root].r == -1) //左右节点均为空(叶子节点){if(flag) cout << " ";cout << root;flag = true;}else{if(t[root].l != -1) q.push(t[root].l); //入队if(t[root].r != -1) q.push(t[root].r);}}
}
int main()
{cin >> n;for(int i = 0; i < n; i++){char l, r;cin >> l >> r;if(l == '-') t[i].l = -1; //空节点else{t[i].l = l - '0';tag[t[i].l] = 1;}if(r == '-') t[i].r = -1;else{t[i].r = r - '0';tag[t[i].r] = 1;}}int root;for(int i = 0; i < n; i++) //寻找根节点{if(!tag[i]){root = i;break;}}Seq(root);
}

7-4 完全二叉树的层序遍历

用数组存储后序遍历,利用层序遍历在数组中存储的特点:若根节点是1,则之后的子树中根节点为cnt,左孩子为(2*cnt),右孩子为(2*cnt+1)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 40;
int last[N], t[N];
int n, idx;
void Seq(int cnt)
{if(cnt > n) return; //因为是完全二叉树,所以下标最大为nSeq(2 * cnt);Seq(2 * cnt + 1);t[cnt] = last[++idx]; //后序遍历:左右根
}
int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> last[i];Seq(1); //根节点为1for(int i = 1; i <= n; i++){if(i > 1) cout << " ";cout << t[i];}
}

7-5 村村通

Prim| Kruskal

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, inf = 0x3f3f3f3f;
int dist[N], g[N][N];
bool vis[N];
int n, m;
int Prim()
{memset(dist, 0x3f, sizeof dist);int res = 0;for(int i = 0; i < n; i++){int t = -1;for(int j = 1; j <=n; j++){if(!vis[j] && (t == -1 || dist[t] > dist[j]))t = j;}if(i && dist[t] == inf) return inf;if(i) res += dist[t];vis[t] = true;for(int j = 1; j <= n; j++){dist[j] = min(dist[j], g[t][j]);}}return res;
}
int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);while(m--){int a, b, c;cin >> a >> b >> c;g[a][b] = g[b][a] = c;}int ans = Prim();if(ans == inf) cout << -1;else cout << ans;
}

7-6 寻宝图

本题采用bfs算法(宽度优先算法)进行搜索,每次从一个未被搜索过的岛屿块出发。

两点注意

  • 本题数据不能采用二维数组,二维数组会超时,应采用字符串数组存取数据
  • s[x][y]='0'可以避免冗余搜索,降低时间复杂度
#include<bits/stdc++.h>
#include <unordered_map>using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m;
bool fg = false;
string s[N];
int cnt1, cnt2;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
void bfs(int x, int y)
{if (x < 0 || x >= n || y < 0 || y >= m)return;if (s[x][y] == '0')return;if (s[x][y] > '1')fg = true;s[x][y] = '0';for (int i = 0; i < 4; i++)bfs(x + dx[i], y + dy[i]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;for (int i = 0; i < n; i++)cin >> s[i];for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (s[i][j] > '0'){cnt1++;fg = false;bfs(i, j);if (fg)cnt2++;}}}cout << cnt1 << " " << cnt2 << endl;return 0;
}

7-7 深入虎穴

本题是一道典型的拓扑排序,拓扑排序适用于有向无环图。

由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

实现拓扑排序最关键的一点是开一个数组存储所有点的入度,从出发点开始,每次都减小与出发点相连的点的入度直至为零,把入度为零的点放入到队列中,再从队列中依次拿出重复上述操作,如果最后队列中点的个数与总点数不相等或搜索入度为零的点失败,说明本图是一个有环图,不能实现拓扑排序。

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int d[N], q[N];
int n, m, x;
void add(int a, int b)//a到b的边
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void topsort()
{int hh = 0, tt = 0;for (int i = 1; i <= n; i++)if (!d[i])//找到入度为零的点q[tt++] = i;while (hh <= tt){int t = q[hh++];for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];d[j]--;if (!d[j])q[tt++] = j;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;memset(h, -1, sizeof h);for (int i = 1; i <= n; i++){cin >> m;for (int j = 1; j <= m; j++){cin >> x;add(i, x);d[x]++;}}topsort();cout << q[n - 1] << endl;return 0;
}

7-8 旅游规划

这道题就是dijkstra算法的应用,只需要在更新路径时加上对花费金额的更新就可以

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
const int N = 510;
int g[N][N], w[N][N];
int dist[N], cost[N];
bool st[N];
int n, m, s, d;
void dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[s] = 0;for (int i = 0; i < n; i++)//有n个点所以要进行n次 迭代{int t = -1;for (int j = 0; j < n; j++)//这里的j代表的是从0号点开始{if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;}st[t] = true;for (int j = 0; j < n; j++){if (!st[j] && dist[j] > dist[t] + g[t][j])//依次更新每个点所到相邻的点路径值和金额{dist[j] = dist[t] + g[t][j];cost[j] = cost[t] + w[t][j];//随时更新金额}else if (!st[j] && dist[j] == dist[t] + g[t][j] && cost[j] > cost[t] + w[t][j])cost[j] = cost[t] + w[t][j];}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);memset(g, 0x3f, sizeof g);memset(w, 0x3f, sizeof w);cin >> n >> m >> s >> d;for (int i = 0; i < m; i++)//输入次数{int a, b, l, c;cin >> a >> b >> l >> c;g[a][b] = g[b][a] = l;w[a][b] = w[b][a] = c;}dijkstra();cout << dist[d] << " " << cost[d] << endl;return 0;
}

7-9 最短工期

本题也是拓扑排序的应用,只需要将在离散数学中学过的最早完工时间是最长工作时间加进来就可以

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 110;
int g[N][N], d[N], t[105];
int n, ans, cnt;//ans最早完工时间
int m, p, x, y, fg;
void topsort() 
{while (1) {fg = 0;//每次重置for (int i = 0; i < n; i++) {if (!d[i]) {  d[i]--;//入度变为0,任务完成cnt++;fg = 1;for (int j = 0; j < n; j++) {if (g[i][j] != -1) //有以i为前驱任务的任务 {d[j]--; // 入度减一t[j] = max(t[j], t[i] + g[i][j]); //选择最长的工作时间 ans = max(ans, t[j]);//统计最早完工时间 }}}}if (!fg) break;//跳出循环的条件}if (cnt == n) cout << ans << endl;  else cout << "Impossible" << endl;//有环存在 
}int main() 
{cin >> n >> m;for (int i = 0; i < n; i++)//工作时长可能为0for (int j = 0; j < n; j++)g[i][j] = -1;while (m--) {cin >> x >> y >> p;g[x][y] = p;d[y]++;//入度即前驱任务}topsort();return 0;
}

7-10 分而治之

本题可以采用结构体和map巧妙解决

  • 用结构体存储相连接的两个城市
  • 用map存储哪个城市已被攻击
  • 遍历结构体数组,如果相连接的两个城市都没有被攻击,那就输出NO,反之YES
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct node
{int x, y;
}s[N];
int n, m, t, k, x;
int main() 
{cin >> n >> m;for (int i = 0; i < m; i++)cin >> s[i].x >> s[i].y;cin >> t;for (int i = 0; i < t; i++){cin >> k;map<int, int>p;for (int i = 0; i < k; i++){cin >> x;p[x] = 1;//已被攻击}int cnt = 0;for (cnt; cnt < m; cnt++){if (p[s[cnt].x] != 1 && p[s[cnt].y] != 1)//联通但都没有被进攻{cout << "NO" << endl;break;}}if (cnt >= m)cout << "YES" << endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.jwkm.cn/p/04142785.html

如若内容造成侵权/违法违规/事实不符,请联系宁远站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

vue:el-table在resize时报错(element-plus@2.3.12)

一,报错信息: Uncaught runtime errors:ERROR ResizeObserver loop completed with undelivered notifications. at handleError (webpack-internal:///./node_modules/webpack-dev-server/client/overlay.js:299:58) at eval (webpack-internal:///./node_modules/webpac…

传递函数变换到状态空间

1. 分子为1的传递函数 例: \[G(s)=\frac{1}{s^3+a_2s^2+a_1s+a_0} \]首先写成输入输出关系: \[(s^3+a_2s^2+a_1s+a_0)Y(s)=U(s) \]对应的微分方程: \[\dddot{y}(t)+a_2\ddot y(t)+a_1\dot y(t)+a_0y(t)=u(t)\\ \dddot{y}(t)=-a_2\ddot y(t)-a_1\dot y(t)-a_0y(t)+u(t)\\ \]令…

-bash: ifconfig: 未找到命令

#abao { background-color: rgba(245, 245, 245, 1); padding: 10px; text-align: center; width: 800px } 命令: yum -y install ifconfig如果返回为:没有可用软件包 ifconfig。错误:无须任何处理则输入:yum search ifconfig返回:==================== 匹配:ifconfig ==…

SOC芯片架构技术分析(三)

SOC芯片架构技术分析(三) 3.1 汽车:汽车平台未来需要高算力 1)汽车半导体涵盖了汽车芯片、功率器件、传感器等重要电子零部件。汽车的计算芯片包括传统的MCU芯片和SoC芯片。 MCU芯片一般包含CPU一个处理器单元;而汽车SoC一般包含多个处理单元。 2)ECU(Electronic Contro…

python文件操作

在python,使用open函数,可以打开一个已经存在的文件,或者创建一个新文件 open(文件路径,访问模式)f = open(test.txt, w)读文件:f1 = open(test1.txt,r)content = f1.read()print(content)readLines返回一个列表,可以遍历 f1 = open(test1.txt,r)content = f1.readlines(…