PAT 2020年秋考解答

7-1 Panda and PP Milk (20分)

这道题杀死了不少同学的心态，但是如果想到方法了就特别简单。
简单说下做法，一共对全表进行两次扫描，第一次从左到右，第二次从右到左，每次扫描时，如果后面熊猫比前面重，则供奶量+1（以2、3、4计，最后统一乘100)如果体重持平，则保持不变，体重减轻，则供奶量恢复为2，从左向右扫描满足所有熊猫看到自己左边的熊猫都会满意，从右向左满足右边熊猫，对每个熊猫取两次扫描中的较大值，即为答案。

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 10005;
const int WMAX = 205;
int main() {
    int n, wight[NMAX], milk_l[NMAX], milk_r[NMAX];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> wight[i];
    }
    int pre, now_milk;
    now_milk = 2;
    pre = WMAX;
    for (int i = 0; i < n; i++) {
        // 左向右扫
        if (wight[i] > pre) {
            now_milk++;
        } else if (wight[i] == pre) { ; //体重相等供奶量保持不变
        } else {
            now_milk = 2;
        }
        milk_l[i] = now_milk;
        pre = wight[i];
    }
    now_milk = 2;
    pre = WMAX;
    for (int i = n - 1; i >= 0; i--) {
        // 右向左扫
        if (wight[i] > pre) {
            now_milk++;
        } else if (wight[i] == pre) { ;
        } else {
            now_milk = 2;
        }
        milk_r[i] = now_milk;
        pre = wight[i];
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += max(milk_l[i], milk_r[i]); // 取较大者
    }
    cout << sum * 100;
    return 0;
}

至于这题是怎么想到的？我也不知道。可能是考场上的灵光一现吧，要是换个时间再来一次，我可能也想不到这样做了。

7-2 How Many Ways to Buy a Piece of Land (25分)

比较简单

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 10005;
int main() {
    int n, m;
    int pieces[NMAX];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> pieces[i];
    }
    int ans = 0;
    int i = 0, j = 0;
    int total = 0;
    while (i < n) {
        while (j < n && total + pieces[j] <= m) {
            total += pieces[j++];
        }
        ans += j - i;
        total -= pieces[i++];
    }
    cout << ans;
    return 0;
}

7-3 Left-View of Binary Tree (25分)

先建树，再层序遍历，考基本功了

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 25;

struct TNode {
    int val;
    int level;
    TNode *left;
    TNode *right;
};

int pre[NMAX], in[NMAX];

TNode *new_node(int val) {
    TNode *node = new TNode;
    node->val = val;
    node->level = -1;
    node->left = node->right = nullptr;
    return node;
}

TNode *built_tree(int in_s, int in_e, int pre_s, int pre_e) {
    if (in_s > in_e)
        return nullptr;
    int mid;
    for (mid = in_s; mid <= in_e; mid++) {
        if (in[mid] == pre[pre_s])
            break;
    }

    TNode *node = new_node(pre[pre_s]);
    node->left = built_tree(in_s, mid - 1, pre_s + 1, pre_s + mid - in_s);
    node->right = built_tree(mid + 1, in_e, pre_s + mid - in_s + 1, pre_e);
    return node;
}


vector<int> ans;

