PAT甲级题目

PAT甲级的题目有关于树的题目,1053,1086,1090,1102,1106,1115,1119,1038,1110,1020,1043

A1053

这题目比较简单,给定一棵树,给定一个数字,要你找到所有和等于给定数字的路径。这个题目的树没有给出是二叉树,自然不能按照原来二叉树的方法来构建了。其实就是BFS,用DFS也是可以的,不过考虑到DFS还要新开一个数组来存储路径,还是使用BFS。 首先是树的结构,只需要在原来二叉树的基础上修改一下就好了。

typedef struct treeNode {
    int val;
    int weight;
    vector<struct treeNode *> generator;
    int parent = -1;
} *TreeNode, treeNode;

把原来的左右子树修改成一个vector存储即可。树的结构中新添加了一个parent,是用于找到根节点,因为题目给出的树是一个列表,接着是树的父节点,不添加parent找不到父节点。如果parent是-1那么就是根节点了。

TreeNode createTree(int n, TreeNode *array, int allNodes) {
    for (int i = 0; i < n; ++i) {
        int index;
        int num;
        cin >> index >> num;
        index_map[index] = true;
        for (int j = 0; j < num; ++j) {
            int next;
            cin >> next;
            array[next]->parent = index;

            array[index]->generator.push_back(array[next]);

        }
        sort(array[index]->generator.rbegin(), array[index]->generator.rend(), cmp);

    }

    for (int k = 0; k < allNodes; ++k) {
        if (array[k]->parent == -1) {
            return array[k];
        }
    }
    return nullptr;
}

创建树的过程,注意后面有一个排序操作,题目的输出要求按照次序输出。然后就是BFS操作了。

void findWeights(TreeNode root, int sum, vector<int> weightsAdd, int equalWeights) {
    if (sum > equalWeights) {
        return;
    } else if (sum < equalWeights) {
        sum += root->weight;
        weightsAdd.push_back(root->weight);
        if (sum == equalWeights) {

            if (!index_map[root->val]) {
                weights_path.push_back(weightsAdd);
                weightsAdd.clear();
            }
            return;
        }
        for (int i = 0; i < root->generator.size(); ++i) {
            TreeNode current = root->generator[i];
            findWeights(current, sum, weightsAdd, equalWeights);
        }
    }
}

BFS把weightsAdd当成是一个拷贝过来的局部变量,不需要回滚操作,比DFS简单多了。然后就是输出了,只需要注意最后不要空格就好。 其实也可以用数组来完成,所占空间可能更小。

1086

这个题目做了很久,要是在上机考试碰见这个题目应该就只有10来分了。题目大意是给定一个入栈出栈的序列,这个出入栈完成后得到的出栈序列是中序遍历的序列,要你求这棵树的后续遍历。我直接从序列入手,发现push操作就是:如果当前节点有左子树,就插入左子树,否则就插入右子树;pop操作是回退到上一课树,按照这个操作就可以创建出一棵树,然后后续遍历即可。然而内存爆炸了。

之前考408的时候遇到过这样的操作,好像是天勤ds里面,中序遍历如果使用栈来实现,入栈顺序就是前序遍历次序。所以题目表面上是给了一个序列,实际上给了前序和中序遍历,让你求后续遍历。这个就很简单了。

TreeNode create(int preL, int preR, int inL, int inR, int *preOrder, int *inOrder) {
    int rootNum = preOrder[preL];
    TreeNode root = new treeNode;
    root->val = rootNum;
    if (preL == preR) {
        root->val = rootNum;
        root->leftChild = root->rightChild = nullptr;
        return root;
    }

    if (preL > preR) {
        return nullptr;
    }

    int mid = -1;

    for (int i = inL; i <= inR; ++i) {
        if (inOrder[i] == rootNum) {
            mid = i;
            break;
        }
    }

    int leftNumber = mid - inL;
    int rightNumber = inR - mid;

    root->leftChild = create(preL + 1, preL + leftNumber, inL, mid - 1, preOrder, inOrder);
    root->rightChild = create(preR - rightNumber + 1, preR, mid + 1, inR, preOrder, inOrder);
    return root;
}

关键就是创建树的操作,天勤的代码题出过这类,主要就是前中序遍历的边界数对就行。

1090

这个题目一开始读的没太懂,两次都超了,只有14分。一开始还以为最后要给出的是路径上零售商的数量,没想到是路径的个数。 很明显是BFS,和上上题一样:

//typedef struct treeNode {
//    int val;
//    vector<struct treeNode *> children;
//    int parent = -1;
//} *TreeNode, treeNode;

double maxPrice = -1;
int maxNumber = -1;

//void BFS(TreeNode root, double currentPrice, double r, vector<int> path) {
//    if (root) {
//        path.push_back(root->val);
//        currentPrice = currentPrice * ((100 + r) / 100);
//        if (maxPrice < currentPrice) {
//            maxPrice = currentPrice;
//            maxNumber = path.size();
//        }
//        for (int i = 0; i < root->children.size(); ++i) {
//            BFS(root->children[i], currentPrice, r, path);
//        }
//    }
//}

建树是不行的,直接就内存爆炸。如此那就直接用数组吧,于是想到从尾巴开始,然而题目有关键一句:It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.假设在供应链上的每名成员都只有一个供应者,除了根部的供应者,没有环,那么就不需要像图一样设置访问标记。

//    for (int j = 0; j < n; ++j) {
//        if (!visited[j]) {
//            int paths = 0;
//            int fa = array[j];
//            while (fa != -1) {
//                visited[fa] = true;
//                fa = array[fa];
//                paths++;
//            }
//            maxNumber = ((maxNumber > paths) ? maxNumber : paths);
//        }
//    }

