第四周题解

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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 列出叶结点

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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'可以避免冗余搜索，降低时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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 深入虎穴

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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算法的应用，只需要在更新路径时加上对花费金额的更新就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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 最短工期

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}