void level_travel(TNode *node) {
    queue<TNode *> q;
    int now_level = 0;
    node->level = 1;
    q.push(node);
    while (!q.empty()) {
        node = q.front();
        q.pop();
        if (node->level != now_level) {
            ans.push_back(node->val);
            now_level = node->level;
        }

        if (node->left) {
            node->left->level = node->level + 1;
            q.push(node->left);
        }
        if (node->right) {
            node->right->level = node->level + 1;
            q.push(node->right);
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> in[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
    }
    TNode *root = built_tree(0, n - 1, 0, n - 1);

    level_travel(root);
    int l = ans.size();
    if (l > 0) {
        cout << ans[0];
    }
    for (int i = 1; i < l; i++) {
        cout << " " << ans[i];
    }
    return 0;
}

7-4 Professional Ability Test (30分)

先判断是否有环（推荐拓扑排序，DFS也许），然后djs算法，纯考基本功，代码量有点大

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1005;
const int MAX_DIS = 500;

struct Edge {
    int v;
    int score, daijinquan;

    Edge() {};

    Edge(int _v, int _score, int _daijinquan) {
        v = _v;
        score = _score;
        daijinquan = _daijinquan;
    }
};

vector<Edge> graph[NMAX];
int in[NMAX], in_buff[NMAX];
int n, m;

void not_consist() {
    // 有环，直接判断
    cout << "Impossible." << endl;
    int k;
    cin >> k;
    while (k--) {
        int node;
        cin >> node;
        if (in[node] == 0)
            printf("You may take test %d directly.
", node);
        else
            printf("Error.
");
    }
}

//vector<int> pre[NMAX];
int pre[NMAX];

void Dijkstra() {
    bool visited[NMAX];
    int dis_score[NMAX];
    int dis_daijinquan[NMAX];
    fill(visited, visited + NMAX, false);
    fill(dis_score, dis_score + NMAX, MAX_DIS);
    fill(dis_daijinquan, dis_daijinquan + NMAX, 0);
    //dis_score[n]=0;
    //int node;
    for (Edge e:graph[n]) {
        dis_score[e.v] = dis_daijinquan[e.v] = 0;
        pre[e.v] = n;
    }
    while (true) {
        int min_node = n;
        int min_dis = MAX_DIS;
        for (int i = 0; i < n; i++) {
            if (visited[i])
                continue;

            if (dis_score[i] < min_dis) {
                min_dis = dis_score[i];
                min_node = i;
            } else if (dis_score[i] == min_dis) {
                if (dis_daijinquan[i] > dis_daijinquan[min_node])
                    min_node = i;
            }
        }
        if (min_node == n)
            break;
        visited[min_node] = true;
        for (Edge e:graph[min_node]) {
            if (min_dis + e.score < dis_score[e.v]) {
                pre[e.v] = min_node;
                dis_score[e.v] = min_dis + e.score;
                dis_daijinquan[e.v] = dis_daijinquan[min_node] + e.daijinquan;
            } else if (min_dis + e.score == dis_score[e.v]) {
                if (dis_daijinquan[min_node] + e.daijinquan > dis_daijinquan[e.v]) {
                    pre[e.v] = min_node;
                    dis_daijinquan[e.v] = dis_daijinquan[min_node] + e.daijinquan;
                }
            }
        }
    }
}

void consist() {
    // 无环 Djs算法
    cout << "Okay." << endl;
    Dijkstra();
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int dst;
        cin >> dst;

        if (pre[dst] == n) {
            printf("You may take test %d directly.
", dst);
        } else {
            vector<int> path;
            while (dst != n) {
                path.push_back(dst);
                dst = pre[dst];
            }
            int l = path.size();
            printf("%d", path[l - 1]);
            for (int j = l - 2; j >= 0; j--) {
                printf("->%d", path[j]);
            }
            printf("
");
        }
    }
}

bool check() {
    // 判断是否有环
    bool visited[NMAX];
    fill(visited, visited + NMAX, false);
    for (int i = 0; i < n; i++) {
        int node = 0;
        for (; node < n; node++) {
            if (!visited[node] && in[node] == 0) {
                break;
            }
        }
        if (node == n)
            break;
        visited[node] = true;
        for (Edge t:graph[node]) {
            in[t.v]--;
        }
    }
    for (int i = 0; i < n; i++) {
        if (in[i])
            return false;
    }
    return true;
}

int main() {

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, s, d;
        cin >> u >> v >> s >> d;
        in[v]++;
        in_buff[v]++;// 入读保存两份，一份用来判环，一份判断是否是启示节点（一开始入读就是0的节点）
        graph[u].push_back(Edge(v, s, d));
    }

    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            // 用节点n作为总起始节点，连接所有起始入度为零的节点，将图变成单源的
            graph[n].push_back(Edge(i, 0, 0));
        }
    }
    if (check())
        consist();
    else
        not_consist();
    return 0;
}