首页 > 其他分享 >第四周题解

第四周题解

时间：2023-09-30 17:44:05浏览次数：34  
标签：cnt 遍历 dist int 题解 cin ++ 四周

第四周题解

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位于中序遍历中的下标idx
    cout << " " << 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）遍历，右边界为tr
    if(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];
        }
    }
    else
        cout << "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; //因为是完全二叉树，所以下标最大为n
    Seq(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); //根节点为1
    for(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++)//工作时长可能为0
		for (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;
}

标签：cnt,遍历,dist,int,题解,cin,++,四周
From： https://www.cnblogs.com/zhaiyinggao/p/17738063.html

相关文章

  • vs code调试rust乱码问题解决方案
    在terminal中用chcp65001修改一下字符集，就行了。有的博主推荐修改区域中的设置，这会引来很大的问题。千万不要修改如下设置：......
  • P7167 [eJOI2020 Day1] Fountain 题解
    Description给定\(n\)个从上往下圆心重叠的圆盘，给定每个圆盘的直径\(d_i\)和容量\(c_i\)，所有圆盘底下有一个容量为\(\infty\)的水池，编号为\(0\)。\(q\)次询问，每次给定\(r\)和\(v\)表示往第\(r\)个圆盘里倒\(v\)的水，输出水最后流到哪个圆盘会停止。Solution倍......
  • 【题解】CF1110D Jongmah（DP）
    【题解】CF1110DJongmah代码很短，但是思路我怎么也想不到的神仙DP。题意概述你在玩一个叫做Jongmah的游戏，你手上有\(n\)个麻将，每个麻将上有一个在\(1\)到\(m\)范围内的整数\(a_i\)。为了赢得游戏，你需要将这些麻将排列成一些三元组，每个三元组中的元素是相同的或者连......
  • 洛谷题解 | AT_abc321_c Primes on Interval
    目录题目翻译题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2样例#3样例输入#3样例输出#3题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查.众所周知,素数又被称为质数，其含义就是除了数字一和本身之外不能......
  • 算法题解--蓝桥云课跳跃
    题目蓝桥云课跳跃1.看完题目先写了个二维数组，然后就真的不懂了，最后找了个大概能懂的题解，思路大概是是建立坐标，再用递归求出所有路径，找出其中最大的权值和2.遇到的问题还是没思路，而且写下面使用递归的方法时光出错，不是很熟练3.测试结果：4.收获：学习过的static终于派上了用场，......
  • 20211325 2023-2024-1 《信息安全系统设计与实现（上）》第四周学习笔记
    202113252023-2024-1《信息安全系统设计与实现（上）》第四周学习笔记一、任务要求自学教材第7,8章，提交学习笔记（10分），评分标准如下1.知识点归纳以及自己最有收获的内容，选择至少2个知识点利用chatgpt等工具进行苏格拉底挑战，并提交过程截图，提示过程参考下面内容（4分）“我......
  • CF38F 题解
    blog。严重怀疑这题放到2023年至少*2000，评绿合情合理。首先是博弈论。然后数据范围很小。直接暴力DP啪的一下上去了，很快啊！这就抽象起来了。另一篇题解说不能暴力转移，但是你先预处理出来\(num(s)\)，然后直接记忆化搜索，暴力枚举每一次操作的字符，这不就做完了吗。具体一点的......
  • [春季测试 2023] 密码锁 题解
    题目传送门闲话duliu题，写了10k。题意形式化地，对于\(1\leqi\leqk\)，定义密码锁第\(i\)行的松散度为\[c(i)=\max\limits_{j=1}^na_{i,j}-\min\limits_{j=1}^na_{i,j}\]同时定义整个密码锁的松散度为\[C=\max\limits_{1\leqi\leq......
  • CF961E Tufurama 题解
    CF961ETufurama题解二维数点做法题意  给定长度为\(n\)的序列\(a\)，统计二元组\((i,j)\)的个数，使得该二元组满足\(1\leqi<j\leqn,a_i\geqj,a_j\geqi\)。\(n\)在\(2\times10^{5}\)级别，\(a_i\)在\(1\times10^{9}\)级别。思路分析  我们考虑把......
  • 《信息安全系统设计与实现》第四周学习笔记
    一、课程内容第七章学习文件操作级别1、硬件级别fdiskmkfsfsck碎片整理2、操作系统内核中的文件系统函数3、系统调用4、I/O库函数5、用户命令6、sh脚本低级别的文件操作中的常用函数：打开和关闭文件：open()：打开文件并返回文件描述符。close()：关闭文件。读写文件：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99