还是超时了,因为如果从底部开始,会出现很多重复的道路,所以最好还是从底部开始访问,我也是在这里看了别人题解之后才知道,原来输出的最后一个数字应该是路径的个数,翻译错了。

vector<int> v[100010];

void bfs(int root, int depth) {
    if (v[root].size() == 0) {
        if (maxPrice < depth) {
            maxPrice = depth;
            maxNumber = 1;
        } else if (maxPrice == depth) {
            maxNumber++;
        }
        return;
    }
    for (int i = 0; i < v[root].size(); ++i) {
        bfs(v[root][i], depth + 1);
    }
}

用一个vector数组把所有儿子串起来,遍历访问即可。

1102

输入详情:每一个输入包含了一个测试样例。对于每一个例子,第一行给出一个正整数,也及是树的总节点数,因此,节点编号从0到N-1,然后下面N行每一行对应节点0到N-1,每一行给出左右子树。如果子树不存在,用-来代替,每一对孩子用空格分离。

输出详情:对于每一个样例,第一行打印翻转树的层序遍历序列,然后第二行打印翻转树的中序遍历序列,用空格隔开,最后不能有空格。

这个题目就非常简单了,唯一的考点就是交换两树的左右子树,直接后序遍历交换就好了,释放树的内存也是后序遍历实现。

    for (int i = 0; i < n; ++i) {
        array[i].val = i;
        string left, right;
        cin >> left >> right;
        if (left == "-") {
            array[i].leftChild = nullptr;
        } else {
            array[i].leftChild = &array[string2Number(left)];
            array[string2Number(left)].parent = i;
        }
        if (right == "-") {
            array[i].rightChild = nullptr;
        } else {
            array[i].rightChild = &array[string2Number(right)];
            array[string2Number(right)].parent = i;
        }
    }

创建树和前面几个题目一样。

void postExchange(TreeNode root) {
    if (root) {
        postExchange(root->leftChild);
        postExchange(root->rightChild);

        TreeNode temp = root->leftChild;
        root->leftChild = root->rightChild;
        root->rightChild = temp;
    }
}

1106

一条供应链网络由零售商,经销商,供应商组成,每一总角色在这条网络(产品从生产者到消费者)中都起到相应的作用。从根节点的供应者开始,每个人从供应商以P的价格购买,以比P价格高上百分之r的价格卖给经销商或者是零售商。只有零售商才会面对客户,假设每一个成员只有一个提供者,而且没有循环。

输出详情:每一个输入包含一个测试样例。对于每一个样例,第一行包含一个正整数,标识供应链中成员总数,P标识根供应者的价格,也就是初始价格。r是比率,每经过一个经销商或者是零售商价格需要提升r比率。接下来N行中,每一行描述的格式:K,ID,......。第i行中Ki表示总共有Ki个接受者,其实就是说第i号的提供者有这么多个接受者。中间空格隔开。

