关于算法:PAT甲级2020年秋季考试题解

7-1 Panda and PP Milk (20 分)

PP milk（盆盆奶）is Pandas’ favorite. They would line up to enjoy it as show in the picture. On the other hand, they could drink in peace only if they believe that the amount of PP milk is fairly distributed, that is, fatter panda can have more milk, and the ones with equal weight may have the same amount. Since they are lined up, each panda can only compare with its neighbor(s), and if it thinks this is unfair, the panda would fight with its neighbor.

Given that the minimum amount of milk a panda must drink is 200 ml. It is only when another bowl of milk is at least 100 ml more than its own that a panda can sense the difference.

Now given the weights of a line of pandas, your job is to help the breeder（饲养员）to decide the minimum total amount of milk that he/she must prepare, provided that the pandas are lined up in the given order.

Each input file contains one test case. For each case, first a positive integer n (≤10^4) is given as the number of pandas. Then in the next line, npositive integers are given as the weights (in kg) of the pandas, each no more than 200. the numbers are separated by spaces.

For each test case, print in a line the minimum total amount of milk that the breeder must prepare, to make sure that all the pandas can drink in peace.

10
180 160 100 150 145 142 138 138 138 140

The distribution of milk is the following:

400 300 200 500 400 300 200 200 200 300

参考代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int n;
int a[maxn],val[maxn];
int main(){scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    int cur=10000;
    for(int i=1; i<=n; ++i){if(a[i]>cur) val[i]=val[i-1]+100;
        else if(a[i]==cur) val[i]=val[i-1];
        else val[i]=200;
        cur=a[i];
    }
    cur=10000;
    for(int i=n; i>=1; --i){if(a[i]>cur)    val[i]=max(val[i+1]+100,val[i]);
        else if(a[i]==cur)  val[i]=max(val[i],val[i+1]);
        else val[i]=max(val[i],200);
        cout << val[i] << endl;
        cur=a[i];
    }
    int ans=0;
    for(int i=1; i<=n; ++i) ans+=val[i];
    printf("%d\n",ans);
    return 0;
}

7-2 How Many Ways to Buy a Piece of Land (25 分)
The land is for sale in CyberCity, and is divided into several pieces. Here it is assumed that each piece of land has exactly two neighboring pieces, except the first and the last that have only one. One can buy several contiguous（间断的）pieces at a time. Now given the list of prices of the land pieces, your job is to tell a customer in how many different ways that he/she can buy with a certain amount of money.

Each input file contains one test case. Each case first gives in a line two positive integers: N (≤10^4), the number of pieces of the land (hence the land pieces are numbered from 1 to N in order), and M (≤10^9), the amount of money that your customer has.

Then in the next line, N positive integers are given, where the i-th one is the price of the i-th piece of the land.

It is guaranteed that the total price of the land is no more than 109.

For each test case, print the number of different ways that your customer can buy. Notice that the pieces must be contiguous.

5 85
38 42 15 24 9

The 11 different ways are:

参考代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int n,m;
int a[maxn],pref[maxn];
int main(){scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]),pref[i]=pref[i-1]+a[i];
    int ans=0;
    for(int i=1; i<=n; ++i){
        int L=i,R=n;
        while(L<R){int mid=(L+R+1)>>1;
            if(pref[mid]-pref[i-1]<=m) L=mid;
            else R=mid-1;
        }
        if(pref[L]-pref[i-1]<=m) ans+=L-i+1;
    }
    printf("%d\n",ans);
    return 0;
}

7-3 Left-View of Binary Tree (25 分)
The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is {1, 2, 3, 4, 5}

Given the inorder and preorder traversal sequences of a binary tree, you are supposed to output its left-view.

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20), which is the total number of nodes in the tree. Then given in the following 2 lines are the inorder and preorder traversal sequences of the tree, respectively. All the keys in the tree are distinct positive integers in the range of int.

For each case, print in a line the left-view of the tree. All the numbers in a line are separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

8
2 3 1 5 4 7 8 6
1 2 3 6 7 4 5 8

1 2 3 4 5

参考代码：

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

struct node{
    int data, level;
    node *left, *right; // 此处命名留神 * 和前面的俩连在一起
};

int n;
int in[25], pre[25];
bool level_print[25] = {false};

