PAT甲級2020年秋季題目記錄分析（全部AC，簡單易懂）

PAT甲級2020年秋季題目記錄分析

題目在官方可以買到，就五塊錢：https://pintia.cn/market/item/1302817001358053376。但是因為有時間限制（3小時候就不能送出了）是以，我是看别的的部落格題目截圖，寫完了，才去買來看看自己對不對的。

1.大熊貓和盆盆奶。

解題思路：

1.把貓從左往右喂一遍，保證每個貓不和自己左邊的吵架。

因為左1貓沒有左鄰居了，他不攀比，直接最少量200.

其餘貓，就看自己體重和左鄰居的關系了，比他重就比他多100，一樣重一樣的奶，輕就最少量200.

2.把貓從右往左喂一遍，保證每個貓不和自己右邊的吵架。

因為右1貓沒有右鄰居了，他不攀比，直接最少量200.

其餘貓，就看自己體重和右鄰居的關系了，比他重就比他多100，一樣重一樣的奶，輕就最少量200.

3.喂完兩遍奶後，每隻熊貓都喂了兩次，取喝的多的那次的量，這隻貓就和左右都不吵架哦了。

代碼：

//
// Created by 江左 on 2021/3/10.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

int main() {
    int n,sum=0;cin>>n;
    vector<int> weight,leftToRight,rightToLeft;
    weight.resize(n);
    leftToRight.resize(n);
    rightToLeft.resize(n);
    for (int i = 0; i < n; ++i)
        cin>>weight[i];
    leftToRight[0]=200;
    for (int i = 1; i < n; ++i) {
       if(weight[i]>weight[i-1])
           leftToRight[i]=leftToRight[i-1]+100;
       else if(weight[i]==weight[i-1])
           leftToRight[i]=leftToRight[i-1];
       else
           leftToRight[i]=200;
    }
    rightToLeft[n-1]=200;
    sum+=max(leftToRight[n-1],rightToLeft[n-1]);
    for (int i = n-2; i >= 0; --i) {
        if(weight[i]>weight[i+1])
            rightToLeft[i]=rightToLeft[i+1]+100;
        else if(weight[i]==weight[i+1])
            rightToLeft[i]=rightToLeft[i+1];
        else
            rightToLeft[i]=200;
        sum+=max(leftToRight[i],rightToLeft[i]);
    }
    cout<<sum;
    return 0;
}
           

2.有多少種方式買連續的島

比較簡單：

代碼

//
// Created by 江左 on 2021/3/9.
//

#include <iostream>
using namespace std;
const int N = 10010;
int n,m;
int sum[N];
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        int x;cin >> x;
        sum[i] = x + sum[i - 1];
    }
    int res = 0;
    for(int i=1,j=0;i<=n;i++)
    {
        while(sum[i] - sum[j] > m)
            j ++ ;
        res += i - j;
    }
    cout << res << endl;
    return 0;
}

           

3.給你一個二叉樹的中序和前序，讓你列印他的left-view。

說白了，就是自上而下，列印每一層最左邊的節點。

解題思路：根據中序和先序，周遊二叉樹的同時把每一個節點押入屬于他的深度集合中。

//
// Created by 江左 on 2021/3/9.
//

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

int in[30],pre[30];
map<int,int> m;
vector<vector<int>> v;
void level(int l,int r,int p,int dep){
    int inRoot=m[pre[p]];
    v[dep].push_back(in[inRoot]);
    if(l<inRoot)
        level(l,inRoot-1,p+1,dep+1);
    if(inRoot<r)
        level(inRoot+1,r,p+1+(inRoot-l),dep+1);
}
int main() {
    int n;cin>>n;v.resize(n+1);
    for (int i = 1; i <= n; ++i) {
        cin>>in[i];
        m[in[i]]=i;
    }
    for (int i = 1; i <= n; ++i) 
        cin>>pre[i];
    level(1,n,1,0);
    int p=0;
    while (!v[p].empty()){
        if(p!=0) cout<<" ";
        cout<<v[p][0];
        p++;
    }
    return 0;
}

           

