PAT甲级刷题记录-(AcWing)-Day12(树 7题)

PAT甲级刷题记录-(AcWing)-Day12(树 7题)

课程来源AcWing
其中AcWing中的题目为翻译好的中文题目

刷题列表

• PAT甲级刷题记录-(AcWing)-Day12(树 7题)
• • 1079 Total Sales of Supply Chain
  • 1090 Highest Price in Supply Chain
  • 1106 Lowest Price in Supply Chain
  • 1155 Heap Paths
  • 1130 Infix Expression
  • 1143 Lowest Common Ancestor
  • 1151 LCA in a Binary Tree
  • 模板

1079 Total Sales of Supply Chain

AcWing链接
PAT链接

#include 
#include 
#include 
#include 

using namespace std;
const int N = 100010;
int n;
double p, r;
int father[N], depth[N];
vector> retailers;

int dfs(int u) {
    if (depth[u] != -1) return depth[u];
    if (father[u] == -1) return 0;
    return depth[u] = dfs(father[u]) + 1;
}

int main() {
    cin >> n >> p >> r;
    memset(father, -1, sizeof father);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        if (k == 0) {
            // 当前是零售商
            int number;
            cin >> number;
            retailers.push_back({i, number});
        } else {
            while (k--) {
                int son;
                cin >> son;
                father[son] = i;
            }
        }
    }
    double res = 0;
    memset(depth, -1, sizeof depth);
    for (auto &item:retailers) {
        int id = item.first;
        int num = item.second;
        res += p * pow(1 + r / 100, dfs(id)) * num;
    }
    printf("%.1lf", res);
    return 0;
}

1090 Highest Price in Supply Chain

AcWing链接
PAT链接

英语单词

解析

注意点
这里的cnt在初始化的时候要为0, 如果只有根节点的话,最大深度就是0,cnt会直接++,产生错误结果2
测试样例如下

1 1.50 1.00
-1

#include 
#include 
#include 

using namespace std;
const int N = 100010;
int father[N], depth[N];
int n;
double p, r;

int dfs(int u) {
    if (depth[u] != -1) return depth[u];
    if (father[u] == -1) return 0;
    return depth[u] = dfs(father[u]) + 1;
}

int main() {
    cin >> n >> p >> r;
    for (int i = 0; i < n; ++i) {
        cin >> father[i];
    }
    memset(depth, -1, sizeof depth);
    int max_depth = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        int dep = dfs(i);
        if (dep > max_depth) { max_depth = dep, cnt = 1; }
        else if (dep == max_depth) cnt++;
    }
    printf("%.2lf %d", p * pow(1 + r / 100, max_depth), cnt);
    return 0;
}

1106 Lowest Price in Supply Chain

AcWing链接
PAT链接

#include 
#include 
#include 
#include 

using namespace std;
const int N = 100010;
int n;
double p, r;
int father[N], depth[N];
vector retailers;

int dfs(int u) {
    if (depth[u] != -1) return depth[u];
    if (father[u] == -1) return 0;
    return depth[u] = dfs(father[u]) + 1;
}

int main() {
    memset(father, -1, sizeof father);
    memset(depth, -1, sizeof(depth));
    cin >> n >> p >> r;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        if (!k) retailers.push_back(i);
        else {
            while (k--) {
                int son;
                cin >> son;
                father[son] = i;
            }
        }
    }
    int min_depth = N, cnt = 0;
    for (auto &id:retailers) {
        int dep = dfs(id);
        if (min_depth > dep) min_depth = dep, cnt = 1;
        else if (min_depth == dep) cnt++;
    }
    printf("%.4lf %d", p * pow(1 + r / 100, min_depth), cnt);
    return 0;
}

1155 Heap Paths

AcWing链接
PAT链接

英语单词

解析

注意点

#include 
#include 

using namespace std;
const int N = 1010;
int n;
int level[N];
bool is_great = false, is_less = false;
vector path;

void dfs(int u) {
    path.push_back(level[u]);
    if (2 * u > n) {
        // u是叶子节点
        cout << path[0];
        for (int i = 1; i < path.size(); ++i) {
            cout << " " << path[i];
            if (path[i - 1] < path[i]) is_less = true;
            else is_great = true;
        }
        cout << endl;
    }
    if (2 * u + 1 <= n)
        // u有右孩子
        dfs(2 * u + 1);
    if (2 * u <= n)
        // u有左节点
        dfs(2 * u);
    path.pop_back();
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)cin >> level[i];
    dfs(1);
    if (is_great && is_less) {
        puts("Not Heap");
    } else if (is_great) puts("Max Heap");
    else puts("Min Heap");
    return 0;
}

1130 Infix Expression

AcWing链接
PAT链接

英语单词

• syntax tree 语法树
• infix expression 插入表达式
• parenthese 括号

解析

注意点
熟悉一下递归输出的写法

#include 
#include 

using namespace std;
const int N = 30;
int n;
string w[N];
int l[N], r[N];
bool father[N], is_leaf[N];