node* build(int inL, int inR, int preL, int preR){if(inL > inR)   return NULL;
    node* root = new node;
    int pos = inL;
    for(;pos <= inR; pos++){if(in[pos] == pre[preL])    break;
    }
    root->data = pre[preL];
    root->left = build(inL, pos-1, preL+1, preL+1+(pos-1-inL));
    root->right = build(pos+1, inR, preR-(inR-pos-1), preR);
    return root;
}

void BFS(node* root){
    queue<node*> q;
    root->level = 1;
    q.push(root);
    printf("%d", root->data);
    level_print[root->level] = true;
    while(!q.empty()){node* top = q.front();
        q.pop();
        if(!level_print[top->level]){printf("%d", top->data);
            level_print[top->level] = true;
        }
        if(top->left != NULL){
            top->left->level = top->level+1;
            q.push(top->left);
        }
        if(top->right != NULL){
            top->right->level = top->level+1;
            q.push(top->right);
        }
    }

}

int main(){scanf("%d", &n);
    for(int i = 0; i < n; i++)  scanf("%d", &in[i]);
    for(int i = 0; i < n; i++)  scanf("%d", &pre[i]);
    node* root = new node;
    root = build(0, n-1, 0, n-1);
    BFS(root);
    return 0;
}

7-4 Professional Ability Test (30 分)
Professional Ability Test (PAT) consists of several series of subject tests. Each test is divided into several levels. Level A is a prerequisite (前置要求)of Level B if one must pass Level A with a score no less than S in order to be qualified to take Level B. At the mean time, one who passes Level A with a score no less than S will receive a voucher（代金券）of D yuans (Chinese dollar) for taking Level B.

At the moment, this PAT is only in design and hence people would make up different plans. A plan is NOT consistent if there exists some test T so that T is a prerequisite of itself. Your job is to test each plan and tell if it is a consistent one, and at the mean time, find the easiest way (with minimum total S) to obtain the certificate of any subject test. If the easiest way is not unique, find the one that one can win the maximum total value of vouchers.

Each input file contains one test case. For each case, the first line gives two positive integers N (≤1000) and M, being the total numbers of tests and prerequisite relations, respectively. Then M lines follow, each describes a prerequisite relation in the following format:

T1 T2 S D

where T1 and T2 are the indices (from 0 to N−1) of the two distinct tests; S is the minimum score (in the range (0, 100]) required to pass T1 in order to be qualified to take T2; and D is the value of the voucher (in the range (0, 500]) one can receive if one passes T1 with a score no less than S and plan to take T2. It is guaranteed that at most one pair of S and D are defined for a prerequisite relation.

Then another positive integer K (≤N) is given, followed by K queries of tests. All the numbers in a line are separated by spaces.

Print in the first line Okay. if the whole plan is consistent, or Impossible. if not.

If the plan is consistent, for each query of test T, print in a line the easiest way to obtain the certificate of this test, in the format:

T0->T1->...->T

However, if T is the first level of some subject test (with no prerequisite), print You may take test T directly. instead.

If the plan is impossible, for each query of test T, check if one can take it directly or not. If the answer is yes, print in a line You may take test T directly.; or print Error. instead.

8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7

Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7

Impossible.
You may take test 3 directly.
Error.

思路剖析：
这种 30 分的题目，读题并了解分明题意真的很重要。模拟训练时就因为没有真正读懂导致无奈下手。实现本题次要从两方面动手：1. 判断给定结点是否在环中。2. 寻找入度为零的结点达到每一给定结点的最短门路。（这里刚开始了解错了，不是连着判断，不是实现后一个结点必须先实现后面的结点，而是每一给定结点独自判断寻找最短门路）
一些易错点：给定的通过考试的分数以及所给处分均由两个点来限定，实际意义均是边权，不要想当然地将其中某一个视为点权；拜访某一点不要求入度为零，但某点在环中则不能拜访。个人感觉这有点小问题，因为既然在环中不能被拜访，那么应该有入度为零能力被拜访的要求，否则该环能够被突破（即通过不在环中的前驱关系来突破）。但还是要依据题意来。

判环
办法比拟多，介绍三种：
1. 对每一给定结点进行深搜，并将该结点作为形参穿入每次递归，若在深搜过程中再次遇到该结点，即该结点在环中，不过这种办法对每个结点都要进行一次深搜，比拟耗时。
2. 对整个图进行解决，寻找入度为零的点，删去并对其连贯的另一个结点的入度减一，一直反复这一过程，那么最初入度不为零的点即都在环中。（个别倡议以队列实现，当然遍历每个结点来解决也能够）

