[数据结构与算法]PAT（甲级）2019年冬季考试

这套卷子蛮简单的。

7-1 Good in C (20 分)

按题目意思做，注意格式处理

#include<iostream>
#include<vector>
#include<unordered_map>
#include<cctype>
using namespace std;
unordered_map<char, vector<string>> mp;

int main(){
    for(char c = 'A'; c <= 'Z'; c++){
        vector<string> v;
        for(int i = 0; i < 7; i++){
            string line; getline(cin, line);
            v.push_back(line);
        }
        mp[c] = v;
    }
    string s;
    getline(cin, s);
    
    bool flag = true;
    for(int i = 0; i < s.size(); i++){
        if(s[i]<'A' || s[i]>'Z') continue;
        if(flag) flag = false; else cout << endl;
        int j = i;
        while(j<s.size() && s[j]>='A' && s[j]<='Z') j++;
        for(int t = 0; t < 7; t++){
            bool first = true; 
            for(int k = i; k < j; k++){
                if(first) first = false; else cout << " ";
                cout << mp[s[k]][t];
            }
            cout << endl;
        }
        i = j;
    }
    
}

7-2 Block Reversing (25 分)

链表反转。测试点6是因为所有链表节点不一定都在头节点所在链表上，也就是说这个测试点的输出节点数是比输入节点数要少的。

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int h, n, k;
unordered_map<int, int> Value, Next;

int main(){
    scanf("%d %d %d", &h, &n, &k);
    for(int i = 0; i < n; i++){
        int x, y, z; scanf("%d %d %d", &x, &y, &z);
        Value[x] = y; Next[x] = z;
    }
    vector<int> flags;
    int t = h;
    while(t!=-1) {
        flags.push_back(t);
        t = Next[t];
    }
    
    n = flags.size();
    t = (n-1)/k;
    for(; t >= 0; t--){
        for(int i = 0; i < k; i++){
            int id = t*k+i;
            if(id >= n) break;
            int p =  flags[id];
            if(t==(n-1)/k && i==0) printf("%05d %d", p, Value[p]);
            else printf(" %05d\n%05d %d", p, p, Value[p]);
        }
    }
    printf(" -1\n");
    
    
}

7-3 Summit (25 分)

一开始以为需要什么复杂的算法不然会超时，一时想不到，就直接先上手做了。直白的做法，主要是数量级不大。

#include<iostream>
#include<vector>
using namespace std;
int n, m, k;
vector<vector<int>> grid;
int main(){
    scanf("%d %d", &n, &m);
    grid.resize(n+1, vector<int>(n+1, 0));
    for(int i = 0; i < m; i++){
        int x, y; scanf("%d %d", &x, &y);
        grid[x][y] = grid[y][x] = 1;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++){
        int l; scanf("%d", &l);
        vector<int> v; vector<int> visited(n+1, 0);
        for(int j = 0; j < l; j++){
            int x; scanf("%d", &x);
            visited[x] = 1;
            v.push_back(x);
        }
        
        int flag = 0;
        for(int p = 0; p < v.size(); p++){
            for(int q = p+1; q < v.size(); q++){
                if(grid[v[p]][v[q]]==0) {flag = -1; break;}
            }
            if(flag==-1) break;
        }
        if(flag==-1) {printf("Area %d needs help.\n", i+1); continue;}
        
        int x = -1;
        for(int t = 1; t <= n; t++){
            if(visited[t]==1) continue;
            bool ok = true;
            for(auto a:v) {
                if(grid[t][a]==0) {ok = false; break;}
            }
            if(ok) {x = t; break;}
        }
        if(x!=-1) printf("Area %d may invite more people, such as %d.\n", i+1, x);
        else printf("Area %d is OK.\n", i+1);
    }
    
}

7-4 Cartesian Tree (30 分)

最小堆。递归。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;
int n;
vector<int> v;
unordered_map<int, int> L, R;
int handle(int l, int r){
    if(l>r) return -1;
    int id = -1, M = 1e9;
    for(int i = l; i <= r; i++){
        if(v[i] < M) {
            id = i;
            M = v[i];
        }
    }
    L[M] = handle(l, id-1);
    R[M] = handle(id+1, r);
    return M;
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        v.push_back(x);
    }
    int h = handle(0, n-1);
    queue<int> q; q.push(h);
    bool first = true;
    while(!q.empty()){
        if(first) first = false; else printf(" ");
        int t = q.front(); q.pop();
        printf("%d", t);
        if(L[t]!=-1) q.push(L[t]);
        if(R[t]!=-1) q.push(R[t]);
    }
    printf("\n");
    
    
    
    
}