攀拓（PAT）- 程序设计（甲级）2024年春季考试仿真卷cpp题解

A-1 Braille Recognition

#include<iostream>
using namespace std;
const int N=110;
int n,m;
char g[N][N];
int sum[10];
void check(int i,int j){
    int cnt=0;
    for(int x=i;x<i+3;x++)
        for(int y=j;y<j+2;y++)
            if(g[x][y]=='*') cnt++;
    if(cnt==1&&g[i][j]=='*') sum[1]++;
    else if(cnt==2){
        if(g[i][j]=='*'){
            if(g[i+1][j]=='*') sum[2]++;
            else if(g[i][j+1]=='*') sum[3]++;
            else if(g[i+1][j+1]=='*') sum[5]++;
        }else if(g[i+1][j]=='*'&&g[i][j+1]=='*') sum[9]++;
    }else if(cnt==3){
        if(g[i][j]=='*'){
            if(g[i][j+1]=='*'&&g[i+1][j+1]=='*') sum[4]++;
            else if(g[i+1][j]=='*'&&g[i+1][j+1]=='*') sum[8]++;
            else if(g[i+1][j]=='*'&&g[i][j+1]=='*') sum[6]++;
        }else if(g[i+1][j]=='*'&&g[i+1][j+1]=='*'&&g[i][j+1]=='*') sum[0]++;
    }else if(cnt==4&&g[i+2][j]=='.'&&g[i+2][j+1]=='.') sum[7]++;
}
int main(){
    cin>>n>>m;
    getchar();
    for(int i=0;i<n;i++) cin>>g[i];
    for(int i=0;i+2<n;i++)
        for(int j=0;j+1<m;j++) {
            check(i,j);
        }
    for(int i=1;i<10;i++) printf("%d ",sum[i]);
    printf("%d",sum[0]);
    return 0;
}

A-2 AI Comments

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
const int N=1e5+10;
struct a{
    int n,v;
    bool operator< (const a& t) const {
        if(n<0&&t.n<0){
            if(v!=t.v) return v>t.v;
            return n>t.n;
        }else if(n>=0&&t.n>=0){
            if(v!=t.v) return v>t.v;
            return n<t.n;
        }else return n>t.n;
    }
}res[5];
unordered_map<string,int> name;
int persons[N][5];
int a[N],mid[5];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        string id;
        cin>>id;
        name[id]=i;
        for(int j=0;j<5;j++) scanf("%d",&persons[i][j]);
    }
    for(int i=0;i<5;i++){
        for(int j=0;j<n;j++) a[j]=persons[j][i];
        sort(a,a+n,greater<int>());
        if(n%2) mid[i]=a[n/2];
        else mid[i]=a[(n-1)/2];
    }
    while(m--){
        string id;
        cin>>id;
        if(name.find(id)!=name.end()){
            int i=name[id];
            for(int j=0;j<5;j++){
                int t=persons[i][j]-mid[j];
                if(t<0) res[j]={-(j+1),t};
                else res[j]={j+1,t};
            }
            sort(res,res+5);
            printf("%d",res[0].n);
            for(int j=1;j<5;j++) printf(" %d",res[j]);
            puts("");
        }else printf("Not Found\n");
    }
    return 0;
}

A-3 Degree of Skewness

#include<iostream>
#include<unordered_map>
using namespace std;
const int N=1e3+10;
int l[N],r[N],n,post[N],in[N];
unordered_map<int,int> pos;
int build(int il,int ir,int pl,int pr){
    int root=post[pr];
    int k=in[root];
    if(il<k) l[root]=build(il,k-1,pl,pl+k-1-il);
    if(k<ir) r[root]=build(k+1,ir,pl+k-il,pr-1);
    return 1;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>post[i];
    for(int i=0;i<n;i++){
        cin>>pos[i];
        in[pos[i]]=i;
    }
    build(0,n-1,0,n-1);
    int a=0,b=0;
    for(int i=1;i<=n;i++) {
        if(l[i]&&!r[i]) a++;
        else if(!l[i]&&r[i]) b++;
    }
    printf("%d = %d + %d\n",a-b,a,b);
    return 0;
}

A-4 Uniqueness of Topological Order

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e4+10;
bool g[N][N],st[N];
int n,m;
int sum[N],dist[N],cnt[N];

int main(){
    cin>>n>>m;
    memset(g,-1,sizeof g);
    int root=0;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a][b]=true;
        sum[b]++;
    }
    int minv=1e4+10;
    for(int i=1;i<=n;i++) minv=min(minv,sum[i]);
    vector<int> fline;
    for(int i=1;i<=n;i++)
        if(sum[i]==minv) fline.push_back(i);
    cout<<fline[0];
    for(int i=1;i<fline.size();i++) cout<<' '<<fline[i];
    puts("");
    if(minv!=0||fline.size()>1){
        puts("N0");
        return 0;
    }
    int q[N];
    int hh=0,tt=0;
    q[0]=fline[0];
    while(hh<=tt){
        int t=q[hh++];
        for(int i=1;i<=n;i++){
            if(g[t][i]&&--sum[i]==0) q[++tt]=i;
        }
    }
    if(tt!=n-1) puts("No");
    else {
        cout<<"Yes"<<endl<<q[0];
        for(int i=0;i<n;i++) cout<<' '<<q[i];
    }
    return 0;
}