寻找最短门路
此次的寻找最短门路与以往有所区别，这里是给定指标结点，寻找一个源点使其门路最短。也即多源点，单指标结点。
几种方向：
1. 逆向思维即可，将该指标结点视为源点进行算法，进行完后再顺次遍历每一个入度为零的结点，找到合乎题意的最短门路。
2. 人为结构一个超级源点，指向所有入度为零的结点，且边权均设置为 0。这样多源点问题就转换为单源点问题。
3. 应用 SPFA 算法，构建队列，将所有入度为零的点入队，且每出队时都看是否有新的入度为零的结点产生，产生则入队。这样，既能够判断是否有环，同时也解决了多源问题。

参考代码：

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

const int maxv = 1010;
const int INF = 0x7fffffff;

int n, m, k;
int in[maxv] = {0}, indegree[maxv] = {0};
int w[maxv], c[maxv], seq[maxv], pre[maxv];
int G[maxv][maxv], money[maxv][maxv];
vector<int> post[maxv];   // 记录后继结点

void SPFA(){
    queue<int> q;
    fill(pre, pre+maxv, -1);
    fill(c, c+maxv, INF);
    fill(w, w+maxv, 0);
    for(int i = 0; i < n; i++){if(!indegree[i]){// 源点初始化并入队
            c[i] = 0;
            w[i] = 0;
            q.push(i);
        }
    }
    while(!q.empty()){int u = q.front();
        q.pop();
        for(int j = 0; j < post[u].size(); j++){int v = post[u][j];
            indegree[v]--;
            if(!indegree[v])   q.push(v);
            if(c[u] + G[u][v] < c[v]){c[v] = c[u] + G[u][v];
                w[v] = w[u] + money[u][v];    // 此处对权值的更新不要忘
                pre[v] = u;
            }else if(c[u] + G[u][v] == c[v]){if(w[u] + money[u][v] > w[v]){w[v] = w[u] + money[u][v];    // 留神不要忘了这句话，即更新最大权值（幸福值）pre[v] = u;
                }
            }
        }
    }
}

int main(){
    int T1, T2, S, D;
    int flag = 1;
    scanf("%d %d", &n, &m);
    fill(G[0], G[0]+maxv*maxv, INF);
    for(int i = 0; i < m; i++){scanf("%d %d %d %d", &T1, &T2, &S, &D);
        indegree[T2]++;
        in[T2]++;
        G[T1][T2] = S;
        money[T1][T2] = D;
        post[T1].push_back(T2);
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++)  scanf("%d", &seq[i]);
    SPFA();
    for(int i = 0; i < k; i++){if(indegree[seq[i]]){
            flag = 0;
            break;
        }
    }
    if(flag){printf("Okay.\n");
        for(int i = 0; i < k; i++){
            vector<int> ans;
            for(int pos = seq[i]; pos != -1; pos = pre[pos]){ans.push_back(pos);
            }
            reverse(ans.begin(), ans.end());
            if(!in[seq[i]]) printf("You may take test %d directly.\n", seq[i]);
            else    for(int j = 0; j < ans.size(); j++)     printf("%d%s", ans[j], j == ans.size()-1 ? "\n":"->");
        }
    }else{printf("Impossible.\n");
        for(int i = 0; i < k; i++){if(!in[seq[i]]) printf("You may take test %d directly.\n", seq[i]);
            else    printf("Error.\n");
        }
    }
    return 0;
}

本次考试几点播种：
1. 英语浏览理解能力真的很重要，题意了解不分明，代码怎么写都不对。
2.#include <bits/stdc++.h> 这个真的好用，一个涵盖所有库。
3. 存储图时，应用邻接表要比应用邻接矩阵节俭很多内存，但应用邻接表时记得要将边的相应信息存到一个构造体外面去。
4. 通过记录前驱来生成最终输入门路时，能够应用深搜来逆序输入，当然应用 reverse 也很简洁。
5.SPFA 算法比 Dijkstra 更简洁，应用范畴也更广，及其举荐应用。

关于算法:PAT甲级2020年秋季考试题解

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Hint:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Hint:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Input Specification:

Output Specification:

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2: