PAT 2024年春季（甲级）

补题链接：PAT 2024春季（甲级）

A-1 Braille Recognition

因为数据可能存在因重叠而导致的重复计算情况，所以我们要遍历每一个3*2的矩阵，注意输出的格式问题。

#include <bits/stdc++.h>
 
using namespace std ;
int n , m ;
char s[110][110] ;
int a[12] ;
 
void check(int x , int y)
{
    if(x + 2 >= n || y + 1 >= m) return ;
    int p = 0 ;
    for(int i = x ; i <= x + 2 ; i ++)
        for(int j = y ; j <= y + 1 ; j ++)
            if(s[i][j] == '*') p ++ ;
    if(p == 1 && s[x][y] == '*' ) a[1] ++ ;
    if(p == 2 && s[x][y] == '*' && s[x + 1][y] == '*') a[2] ++ ;
    if(p == 2 && s[x][y] == '*' && s[x][y + 1] == '*') a[3] ++ ;
    if(p == 3 && s[x][y] == '*' && s[x][y + 1] == '*' && s[x + 1][y + 1] == '*') a[4] ++ ;
    if(p == 2 && s[x][y] == '*' && s[x + 1][y + 1] == '*') a[5] ++ ;
    if(p == 3 && s[x][y] == '*' && s[x][y + 1] == '*' && s[x + 1][y] == '*') a[6] ++ ;
    if(p == 4 && s[x][y] == '*' && s[x][y + 1] == '*' && s[x + 1][y] == '*' && s[x + 1][y + 1] == '*') a[7] ++ ;
    if(p == 3 && s[x][y] == '*' && s[x + 1][y + 1] == '*' && s[x + 1][y] == '*') a[8] ++ ;
    if(p == 2 && s[x + 1][y] == '*' && s[x][y + 1] == '*') a[9] ++ ;
    if(p == 3 && s[x + 1][y] == '*' && s[x][y + 1] == '*' && s[x + 1][y + 1] == '*') a[0] ++ ;
    
}
signed main()
{
    cin >> n >> m ;
    for(int i = 0 ; i < n ; i ++)
        cin >> s[i] ;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < m ; j ++)
            check(i , j) ;
    for(int i = 1 ; i <= 9 ; i ++)
        cout << a[i] << " " ;
    cout << a[0] << endl ;
    return 0 ;
}

A-2 AI Comments

对于PTA（包括天梯赛、睿抗、PAT等等）中常考的描述文字和要求较多的问题，我们拆分成多个问题，分别求解，对于姓名和五个数字的匹配，我们用map来储存（进而可以直接用map判断考生是否存在），用结构体来存这五个数字。

求解每组数的中位数，与考生姓名无关，我们用5个vector来存储这五个类别的数字，排序后得到中位数。

对于每个查询考生的输出，我们可以再用一个结构体来存差值，用cmp重载排序，按着题目格式进行输出。

#include <bits/stdc++.h>
 
using namespace std ;
const int N = 100010 ;
int n , m ;
map<string,int> mp ;
struct e{
    int a , b , c , d , e ;
}p[N] ;
vector<int> q[6] ;
int va , vb , vc , vd , ve ;
struct f{
    int id , c ;
}v[6] ;
 
bool cmp(f x , f y)
{
    if(x.c != y.c) return x.c > y.c ;
    return x.id < y.id ;
}
signed main()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i ++)
    {
        string s ;
        int a , b , c , d , e ;
        cin >> s >> a >> b >> c >> d >> e ;
        mp[s] = i ;
        p[i] = {a , b , c , d , e} ;
        q[0].push_back(a) , q[1].push_back(b) , q[2].push_back(c) , q[3].push_back(d) , q[4].push_back(e) ;
    }
    sort(q[0].begin() , q[0].end()) , sort(q[1].begin() , q[1].end()) , sort(q[2].begin() , q[2].end()) , sort(q[3].begin() , q[3].end()) , sort(q[4].begin() , q[4].end()) ;
    va = q[0][n / 2] , vb = q[1][n / 2] , vc = q[2][n / 2] , vd = q[3][n / 2] , ve = q[4][n / 2] ;
    while(m --)
    {
        string s ;
        cin >> s ;
        if(!mp.count(s)) cout << "Not Found" << endl ;
        else
        {
            int u = mp[s] ;
            v[1].id = 1 , v[1].c = p[u].a - va ;
            v[2].id = 2 , v[2].c = p[u].b - vb ;
            v[3].id = 3 , v[3].c = p[u].c - vc ;
            v[4].id = 4 , v[4].c = p[u].d - vd ;
            v[5].id = 5 , v[5].c = p[u].e - ve ;
            sort(v + 1 , v + 6 , cmp) ;
            vector<int> res ;
            for(int i = 1 ; i <= 5 ; i ++)
                if(v[i].c >= 0) res.push_back(v[i].id) ;
            for(int i = 1 ; i <= 5 ; i ++)
                if(v[i].c < 0) res.push_back(-v[i].id) ;
            for(int i = 0 ; i < 5 ; i ++)
                if(i != 4) cout << res[i] << " " ;
                else cout << res[i] << endl ;
        }
    }
    return 0 ;
}