输出详情:对于每一个测试样例,打印出零售商的最低价格,也就是最后一个`叶子的最低价格,精确到四位小数,有多少个零售商可以拿到最低价格。

读完题,一看就知道BFS,和前面那道题没有什么区别。

void BFS(int root, int depth, treeNode *array) {

    if (depth > minDepth && minNumber > 0) {
        return;
    }

    if (array[root].childen.size() == 0) {
        if (depth < minDepth) {
            minDepth = depth;
            minNumber = 1;
        } else if (depth == minDepth) {
            minNumber++;
        }
        return;
    }
    for (int i = 0; i < array[root].childen.size(); ++i) {
        BFS(array[root].childen[i], depth + 1, array);
    }
}

仅仅修改此处即可。不过值得注意的是,我一开始是创建了一颗树,后来发现超时,我一开始还以为是递归调用超时,于是我添加了:

    if (depth > minDepth && minNumber > 0) {
        return;
    }

如果已经找到了一个更短的,那么如果还有,要么和其相同,要么更短,所以如果还有比他长的直接去掉。但是加上后PAT评测的时间有减少,但是还是有两个数据是段错误,修改一下,把一些多余数据去掉就可以了。推测原因应该是内存超限了。

1115

这个题目就不翻译了,非常简单,就要你找倒数第一和倒数第二层的节点数加起来。层序遍历是最为适合的了,BFS也可以。关键有几个地方,构建树:

TreeNode insert(TreeNode root, int num) {
    if (root) {
        if (root->val < num) {
            root->rightChild = insert(root->rightChild, num);
        } else {
            root->leftChild = insert(root->leftChild, num);
        }
        return root;
    } else {
        root = new treeNode;
        root->val = num;
        root->leftChild = root->rightChild = nullptr;
        return root;
    }
}

在树的结构中添加一个层次属性,记录属于第几层。

void level(TreeNode root) {
    fill(depth, depth + MAX, 0);
    queue<TreeNode> Queue;
    Queue.push(root);
    while (!Queue.empty()) {
        TreeNode cur = Queue.front();
        Queue.pop();
        depth[cur->depth]++;
        maxDepth = ((maxDepth > cur->depth) ? maxDepth : cur->depth);
        if (cur->leftChild) {
            cur->leftChild->depth = cur->depth + 1;
            Queue.push(cur->leftChild);
        }
        if (cur->rightChild) {
            cur->rightChild->depth = cur->depth + 1;
            Queue.push(cur->rightChild);
        }
    }
}

每一次取出节点的时候顺便直接存进数组里面计数,免得害得遍历一次数组。水题一道。

1119

假设在二叉树中所有的关键字都是互不相同的正整数。一颗独一无二的二叉树可以由一对后序和中序遍历序列得到,或者是前序和中序得到。但是,如果只给了后续和前序遍历,那么对应的二叉树并非是唯一的。

现在给一串后序和中序遍历序列,你应该要输出对应的中序遍历的序列,如果此树不唯一,只需要输出他们其中一个即可。

输入详情:每一个输入包含一个测试样例,对于每一个样例,第一个是一个正整数,表示整个二叉树有多少个节点。第二行给出前序遍历序列,第三行给出后续遍历序列,所有的数字之间右空格分隔。

输出详情:对于每一个测试样例,如果树是唯一的,输出yes,如果不是,输出no。下一行输出中序遍历序列。如果解不是唯一的,任何答案都可以。保证至少有一个解。

这个题目第一眼看到是一点思路都没有,上了考场标准0分。首先分析一下前序遍历和后续遍历。前序遍历:根,左子树,右子树;后序遍历:左子树,右子树,根。那么如果这一棵树都有左右子树,那么这棵树就是唯一的,如果这棵树只有左子树,或者右子树,那就有可能有多种情况,这唯一的一棵树可以在左边也可以在右边。这也就是为什么不能唯一确定的原因,这个问题在考408的时候都没有深究。

那么关键就是切分了:

TreeNode create(int preL, int preR, int postL, int postR, int *preSequences, int *postSequences) {
    if (preL > preR) {
        return nullptr;
    }
    TreeNode root = new treeNode;
    root->val = preSequences[preL];
    root->leftChild = root->rightChild = nullptr;
    if (preL == preR) {
        return root;
    }

如果如果只有一个元素,说明就是一个节点,没有左右子树,直接返回。

    if (k - preL > 1) {
        root->leftChild = create(preL + 1, k - 1, postL, postL + k - preL - 2, preSequences, postSequences);
        root->rightChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
    } else {
        flag = false;
        root->leftChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
    }

如果发现包括根节点在内是大于1的,那么说明存在左右子树,那么肯定唯一,如果不是大于1,那说明只有一颗子树,放左放右都可以。最后遍历即可。

1083

给出一段数字,你应该可以用他们组成最小的数字,举个例子,我们组成许多数字如32-321-0229-87or0229-321-3214等等不同组成方式的数字段。

这个题目真的非常简单,之前在洛谷刷过差不多的。主要是几个字符串比较的情况,如123 1230,如果是这样,排序必须是1230123,因为最后的0是小于前面的第一个数1的,但如果是123 1235,那么就要倒过来了,1231235。其实就是贪心就好了。我也不知道为什么这个题目会归类到树这一块。

int cmp(string a, string b) {
    return a + b < b + a;
}

这句就是最关键的了,注意一些特殊情况,当全是0的时候要输出0即可。之前就是因为直接把打头的0去掉,导致如果result = 0那么什么都不输出。

1147

水题一道,题目直接给出是完全二叉树了,直接用数组表示即可。

bool isHeap(int *array, int n, bool maxHeap) {
    for (int i = 1; i <= n / 2; ++i) {
        int left = i * 2;
        int right = left + 1;
        if (left <= n) {
            if (maxHeap) {
                if (array[left] > array[i]) {
                    return false;
                }
            } else {
                if (array[left] < array[i]) {
                    return false;
                }
            }
        }

        if (right <= n) {
            if (maxHeap) {
                if (array[right] > array[i]) {
                    return false;
                }
            } else {
                if (array[right] < array[i]) {
                    return false;
                }
            }
        }
    }
    return true;
}

考查一下是否符合堆的要求即可。

1151

这个题目写出来本以为胜券在握,这个规律很好找,前序遍历是根左右,中序遍历是左根右,那么在中序遍历里面给出的两个关键字的根一定在两个关键字之间,比如中序遍历7 2 3 4 6 5 1 8,找26的最短祖先,祖先看定在3,4之间。对于前序遍历,祖先肯定在26的前面,以此类推就好了。

所以首要一步就是要找到当前两个关键字的位置,然后看他中间的数是不是在前序遍历的那两个关键字的前面即可。一开始是直接遍历找位置,结果超时了。

//        map<int, bool> map_match;
//
//        int first, second;
//
//        if (aIndex > bIndex) {
//            first = bIndex;
//            second = aIndex;
//        } else {
//            first = aIndex;
//            second = bIndex;
//        }
//
//        for (int j = first; j <= second; ++j) {
//            map_match[inOrder[j]] = true;
//        }
//
//        for (int l = 0; l <= aPreIndex && l <= bPreIndex; ++l) {
//            if (map_match[preOrder[l]]) {
//                if (preOrder[l] != a && preOrder[l] != b) {
//                    cout << "LCA of " << a << " and " << b << " is " << preOrder[l] << "." << endl;
//                    break;
//                } else if (preOrder[l] == a) {
//                    cout << a << " is an ancestor of " << b << "." << endl;
//                    break;
//
//                } else if (preOrder[l] == b) {
//                    cout << b << " is an ancestor of " << a << "." << endl;
//                    break;
//
//                }
//            }
//        }

超时的想法是先把中序遍历里面的在关键字之间的变量都存在一个map里面,然后遍历前序遍历直到遇到关键字,结果超时了。在输入的时候,就应该事先把遍历的位置用map存下来,然后就只需要遍历一次了:

//
// Created by GreenArrow on 2020/3/15.
//
#include <iostream>
#include <map>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    int preOrder[n];
    int inOrder[n];

    map<int, int> positionPre, positionIn;

    for (int i = 0; i < n; ++i) {
        cin >> inOrder[i];
        positionIn[inOrder[i]] = i;
    }

    for (int j = 0; j < n; ++j) {
        cin >> preOrder[j];
        positionPre[preOrder[j]] = j;
    }

    for (int k = 0; k < m; ++k) {

        int a, b;
        cin >> a >> b;

        int aIndex = -1;
        int bIndex = -1;
        int aPreIndex = -1;
        int bPreIndex = -1;

        if (positionIn.count(a)) {
            aIndex = positionIn[a];
        }
        if (positionIn.count(b)) {
            bIndex = positionIn[b];
        }

        if (aIndex == -1 && bIndex == -1) {
            cout << "ERROR: " << a << " and " << b << " are not found." << endl;
            continue;
        } else if (aIndex != -1 && bIndex == -1) {
            cout << "ERROR: " << b << " is not found." << endl;
            continue;
        } else if (aIndex == -1) {
            cout << "ERROR: " << a << " is not found." << endl;
            continue;
        }

        if (a == b) {
            cout << a << " is an ancestor of " << b << "." << endl;
            continue;
        }


        for (int i = 0; i < n; ++i) {
            int temp = preOrder[i];
            int inPosition = positionIn[temp];

            if (temp == a) {
                cout << a << " is an ancestor of " << b << "." << endl;
                break;
            } else if(temp == b){
                cout << b << " is an ancestor of " << a << "." << endl;
                break;
            }

            if(inPosition > aIndex && inPosition < bIndex){
                cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
                break;
            } else if(inPosition > bIndex && inPosition < aIndex){
                cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
                break;
            }
        }

1110

这个题目想了挺久的,有点意思,完全二叉树的数组是全满的,所以只需要看看数组是不是全部能访问就好了。首先建树找根节点:

    for (int i = 0; i < n; ++i) {
        string left, right;
        cin >> left >> right;
        if (left == "-") {
            array[i].left = -1;
        } else {
            array[i].left = string2number(left);
            father[array[i].left] = i;
        }
        if (right == "-") {
            array[i].right = -1;
        } else {
            array[i].right = string2number(right);
            father[array[i].right] = i;
        }
    }

    int root = -1;
    for (int j = 0; j < n; ++j) {
        if (father[j] == -1) {
            root = j;
        }
    }

father的用处就是看看是不是根节点而已。没有什么太大用处,接着就是遍历填数组了,用前中后序遍历填写都可以,这里还是用层次遍历好了:

int level(node *array, int root, int *array_tree) {
    queue<int> Queue;
    Queue.push(root);
    array[root].index = 0;
    array_tree[array[root].index] = 1;
    vector<int> sequences;
    while (!Queue.empty()) {
        int cur = Queue.front();
        sequences.push_back(cur);
        Queue.pop();
        if (array[cur].left != -1) {
            Queue.push(array[cur].left);
            array_tree[array[cur].index * 2 + 1] = 1;
            array[array[cur].left].index = array[cur].index * 2 + 1;
        }
        if (array[cur].right != -1) {
            Queue.push(array[cur].right);
            array_tree[array[cur].index * 2 + 2] = 1;
            array[array[cur].right].index = array[cur].index * 2 + 2;
        }
    }

    return sequences[sequences.size() - 1];
}

然后只要看看遍历过的数组有没有空的,有空的那就不是完全二叉树了。

1020

给定后序遍历和中序遍历求前序遍历,这个考408的时候就写过了,水题一道,直接上代码。

//
// Created by GreenArrow on 2020/2/21.
//

#include <iostream>
#include <queue>

using namespace std;

typedef struct node {
    int data;
    node *left;
    node *right;
} node;

node *create(int postl, int postr, int inl, int inr, int *post, int *in) {

    if (postl > postr) {
        return nullptr;
    }

    node *root = new node;

    root->data = post[postr];

    int index = 0;
    for (int i = inl; i <= inr; ++i) {
        if (in[i] == post[postr]) {
            index = i;
            break;
        }
    }

    int leftTreeNumber = index - inl;
    int rightTreeNumber = inr - index;

    root->left = create(postl, postl + leftTreeNumber - 1, inl, index - 1, post, in);
    root->right = create(postl + leftTreeNumber, postr - 1, index + 1, inr, post, in);

    return root;


}

void levelOrder(node *root) {
    queue<node *> Queue;
    Queue.push(root);
    int index = 0;
    int arr[10010];
    while (!Queue.empty()) {
        node *next = Queue.front();
        arr[index++] = next->data;
        Queue.pop();
        if (next != nullptr && next->left) {
            Queue.push(next->left);
        }
        if (next != nullptr && next->right) {
            Queue.push(next->right);
        }
    }

    for (int i = 0; i < index; ++i) {
        cout << arr[i];
        if (i != index - 1) {
            cout << " ";
        }
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    int postOrder[n], inOrder[n];
    for (int i = 0; i < n; ++i) {
        cin >> postOrder[i];
    }
    for (int j = 0; j < n; ++j) {
        cin >> inOrder[j];
    }

    node *root = create(0, n - 1, 0, n - 1, postOrder, inOrder);


    levelOrder(root);
}

1043

这个题也是水题,就是麻烦,也就镜像哪里有点麻烦,遍历的时候先遍历右边再遍历左边就好了,代码不贴了,占篇幅。


有关图的题目:1122,1142,1150,1026,1013,1021,1034,1003,1018,1030,1087,1111

1122

这个题目能不能做出来就看你能不能记得简单回路是啥玩意了。简单回路就是在回路序列里面,除了第一个与最后一个顶点相同,其他顶点各不相同;那么哈密顿回路就再加上访问所有节点的条件。访问到所有节点,只有第一个与最后一个节点相同,中间访问的节点只访问一次就叫哈密顿回路。

那么判断的几个条件:

1.总点数是否等于n+1

2.第一项是否等于最后一项

3.相邻节点之间是否能访问

4.是否访问了所有节点

bool Hamilton(int n, int *array, int vertex_n) {
    if (vertex_n + 1 != n) {
        return false;
    }

    bool visited[vertex_n + 1];
    fill(visited + 1, visited + vertex_n + 1, false);

    int pre = array[1];
    visited[pre] = true;
    for (int i = 2; i <= n; ++i) {
        if (chess[pre][array[i]] != 1 && chess[array[i]][pre] != 1 && array[i] != pre) {
            return false;
        }
        pre = array[i];
        visited[pre] = true;
    }

    for (int j = 1; j <= vertex_n; ++j) {
        if (!visited[j]) {
            return false;
        }
    }

    if (array[1] != array[n]) {
        return false;
    }

    return true;
}

1142

这个题目也是水题,遍历就好了,还不超时。首先遍历一遍看看序列之间的数字是否都有通路,其次遍历剩下不再序列里面的点看看能不能加入即可。

string isMaxClique(int vertex_n, int n, int *array) {


    if(n == 0){
        return "Not a Clique";
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (array[i] != array[j] && chess[array[i]][array[j]] == 0) {
                return "Not a Clique";
            }
        }
    }

    for (int k = 1; k <= vertex_n; ++k) {
        bool flag = true;
        if (!visited[k]) {
            for (int i = 1; i <= vertex_n; ++i) {
                if (i == k) {
                    continue;
                }
                if (!visited[i]) {
                    continue;
                }
                if (chess[k][i] != 1) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return "Not Maximal";
            }
        }
    }

    return "Yes";

}

水题一道。

1150

存在一个旅行推销员的问题,给定一个城市列表和这些城市之间的距离,问,哪条最短的路能够访问所有的城市并且最后能回到出发的城市?这是哪个NPhard的问题,也就是指示复杂度类型的问题,在运筹学研究和计算机科学理论研究上有很重要的意义。

在这个问题里,你应该要从这些城市列表里面找到一个循环,这个循环是旅行者问题的解。

输入详情:每一个输入包含一个测试样例。对于每一个案例,第一行给出两个正整数,分别是城市的数量以及边数。接下来是M行,每一个描述一条边,边的格式如下:城市1,城市2,距离。城市编号从1到N且距离为正数不超过100。接下来一行给出正整数K,路径的数量,紧接着K行描述路径,路径格式为n,C1,C2......。

输出详情:对于每一条路,打印出路径PathX:TotalDist,x是标号,totalDist是路径的总距离。差不多就这样。

这个题目读起来,很繁杂,一开始看的时候还以为他要我算出所有的简单回路。其实也就是遍历操作即可。和前面一道图的题目类似,注意一些细节操作即可,水题一道。

int getClassification(int vertex_n, int n, int *array, int &classification) {
    int pre = array[0];
    int sum = 0;
    int result = 0;
    for (int i = 1; i < n; ++i) {
        if (chess[pre][array[i]] != INT_MAX) {
            sum += chess[pre][array[i]];
            pre = array[i];
        } else {
            result = INT_MAX;
            classification = 2;
            return result;
        }
    }


    if (array[0] != array[n - 1]) {
        classification = 2;
        result = sum;
        return result;
    }

    bool flag2 = false;
    for (int j = 1; j <= vertex_n; ++j) {
        if (visited[j] == 0) {
            classification = 2;
            result = sum;
            return result;
        }

        if (visited[j] >= 2) {
            if (j == array[0] && visited[j] > 2) {
                flag2 = true;
            }

            if (j != array[0] && visited[j] > 1) {
                flag2 = true;
            }
        }

    }

    if (flag2) {
        classification = 3;
        result = sum;
        return result;
    }

    classification = 1;

    result = sum;
    return result;


}

1126

在图论中,一条路径如果能访问每条边一次就叫做欧几里得路径。相同的,一条欧几里得环一条起点和终点相同的欧几里得路径。在1736年,欧拉等人第一次在解决著名的七....问题是提出。如果一个图是联通图并且所有的顶点的度为偶数,那么它会存在一条欧几里得环,这样的图我们称为Eulerian。(欧几里得人???)如果此图恰好有两个奇数度的顶点,则所有的欧几里得路径都是从其中一个顶点出发到另一个顶点结束,只有欧几里得路径而没有欧几里得环的图称为semi-Eulerian

输入详情:每一个输入文件包含一个测试样例,每一个案例开头第一行包含两个数字,N和M,分别是顶点总数和边的总数。接下来的M行描述一条边的两端。

输出描述:第一行打印出顶点的度,按照顶点序号递增的次序,第二行输出图的类型。大概就是这样吧。

这个题目很容易瞎了眼,条件有几个,其一连通图,其二度的数量。首先可以用BFS或者DFS判断是否是联通图,然后再判断度的数量即可。先随机找一个点开始BFS,如果一次BFS完成之后所有的点都被访问了,那么这个图就是联通图,看到很多答案都是每一个点都BFS,其实没有必要,仅仅一个点进行BFS即可。

void BFS(int v) {
    visited[v] = true;
    for (int i = 0; i < nodes[v].size(); ++i) {
        if (!visited[nodes[v][i]]) {
            BFS(nodes[v][i]);
        }
    }
}

后面的判断degress奇偶没有很简单,也是水题。

1013

这也是一个连通图问题,给出n个城市,m条路,问你如果这个城市消失了,需要添加多少条道路才能联通。也是个水题,你把当前要消失的城市包括其有关路径都去掉,然后看看有多少个联通分量,有多少个联通分量就证明有多少个地区是分开的,然后减一就是公路的数量。一开始的做法是复制一份新的地图,把敌对城市去掉,超时了,然而我这么做是多余的,完全可以在深度遍历的时候忽略敌对城市即可。

    for (int k = 0; k < K; ++k) {
        fill(visited, visited + N + 1, false);
        int city;
        scanf("%d", &city);

        visited[city] = true;
        int index = 0;
        for (int l = 1; l <= N; ++l) {
            if (!visited[l]) {
                BFS(l, city);
                index++;
            }
        }

直接把敌对城市设置成已经访问即可,这样BFS不会去寻找已经访问的节点。

1021

如果一个图是联通的而且又没有环,那么就可以看成是一颗树。树的高度就依赖于选择的根是哪一个点。现在要求你找出高度最高的树的根,这样的根称为最深根。

输入详情:每一个输入包含一个测试样例,对于每一个样例,第一行一个正整数,表示顶点的数量,因此,顶点编号从1到N,接下来N-1行描述边。

输出详情:对于每一个测试样例,打印出深的根,如果根不是唯一,打印出所有的根,并按照升序排列。如果不是树,打印出联通分量的个数。

考查深度优先和联通分量,也是水题,BFS遍历查找最深的根,同时BFS把联通分量给找出来,因为查找最深的根和查找联通分量是可以合在一起,关键就是怎么合起来了。修改一下BFS,让其返回最深的层次:

void BFS(int v, int depth) {
    visited[v] = true;


    bool flag = true;
    for (int i = 0; i < graph[v].size(); ++i) {
        int u = graph[v][i];
        if (!visited[u]) {
            flag = false;
            BFS(u, depth + 1);
        }
    }

    if (flag) {
        if (max_BFS < depth) {
            max_BFS = depth;
        }
    }
}

每一次就看看当前节点的下一个节点是不是全部都访问过了,如果都访问过了那就说明到底了,对比之前的然后返回。完成后注意清空visited:

    for (int j = 1; j <= N; ++j) {
        fill(visited, visited + N + 1, false);
        max_BFS = INT_MIN;
        BFS(j, 0);

每一次完成需要清空,需要遍历所有的点找到最深的根。顺便在第一次BFS遍历的时候看看是否有访问到了所有的节点,如果没有,那就没有必要再找最深的点了,直接找联通分量了:

    int max = INT_MIN;
    int index_ = 0;
    bool flag = false;
    for (int j = 1; j <= N; ++j) {
        fill(visited, visited + N + 1, false);
        max_BFS = INT_MIN;
        BFS(j, 0);
        //cout << max_BFS << endl;
        index_++;
        if (!flag)
            for (int i = 1; i <= N; ++i) {
                if (!visited[i]) {
                    flag = true;
                    //不联通
                    for (int k = j + 1; k <= N; ++k) {
                        if (!visited[k]) {
                            BFS(k, 0);
                            index_++;
                        }

                        bool connected = true;

                        for (int l = 1; l <= N; ++l) {
                            if (!visited[l]) {
                                connected = false;
                                break;
                            }
                        }

                        if (connected) {
                            cout << "Error: " << index_ << " components" << endl;
                            return 0;
                        }

                    }

                }
            }

1034

警察找到犯罪团伙透明的方法是检查他们的手机,如果在A和B之间存在了电话联系,那么久说A和B是有关系的。关系的权重是定义了双方通话的总时长。一个帮派是指帮派成员超过两个人,并且这些人之间互相都有联系,且通话量超过既定阈值K。在每一个帮派,存在一个通话量权重最高的人,以此人为首。现在给定一些通话列表,你应该团伙以及头目。

一开始没看清题目,以为名字是三个字母相同的,从A-Z,就26个,然后写出来只对了两个点。然后做出来发现不是。我这里使用的是用向量存储图,单独存储边,如果要计算一个图的权重,遍历图中节点相加即可。这里的关系的双向关系,也就是无向图,但是通话量是单向的,在计算联通分量的时候需要按照无向图计算,计算权重的时候要按照有向图的边相加。如果按照上述做法,就麻烦了,我就是这么做的,其实A->B和B->A的权重是可以相加当成一条边计算,然后权重相加的时候只需要加一次就好了,代码优化的地方可以很多,首先就是使用的存储图的结构就可以使用矩阵,然后权重计算不用分开算,相加在一起当成是无向图。

    for (int i = 0; i < n; ++i) {
        string A, B;
        int weight;
        cin >> A >> B >> weight;
        int ANumber = string2number(A), BNumber = string2number(B);

        name[ANumber] = A;
        name[BNumber] = B;

        visited[ANumber] = false;
        visited[BNumber] = false;

        graphs[ANumber].push_back(BNumber);
        graphs[BNumber].push_back(ANumber);

        if (edges.count(ANumber) == 0) {
            vector<edge> e;
            e.emplace_back(BNumber, weight);
            edges[ANumber] = e;
        } else {
            edges[ANumber].push_back(edge(BNumber, weight));
        }

        totalPhone[ANumber] += weight;
        totalPhone[BNumber] += weight;
    }

这块在输入的时候把输入的name给量化了,把所有通过节点的通话量加起来,后面要选择一个团伙的头目需要使用到。边也存储下来,数组下标就是起始点,边存储终点和权值。

void BFS(int v, int &size, int &total, vector<int> &gangs) {
    visited[v] = true;
    for (int i = 0; i < graphs[v].size(); ++i) {
        if (!visited[graphs[v][i]]) {
            
            gangs.push_back(graphs[v][i]);

            total = addEdges(graphs[v][i], total);

            size++;

            BFS(graphs[v][i], size, total, gangs);
        }
    }
}

然后就是调用BFS了,最后还需要进行排序输出。

1003

找最短路径,算出最短路径有多少条,每一个城市会有相应的人员,经过这个城市就可以带走这些人员,在这些最短路径里面最多能带走多少人。

很明显是属于最短路径的问题,最短路径很容易,关键是如何存储下最短路径的条数。可以使用一个Num数组存储,一开始num[source] = 1,代表当前只有这一条路径,当出现了多条路径之后,也就是在更新到达路径的时候d[v]如果和之前的是相同的,num[v] += num[source],这样其实模拟了一个乘法增长的过程,因为后面的每一条路增加,其实都是倍数增长。

void Dijikstra(int v, int n) {

    fill(d, d + MAX, INT_MAX);
    fill(visited, visited + MAX, false);
    fill(w, w + MAX, 0);
    fill(num, num + MAX, 0);
    w[v] = people[v];
    num[v] = 1;
    d[v] = 0;

    for (int i = 0; i < n; ++i) {
        int min = INT_MAX;
        int u = -1;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && min > d[j]) {
                min = d[j];
                u = j;
            }
        }

        if (u == -1)
            return;

        visited[u] = true;

        for (int k = 0; k < n; ++k) {
            if (!visited[k] && chess[u][k] != INT_MAX) {

                if (d[k] > d[u] + chess[u][k]) {
                    d[k] = d[u] + chess[u][k];
                    w[k] = w[u] + people[k];
                    num[k] = num[u];
                } else if (d[k] == d[u] + chess[u][k]) {
                    num[k] += num[u];
                    if (w[u] + people[k] > w[k]) {
                        w[k] = w[u] + people[k];
                    }
                }

            }
        }

    }

}

就是调用算法即可,如果还需要求路径,只需要用一个vector即可。

1018

大概就是说有几个车站,当容量为一半的时候是最佳状态,现在需要去某一个车站,问你那一条路径是路径最短,填补车辆最少,回收车辆最少。看上去好像是最短路径,但是事实上这是一个深度搜索的问题,最短路径没有办法保证送回和送出的数据是全局最优的。

void DFS(int s, int end, int tempSend, int tempBack, int tempDis) {
    visited[s] = true;
    tempPath.push_back(s);

    if (s == end) {
        if (minDis > tempDis) {
            path = tempPath;
            minDis = tempDis;
            minSend = tempSend;
            minBack = tempBack;
        } else if (minDis == tempDis) {
            if (minSend > tempSend) {
                path = tempPath;
                minSend = tempSend;
                minBack = tempBack;
            } else if (minSend == tempSend) {
                if (minBack > tempBack) {
                    path = tempPath;
                    minSend = tempSend;
                    minBack = tempBack;
                }
            }
        }
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i] && chess[s][i] != INT_MAX) {

            int temp = bikes[i] - capacity / 2;
            int tempB = tempBack;
            int tempS = tempSend;
            if (temp >= 0) {
                tempB += temp;
            } else {
                if (temp + tempB < 0) {
                    tempS -= (temp + tempB);
                    tempB = 0;
                } else {
                    tempB = (temp + tempB);
                }
            }
            DFS(i, end, tempS, tempB, tempDis + chess[s][i]);
            tempPath.pop_back();
            visited[i] = false;
        }
    }
}

有点复杂,用Dijiskra也只能有25分,主要容易搞混的其实就是回收和放出那里:

            int temp = bikes[i] - capacity / 2;
            int tempB = tempBack;
            int tempS = tempSend;
            if (temp >= 0) {
                tempB += temp;
            } else {
                if (temp + tempB < 0) {
                    tempS -= (temp + tempB);
                    tempB = 0;
                } else {
                    tempB = (temp + tempB);
                }
            }

先算出当前点需要多少,如果不需要了还多出盈余,那就加上前面需要送回的;如果缺了,就看看以往需要送回的能不能填补,如果能填补,那么减去已经填补的,如果不能填补,那么就要继续送剩下的。

1030

给出一张旅行者地图,地图给出城市之间的距离已经花费,现在要求你写出程序帮助旅行者决定最短的路径,如果路径最短并非唯一,则给出最小花费,次最小花费的最短路径保证唯一。

输入详情:每一个输入包含了一个测试样例,每一个样例由4个正整数开始,分别是城市数量,告诉公路的数量,起始点和目的地。接下来M行分别就是边的属性。

输出详情:对于每一个测试样例,输出最短路径,路径距离,路径花费。

这个题目相比上面一题要简单不少,就是一个条件而已:

···

void Dijiskra(int s, int n) {

fill(visited, visited + MAX, false);

fill(d, d + MAX, edge(INT_MAX, INT_MAX));

d[s].distance = 0;

d[s].cost = 0;

for (int i = 0; i < n; ++i) {

int u = -1;

int min = INT_MAX;

for (int j = 0; j < n; ++j) {

if (!visited[j] && d[j].distance < min) {

min = d[j].distance;

u = j;

}

}

if (u == -1) {

return;

}

    visited[u] = true;
    for (int k = 0; k < n; ++k) {
        if (!visited[k] && map[u][k].distance != INT_MAX) {
            if (d[k].distance > d[u].distance + map[u][k].distance) {
                d[k].distance = d[u].distance + map[u][k].distance;
                d[k].cost = d[u].cost + map[u][k].cost;
                path[k] = u;
            } else if (d[k].distance == d[u].distance + map[u][k].distance) {
                if (d[k].cost > d[u].cost + map[u][k].cost) {
                    d[k].distance = d[u].distance + map[u][k].distance;
                    d[k].cost = d[u].cost + map[u][k].cost;
                    path[k] = u;
                }
            }
        }
    }
}

}

···

1087

说是有几个城市,城市之间存在路径,通过路径需要花费,而每经过一个城市就可以获得这个城市的快乐值,问路径最短并且能得到最大快乐值的是那一条路。

这个题目比上上题和上上上题都要简单,和上一题难度差不多,其实就是最短路径加上一点条件而已。

void Dijiskra(int s, int n) {
    fill(visited, visited + MAX, false);
    fill(d, d + MAX, INT_MAX);
    fill(happy_total, happy_total + MAX, 0);
    fill(num, num + MAX, 0);
    num[s] = 1;
    d[s] = 0;

    for (int i = 0; i < n; ++i) {
        int u = -1;
        int min = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && d[j] < min) {
                min = d[j];
                u = j;
            }
        }

        visited[u] = true;
        if (u == -1)
            return;

        for (int k = 0; k < n; ++k) {
            if (!visited[k] && chess[u][k] != INT_MAX) {
                if (d[k] > d[u] + chess[u][k]) {
                    d[k] = d[u] + chess[u][k];
                    happy_total[k] = happy_total[u] + name[k].happy;
                    num[k] = num[u];
                    path[k] = u;
                } else if (d[k] == d[u] + chess[u][k]) {
                    num[k] += num[u];
                    if (happy_total[k] < happy_total[u] + name[k].happy) {
                        happy_total[k] = happy_total[u] + name[k].happy;
                        path[k] = u;
                    }
                }
            }
        }
    }
}

1111

这个题目和上一题很类似,两个最短路径就好了,当然了也可以合成一个。首先一个是求路程花费最短的,其次是求时间最短,如果路径最短有多条,那就把时间最短的选出来;如果时间最短的有多条,把经过城市最短的选出来。城市最短可以用一个数组记录,每更新一次,就继承前一点的值加1。

void Dijiskra_t(int s, int n) {
    fill(t, t + MAX, INT_MAX);
    fill(visited_t, visited_t + MAX, false);
    fill(size_time, size_time + MAX, 0);
    size_time[s] = 1;
    t[s] = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        int min = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (!visited_t[j] && t[j] < min) {
                u = j;
                min = t[j];
            }
        }

        visited_t[u] = true;

        for (int k = 0; k < n; ++k) {
            if (!visited_t[k] && chess[u][k].time != INT_MAX) {
                if (t[k] > t[u] + chess[u][k].time) {
                    t[k] = t[u] + chess[u][k].time;
                    size_time[k] = size_time[u] + 1;
                    path_t[k] = u;
                } else if (t[k] == t[u] + chess[u][k].time) {
                    if (size_time[k] > size_time[u] + 1) {
                        size_time[k] = size_time[u] + 1;
                        path_t[k] = u;
                    }
                }
            }
        }
    }
}

DFS,BFS:1004,1021,1018(这两题图论已写)

1004

规定了根节点是1号,让你找出每一层的叶子节点。这个题目也是个水题,但是有些小坑,稍不注意就拿不了30。可以用BFS也可以用DFS,我是用BFS做的,因为直接在树的结构里面加上层次属性就可以了。测试点2有一个小坑,当输入1 0的时候要输出1,因为在BFS里面我的最大层次是初始-1,如果输入1 0那么就不会进入到while循环里面,结果什么都不输出了,所以把最大层次初始化为0就好;还有当n=0的时候不做处理,什么都不输出,需要直接return 0;

int levelOrder(treeNode *root) {
    int max = 0;
    queue<treeNode *> Queue;
    Queue.push(root);
    root->depth = 0;
    while (!Queue.empty()) {
        treeNode *cur = Queue.front();
        Queue.pop();
        if (!cur->children.size())
            depth[cur->depth]++;
        for (int i = 0; i < cur->children.size(); ++i) {
            cur->children[i]->depth = cur->depth + 1;
            Queue.push(cur->children[i]);
            if (cur->children[i]->depth > max) {
                max = cur->children[i]->depth;
            }
        }
    }
    return max;
}

1076

这个题目,一开始看错题目了,把粉丝和up主的关系看反了,第一行3 2 3 4应该是2 3 4号用户关注了1才对。这个题目其实也很简单,就是广度优先就好了:

int BFS(int s, int L, vector<int> graph[MAX]) {
    fill(visited, visited + MAX, false);
    fill(layer, layer + MAX, 0);
    int number = 0;
    layer[s] = 0;
    visited[s] = true;
    queue<int> Queue;
    Queue.push(s);
    while (!Queue.empty()) {
        int cur = Queue.front();
        Queue.pop();
        if (layer[cur] <= L && cur != s) {
            number++;
        }
        for (int i = 0; i < graph[cur].size(); ++i) {
            int v = graph[cur][i];
            if (!visited[graph[cur][i]]) {
                Queue.push(graph[cur][i]);
                layer[graph[cur][i]] = layer[cur] + 1;
                visited[graph[cur][i]] = true;
            }
        }
    }

    return number;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Data Structure_图

    交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

    西红柿炒鸡蛋
  • Data Structure_图图论带权图

    交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

    西红柿炒鸡蛋
  • Data Structure_Visualization

    选择排序很简单,遍历所有元素,查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程,可以用不同颜色代表排...

    西红柿炒鸡蛋
  • 4.7字符串匹配(3)

    用户1147447
  • SDOI 2018二轮题解(除Day2T1)

    然鹅学了不到一个月文化课再回来看OI的东西有一种恍如隔世的感觉,烤前感觉也没啥可复习的,就补一补去年二轮的题吧。

    attack
  • 洛谷P4783 【模板】矩阵求逆(高斯消元)

    attack
  • ZROJ#397. 【18提高7】模仿游戏(爆搜)

    读完题目后不难发现,每次约束的条件相当于是\(b[((x[i] + i) % N + (i / N) % N) % N] = y[i]\)

    attack
  • 挑战程序竞赛系列(80):4.3 2-SAT(4)

    挑战程序竞赛系列(80):4.3 2-SAT(4) 传送门:POJ 2749: Building roads 题意: 阳关路与独木桥:有N个农场,其中A对相...

    用户1147447
  • 【计算机本科补全计划】CCF计算机职业资格认证 2016-04-1/2(俄罗斯方块)详解

    正文之前 果然,上一篇文章结尾的预言果然一语成谶,2016-09-4我果然没做出来。没错,昨晚到现在都没有做出来,当然,也是我做了一晚上心灰意冷,然后去欺负本文...

    用户1687088
  • pHash的Java实现

    此算法中的DCT变换是从 http://blog.csdn.net/luoweifu/article/details/8214959抄过来的,因为这种需要大量的...

    Venyo

扫码关注云+社区

领取腾讯云代金券