string dfs(int u) {
    string left, right;
    if (l[u] != -1) {
        left = dfs(l[u]);
        if (!is_leaf[l[u]]) left = "(" + left + ")";
    }
    if (r[u] != -1) {
        right = dfs(r[u]);
        if (!is_leaf[r[u]]) right = "(" + right + ")";
    }
    return left + w[u] + right;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        // 记录编号与权值的对应关系,左右孩子编号
        cin >> w[i] >> l[i] >> r[i];
        if (l[i] != -1) father[l[i]] = true;
        if (r[i] != -1) father[r[i]] = true;
        if (l[i] == -1 && r[i] == -1) is_leaf[i] = true;
    }
    // 获取根节点
    int root = 1;
    while (father[root]) root++;
    cout << dfs(root) << endl;
    return 0;
}

1143 Lowest Common Ancestor

AcWing链接
PAT链接

英语单词

解析
使用一个数组映射一下节点的权重与编号
使用爬山法来找共同的祖先
使用前序和中序创建二叉树的过程中,记录每个节点的父亲节点,以及每个节点的深度,为了方便之后的操作

#include 
#include 
#include 

using namespace std;
const int N = 10010;
int m, n;
int pre[N], w[N], in[N];
unordered_map pos;
int p[N], depth[N];

int build(int il, int ir, int pl, int pr, int d) {
    int root = pre[pl];
    int k = pos[w[root]];

    depth[root] = d; //记录每个节点所在的深度是什么
    // 记录孩子的父亲节点值
    if (il < k) p[build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, d + 1)] = root;

    if (k < ir) p[build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr, d + 1)] = root;

    return root;
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < n; ++i) {
        cin >> pre[i];
        w[i] = pre[i];
    }
    sort(w, w + n);
    for (int i = 0; i < n; ++i) {
        in[i] = i;
        pos[w[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        pre[i] = pos[pre[i]];
    }
    build(0, n - 1, 0, n - 1, 0);
    while (m--) {
        int a, b;
        cin >> a >> b;
        if (pos.count(a) && pos.count(b)) {
            int pa = pos[a], pb = pos[b];
            int x = pa, y = pb;
            while (pa != pb) {
                if (depth[pa] < depth[pb]) pb = p[pb]; // pb节点的深度更深,让pb先往上找
                else if (depth[pa] > depth[pb]) pa = p[pa];
                else {
                    //两个相等,一起往上找
                    pa = p[pa];
                    pb = p[pb];
                }
            }
            if (pa != x && pb != y) {
                // 公共的父节点不是他们自己
                printf("LCA of %d and %d is %d.n", a, b, w[pa]);
            } else if (pa == x) {
                printf("%d is an ancestor of %d.n", a, b);
            } else printf("%d is an ancestor of %d.n", b, a);
        } else if (pos.count(a)) printf("ERROR: %d is not found.n", b);
        else if (pos.count(b)) printf("ERROR: %d is not found.n", a);
        else printf("ERROR: %d and %d are not found.n", a, b);


    }
    return 0;
}

1151 LCA in a Binary Tree

AcWing链接
PAT链接

英语单词

解析

注意点
和上一道题一样, 在映射关系那边卡了好久

int root = pre[pl];
int k = pos[w[root]];
或者
int k = root;
一开始错误的写成 int k = pos[root]; // pos中存放的是权值,而root是映射之后的编号,所以出现错误

#include 
#include 
#include 

using namespace std;
const int N = 10010;
int m, n;
int in[N], pre[N], w[N];
unordered_map pos;
int father[N], depth[N];

int build(int il, int ir, int pl, int pr, int d) {
    int root = pre[pl];

    int k = pos[w[root]];
    depth[root] = d;
    if (il < k) father[build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, d + 1)] = root;
    if (k < ir) father[build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr, d + 1)] = root;

    return root;
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
        pos[w[i]] = i;
        in[i] = i;
    }
    for (int i = 0; i < n; ++i) {
        cin >> pre[i];
        pre[i] = pos[pre[i]];
    }

    build(0, n - 1, 0, n - 1, 0);
    while (m--) {
        int a, b;
        cin >> a >> b;
        if (pos.count(a) && pos.count(b)) {
            int pa = pos[a], pb = pos[b];
            int x = pa, y = pb;
            while (pa != pb) {//爬山法找祖先
                if (depth[pa] > depth[pb]) pa = father[pa];
                else if (depth[pa] < depth[pb]) pb = father[pb];
                else pa = father[pa], pb = father[pb];
            }
            if (pa != x && pb != y) printf("LCA of %d and %d is %d.n", a, b, w[pa]);
            else if (pb != x)printf("%d is an ancestor of %d.n", b, a);
            else printf("%d is an ancestor of %d.n", a, b);

        } else if (pos.count(a)) printf("ERROR: %d is not found.n", b);
        else if (pos.count(b)) printf("ERROR: %d is not found.n", a);
        else printf("ERROR: %d and %d are not found.n", a, b);
    }
    return 0;
}

模板

AcWing链接
PAT链接

英语单词

解析

注意点