文章目录

第一题：《教父》家族关系维护
第二题：柯里昂家族树

第一题：《教父》家族关系维护

题目描述

在《教父》中，有五个家族，分别是Corleone家族、Tattaglia家族、Cuneo家族、Stracci家族和Barzini家族。五个家族之间的关系是复杂的，它们之间可能存在敌对关系、盟友关系和中立关系。

你需要写一个程序来计算五个家族之间的关系。你需要输入五个家族之间的关系，然后输出五个家族之间的关系矩阵。

你需要自定义一个算法来计算五个家族之间的关系，算法的输入是五个家族之间的关系，输出是五个家族之间的关系矩阵。

算法的实现方式是你自己决定的，但你需要考虑这道题的时间复杂度和空间复杂度。

输入格式：

输入第一行包含五个整数，分别表示Corleone家族、Tattaglia家族、Cuneo家族、Stracci家族和Barzini家族之间的关系。整数的取值范围是-1、0、1，分别表示敌对关系、中立关系和盟友关系。

输入格式

输出格式

输出五行，每行五个整数，分别表示Corleone家族、Tattaglia家族、Cuneo家族、Stracci家族和Barzini家族之间的关系。整数的取值范围是-1、0、1，分别表示敌对关系、中立关系和盟友关系。

输入样例

1 -1 0 0 -1

输出样例

1 -1 0 0 -1
-1 1 0 0 1
0 0 1 0 0
0 0 0 1 0
-1 1 0 0 1

解题思路&C++题解

算法1

(暴力枚举) O ( n 2 ) O(n^2) O(n2)

对于每个家族，枚举其他四个家族，如果两个家族之间有关系，就在矩阵中记录下来。

C++ 代码：

#include <iostream>
using namespace std;

const int N = 5;

int main()
{
    int a[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) cout << "0 ";
            else if (a[i][j] == 1) cout << "1 ";
            else if (a[i][j] == -1) cout << "-1 ";
            else cout << "0 ";
        }
        cout << endl;
    }

    return 0;
}

算法2

(暴力枚举) O ( n 2 ) O(n^2) O(n2)

和算法1相似，但是使用了一个二维数组来存储家族之间的关系，这样就可以直接访问数组来判断两个家族之间的关系，而不需要枚举。

C++ 代码：

#include <iostream>
using namespace std;

const int N = 5;

int main()
{
    int a[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) cout << "0 ";
            else cout << a[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

算法3

(暴力枚举) O ( n 2 ) O(n^2) O(n2)

和算法2相似，但是使用了邻接矩阵来存储家族之间的关系。邻接矩阵是一种常见的图论数据结构，它用二维数组表示图中节点之间的边。在这道题中，每个家族就是图中的一个节点，家族之间的关系就是边。使用邻接矩阵可以更方便地表示和操作图中的节点和边。

C++ 代码：

#include <iostream>
using namespace std;

const int N = 5;

int main()
{
    int a[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) cout << "0 ";
            else if (a[i][j] == 1 || a[j][i] == 1) cout << "1 ";
            else if (a[i][j] == -1 || a[j][i] == -1) cout << "-1 ";
            else cout << "0 ";
        }
        cout << endl;
    }

    return 0;
}

算法4

(暴力枚举) O ( n 2 ) O(n^2) O(n2)

和算法3相似，但是使用了邻接表来存储家族之间的关系。邻接表是另一种常见的图论数据结构，它用链表表示图中节点之间的边。在这道题中，每个家族就是图中的一个节点，家族之间的关系就是边。使用邻接表可以更方便地表示和操作图中的节点和边。

C++ 代码：

#include <iostream>
#include <vector>
using namespace std;

const int N = 5;

int main()
{
    vector<int> a[N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            int x;
            cin >> x;
            if (x != 0) a[i].push_back(j);
        }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) cout << "0 ";
            else
            {
                bool flag = false;
                for (int k = 0; k < a[i].size(); k++)
                {
                    if (a[i][k] == j)
                    {
                        cout << "1 ";
                        flag = true;
                        break;
                    }
                }
                if (!flag) cout << "0 ";
            }
        }
        cout << endl;
    }

    return 0;
}