A-3 Degree of Skewness

给定一棵二叉树的后序遍历和中序遍历，要我们求只有左子节点和只有右子节点的差值。

后序遍历的次序是：左、右、中

中序遍历的次序是：左、中、右

用pos来记录后序遍历的数在中序遍历中的位置

根据根的位置，通过递归，得到树的前序遍历。

再计算只有左子节点的根的数量和只有右子节点的根的数量的差值。

#include <bits/stdc++.h>

using namespace std ;
const int N = 1010 ;
int n , sl , sr ;
int a[N] , b[N] ;
unordered_map<int,int> l , r , pos ;

int bulid(int bl , int br , int al , int ar)
{
    int root = a[ar] ;
    int k = pos[root] ;
    if(bl < k) l[root] = bulid(bl , k - 1 , al , al + k - 1 - bl ) ;
    if(br > k) r[root] = bulid(k + 1 , br , ar - br + k  , ar - 1) ;
    return root ;
}
void dfs(int u)
{
    if(l[u] && !r[u]) sl ++ ;
    if(!l[u] && r[u]) sr ++ ;
    if(l[u]) dfs(l[u]) ;
    if(r[u]) dfs(r[u]) ;
}

int main()
{
    cin >> n ;
    for(int i = 0 ; i < n ; i ++) cin >> a[i] ;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> b[i] ;
        pos[b[i]] = i ;
    }
    
    int root = bulid(0 , n - 1 , 0 , n - 1) ;
    dfs(root) ;
    cout << (sl - sr) << " = " << sl << " - " << sr << endl ;
    return 0 ; 
}

A-4 Uniqueness of Topological Order

用d数组来存储每个点的度数，取min，再去遍历，即可得到度数最小的点。

这道题的难点在于如何判断拓扑排序是否是唯一的。

先来思考什么情况下不是唯一的：

1.度数最小的点的度数不为0，无法进行拓扑，则不存在唯一的拓扑序。

2.有多个点的度数为0，说明起始排序的点都不唯一，序列一定不唯一。

3.当只有一个点的度数最小为0时，排序后的点的总数不为n。这说明在拓扑序之外，可能还有环的存在。（未判断这一点，样例3和样例4会wa）

#include <bits/stdc++.h>

using namespace std ;
const int N = 100010 ;
int n , m ;
int d[N] , h[N] , e[N] , ne[N] , idx ;

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
signed main()
{
    cin >> n >> m ;
    memset(h , -1 , sizeof h) ;
    while(m --)
    {
        int a , b ;
        cin >> a >> b ;
        d[b] ++ ;
        add(a , b) ;
    }
    
    int mx = 1e9 ;
    vector<int> qu ;
    for(int i = 1 ; i <= n ; i ++)
        mx = min(mx , d[i]) ;
    for(int i = 1 ; i <= n ; i ++)
        if(d[i] == mx) qu.push_back(i) ;

    
    for(int i = 0 ; i < qu.size() ; i ++)
        if(i != qu.size() - 1) cout << qu[i] << " " ;
        else cout << qu[i] << endl ;

    queue<int> q ;
    vector<int> res ;
    for(int i = 1 ; i <= n ; i ++)
        if(d[i] == 0)
        {
            q.push(i) , res.push_back(i) ;
        }
    int f = 1 ;
    while(q.size())
    {
        int t = q.front() ;
        q.pop() ;
        int u = 0 ;
        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i] ;
            d[j] -- ;
            if(d[j] == 0)
            {
                u ++ ;
                q.push(j) , res.push_back(j) ;
            }
        }
        if(u > 1) f = 0 ;
    }
    if(f && qu.size() == 1 && res.size() == n)
    {
        cout << "Yes" << endl ;
        for(int i = 0 ; i < res.size() ; i ++)
            if(i != res.size() - 1) cout << res[i] << " " ;
            else cout << res[i] << endl ;
    }
    else cout << "No" << endl ;   

    return 0 ;
}