4.Professional Ability Test

題目又臭又長，人都讀傻了，因為我英語不好，了解起來很困難。

大意是：

PAT，有很多考試，比如你想考B，但是得考A，分數必須大于S，會得到一個D的優惠券。

輸入：給你若幹考試的關系，然後問你如果我想通過某個考試x，需要經曆的流程。

如果關系中有環，則impossible，反之okay，

經曆的流程考試要求，過程中最小的totalS，totalS可能重複，就要最大的totalD。

注意點：編輯器要使用clang，。。。。不知道為什麼g++沒有全對，如果有人知道，請不吝賜教。

還有最後一個節點有時逾時，有時不逾時，很明顯把輸入輸出都改成printf和scanf就一定能過了，但是我懶。

代碼：

#include <iostream>
#include <vector>
using namespace std;
/// 檢查圖是否有自環,應該用拓撲排序
/// 解題方法,找入度為零的點,沒有就輸出NO,有就删除這個點和關聯邊,繼續下一次循環
class Node{
public:
    int cnt=0;//自己入度的個數
    vector<int> GOTO;//由自己發起的,去往的頂點
};

vector<vector<int>> post; //下标為i的節點的入度情況
vector<Node> G;//node集合
int w1[1010][1010];//儲存路徑的S值
int w2[1010][1010];//儲存路徑的D值
int minS=9999999,maxD=-1;
vector<int> temp,res;
void dfs(int root,int sumS,int sumD){
    if(sumS>minS) return;//剪枝
    temp.push_back(root);
    if (post[root].empty()){
        //找到起始根節點了
        if(sumS<minS){
            minS=sumS;
            res=temp;
            maxD=sumD;
        }else if(sumS==minS){
            if(sumD>maxD){
                maxD=sumD;
                res=temp;
            }
        }
        temp.pop_back();
        return;
    }
    for (int i = 0; i < post[root].size(); ++i) {
        dfs(post[root][i],sumS+w1[post[root][i]][root],sumD+w2[post[root][i]][root]);
    }
    temp.pop_back();
}
int main() {
    int n,m;cin>>n>>m;
    post.resize(n);G.resize(n);
    for (int i = 0; i < m; ++i) {
        int a,b;cin>>a>>b>>w1[a][b]>>w2[a][b];
        G[b].cnt++;G[a].GOTO.push_back(b);
        post[b].push_back(a);
    }

    int k;cin>>k;
    vector<int> input;input.resize(k);
    for (int i = 0; i < k; ++i) {
        cin>>input[i];
    }
    //拓撲排序驗證他是否有自環現象,如果有則imp
    bool flag=true;int p=0;
    while (p<G.size()){
        p++;
        bool f= true;
        for (int i = 0; i < G.size(); ++i) {
            if (G[i].cnt==0){
                f=false;
                for (int j = 0; j < G[i].GOTO.size(); ++j) {
                    G[G[i].GOTO[j]].cnt--;
                }
                G[i].cnt=-1;
                break;
            }
        }
        if(f){//自環的标志,沒有了入度為零的點
            flag=false;
            break;
        }
    }
    if(flag){
        //正确完成了拓撲排序
        cout<<"Okay."<<endl;
    }else{
        cout<<"Impossible."<<endl;
    }
    for (int i = 0; i < k; ++i) {
        int t=input[i];
        minS=9999999,maxD=-1;
        if(post[t].empty()){
            cout<<"You may take test "<<t<<" directly."<<endl;
            continue;
        }
        if(flag){
            dfs(t,0,0);
            for (int j = res.size()-1; j >= 0; --j) {
                if(j!=res.size()-1) cout<<"->";
                    cout<<res[j];
            }cout<<endl;
        }else{
            cout<<"Error."<<endl;
        }
    }
    return 0;
}
           

總結跌跌撞撞考了滿分，但是明顯用的時間超過考試給的三個小時，大後天就要參加PAT2021年春季考了，希望取得好成績，理想成績是九十分，嗚嗚，不想二戰。