算法5

(暴力枚举) O ( n 2 ) O(n^2) O(n2)

和算法4相似，但是使用了边集数组来存储家族之间的关系。边集数组是另一种常见的图论数据结构，它用一个数组来表示图中的边。在这道题中，每个家族就是图中的一个节点，家族之间的关系就是边。使用边集数组可以更方便地表示和操作图中的节点和边。

C++ 代码：

#include <iostream>
#include <utility>
using namespace std;

const int N = 5;

int main()
{
    pair<int, int> a[N * N];
    int cnt = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            int x;
            cin >> x;
            if (x != 0) a[cnt++] = make_pair(i, j);
        }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) cout << "0 ";
            else
            {
                bool flag = false;
                for (int k = 0; k < cnt; k++)
                {
                    if (a[k].first == i && a[k].second == j)
                    {
                        cout << "1 ";
                        flag = true;
                        break;
                    }
                }
                if (!flag) cout << "0 ";
            }
        }
        cout << endl;
    }

    return 0;
}

算法6

(并查集) O ( n ) O(n) O(n)

使用并查集来维护五个家族之间的关系。并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。在这道题中，可以将每个家族看作一个集合，然后使用并查集来维护五个家族之间的关系。

首先，将每个家族初始化为一个单独的集合。然后，对于输入的每一对家族之间的关系，使用并查集的合并操作将这两个家族合并为一个集合。最后，遍历五个家族，对于每个家族，输出它和其他四个家族之间的关系。

C++ 代码：

#include <iostream>
using namespace std;

const int N = 5;

int fa[N];

int find(int x)
{
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    for (int i = 0; i < N; i++) fa[i] = i;

    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        int fx = find(x), fy = find(y);
        if (fx != fy) fa[fx] = fy;
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) cout << "0 ";
            else if (find(i) == find(j)) cout << "1 ";
            else cout << "-1 ";
        }
        cout << endl;
    }

    return 0;
}

算法7

(深度优先搜索) O ( n 2 ) O(n^2) O(n2)

使用深度优先搜索来维护五个家族之间的关系。深度优先搜索是一种图论算法，用于遍历图中的所有节点。在这道题中，每个家族就是图中的一个节点，家族之间的关系就是边。

首先，初始化五个家族之间的关系矩阵。然后，对于输入的每一对家族之间的关系，使用深度优先搜索的遍历操作来更新五个家族之间的关系矩阵。最后，输出五个家族之间的关系矩阵。

C++ 代码：

#include <iostream>
using namespace std;

const int N = 5;

int a[N][N];

void dfs(int x, int y)
{
    a[x][y] = 1;
    for (int i = 0; i < N; i++)
        if (a[y][i] == 1 && a[x][i] == 0)
            dfs(x, i);
}

int main()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (a[i][j] == 1) dfs(i, j);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }

    return 0;
}

第二题：柯里昂家族树

题目描述

在《教父》中，柯里昂家族是一个著名的黑手党家族，由家族的首领柯里昂（Don Corleone）和他的四个儿子构成。柯里昂家族的家谱是一棵二叉树，其中柯里昂是根节点，他的儿子们分别是他的左儿子和右儿子。

现在，你需要编写一个程序，读入一个包含若干行的字符串，每行表示一个人的信息。每行的格式如下：

<人物名称> is the <父亲名称>'s <儿子>

其中，人物名称是一个不包含空格的字符串，父亲名称和儿子也是一个不包含空格的字符串。

例如，下面是一棵柯里昂家族的家谱：

Don Corleone is the Don’s son
Fredo Corleone is the Don’s son
Michael Corleone is the Don’s son
Tom Hagen is the Don’s adopted son

你的程序需要按照这些信息建立一棵二叉树，并输出这棵树的前序遍历。

例如，对于上面的家谱，输出应该是：

Don Corleone Fredo Corleone Michael Corleone Tom Hagen

你的程序需要支持以下功能：

建立二叉树。你需要定义一个结构体表示一个节点，包含人物名称、左儿子和右儿子三个字段。你需要编写一个函数，读入若干行字符串，根据字符串中的信息建立二叉树。
输出前序遍历。你需要编写一个函数，输出给定二叉树的前序遍历。

约定

人物名称和父亲名称均由不超过 100 个字符组成，且不包含空格。
儿子的值可能是 “son” 或 “adopted son”。
输入中可能会出现重名的人物，你的程序需要处理这种情况。
输入的字符串保证是合法的，不会出现父亲名称找不到的情况。

输入格式

输入的第一行包含一个整数 n（1 <= n <= 1000），表示字符串的行数。

接下来的 n 行，每行包含一个字符串，表示一个人的信息。字符串的格式如上文所述。

输出格式

输出给定二叉树的前序遍历，每个人物名称占一行。

输入样例

4
Don Corleone is the Don's son
Fredo Corleone is the Don's son
Michael Corleone is the Don's son
Tom Hagen is the Don's adopted son

输出样例

Don Corleone
Fredo Corleone
Michael Corleone
Tom Hagen

解题思路&C++题解

算法1

(暴力枚举) O ( n 2 ) O(n^2) O(n2)

对于每个节点，遍历整棵树，找到他的父亲节点，然后将他作为父亲节点的左儿子或右儿子，听起来很奇怪😂

算法2

(暴力枚举) O ( n 2 ) O(n^2) O(n2)

和算法1思路相同，只是将结构体改为类，并使用类的成员函数和私有变量来表示二叉树。

算法3

我们来看一种时间复杂度更优的做法。

我们可以使用一个哈希表（也叫映射）来存储每个人物的信息，哈希表的键为人物名称，值为人物节点的指针。这样，我们就可以在建立二叉树时，直接在哈希表中查找父亲节点的信息，将新节点作为父亲节点的左儿子或右儿子。

这种做法的时间复杂度是 O ( n ) O(n) O(n) 的，因为哈希表的查找时间复杂度为 O ( 1 ) O(1) O(1)。

下面是用 C++ 实现的代码：

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node {
    string name;
    Node* left;
    Node* right;
    Node(string name): name(name), left(nullptr), right(nullptr) {}
};

unordered_map<string, Node*> nodes;

Node* buildTree() {
    int n;
    cin >> n;
    cin.get();  // 忽略换行符

    while (n--) {
        string line;
        getline(cin, line);

        // 解析字符串
        int i = 0;
        while (line[i] != ' ') {
            i++;
        }
        string name = line.substr(0, i);
        i += 3;  // 跳过 " is the "
        int j = i;
        while (line[j] != '\'') {
            j++;
        }
        string fatherName = line.substr(i, j - i);
        i = j + 4;  // 跳过 "'s "
        string relation = line.substr(i);

        // 在哈希表中查找父亲节点
        Node* father = nodes[fatherName];
        if (father == nullptr) {
            father = new Node(fatherName);
            nodes[fatherName] = father;
        }

        // 创建新节点
        Node* node = new Node(name);

        // 将新节点添加到父亲节点的左儿子或右儿子
        if (relation == "son") {
            if (father->left == nullptr) {
                father->left = node;
            } else {
                father->right = node;
            }
        } else {
            father->right = node;
        }
    }

    // 返回根节点
    return nodes["Don Corleone"];
}

void preorderTraversal(Node* node) {
    cout << node->name << endl;
    if (node->left != nullptr) {
        preorderTraversal(node->left);
    }
    if (node->right != nullptr) {
        preorderTraversal(node->right);
    }
}

int main() {
    Node* root = buildTree();
    preorderTraversal(root);
    return 0;
}

热爱科技的刘同学

【有料c++题目周刊 | 第六期】The Godfather

文章目录

第一题：《教父》家族关系维护

题目描述

输入格式

输出格式

输入样例

输出样例

解题思路&C++题解

算法1

算法2

算法3

算法4

算法5

算法6

算法7

第二题：柯里昂家族树

题目描述

约定

输入格式

输出格式

输入样例

输出样例

解题思路&C++题解

算法1

算法2

算法3