PAT-2022年春季考试 - 甲级题解-蒲公英云

7-1 Simple Lie Detection

算法标签

模拟

原题

在这里插入图片描述

思路

依题意模拟即可

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define pb push_back
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
typedef pair<int, int> PII;
const int N=10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
//int t, n, m, cnt, ans; 
char c[105];
string s;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int ca(string s){
    int res=0;
    // 条件1
    if(s[0]=='f'){
        res-=2;
    }
    // 条件2
    if(s[s.size()-1]=='a'){
        res-=1;
    }
    // 条件3
    for(int i=0; i<s.size();){
        int j=i+1;
        while(j+1<=s.size()&&s[i]==s[j]){
            j++;
        }
        if(j-1-i+1>5){
            res+=3;
        }
        i=j;
    }
    // 条件4
    rep(i, 0, s.size()){
        if(i+1<=s.size()&&s[i]=='a'&&(s[i+1]=='e'||s[i+1]=='h')){
            res-=4;
        }
    }
    // 条件5
    for(int i=0; i<s.size();){
        int j=i+1;
        while(j+1<=s.size()&&s[j]-'a'-(s[i]-'a')==1){
            s[i]=s[j];
            j++;
        }
        if(j-1-i+1>3){
            res+=5;
        }
        i=j;
    }
    return res;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, t, m;
    scanf("%lld %lld %lld", &n, &t, &m);
    rep(i, 0, m){
        scanf("%s", c);
        s=c;
        int res=ca(s);
        if(res<=t){
            printf("%lld\n", res);
        }else{
            printf("%lld!!!\n", res);
        }
    }
    return 0;
}

7-2 The First K Largest Numbers 分数 25

原题

在这里插入图片描述

算法标签

排序优先队列

思路

由于本题时间限制150 ms，内存限制2 MB，若直接开辟大小为n的数组依次读入并进行快排，将会超出内存限制（测试点3 4 5 6 ）可以采用优先队列维护前K大的值或是只存前k+1个数并进行排序

优先队列AC代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define pb push_back
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
typedef pair<int, int> PII;
const int N=10005, K=10, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
//int t, n, m, cnt, ans; 
int a[K];
pq<int, vector<int>, greater<int>> q;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=rd(),k=rd();
    memset(a, inf, sizeof a);
    if(n<k){
        n=k;
    }
    for(int i=0;i<n;++i){
        int num=rd();
        q.push(num);
        if(q.size()>K){
            q.pop();
        }
    }
    int p=0;
    while (!q.empty()){
        a[p++]=q.top();
        q.pop();
    }
    for(int i=p-1, j=0; j<k; i--, j++) {
        if(i==p-1){
            printf("%lld", a[i]);
        }else{
            printf(" %lld", a[i]);
        }
    }
    return 0;
}

只存储前K个值进行排序

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define pb push_back
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
typedef pair<int, int> PII;
const int N=10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
int a[100];
inline int rd() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
bool cmp(int n1,int n2){
    return n1>n2;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=rd(), k=rd();
    rep(i, 0, n){
        int t=min(i, k);
        a[t]=rd();
        sort(a,a+t,cmp);
    }
    rep(i, 0, min(n, k)){
        if(!i){
            printf("%lld",a[i]);
        }
        else{
            printf(" %d",a[i]);
        } 
    }
    return 0;
}

7-3 Is It A Binary Search Tree - Again分数 25

原题

在这里插入图片描述

算法标签

树 dfs

思路

读入数据，对树进行中序遍历，若中序遍历序列有序，即为二叉搜索树，依题意对树的中序遍历结果输出

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define pb push_back
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
typedef pair<int, int> PII;
const int N=10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
//int t, n, m, cnt, ans;
int n; 
int w[N];
vector<int> v;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void dfs(int u){
    if(u>n){
        return ;
    }
    if(u*2<=n){
        dfs(u*2);
    }
    if(w[u]!=-1){
        v.pb(w[u]);
    }
    if(u*2+1<=n){
        dfs(u*2+1);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n=rd();
    rep(i, 1, n+1){
        w[i]=rd();
    }
    dfs(1);
    bool flag=true;
    rep(i, 0, v.size()-1){
        if(v[i+1]<v[i]){
            flag=false;
            break;
        }
    }
    if(flag){
        puts("YES");
    }else{
        puts("NO");
    }
    printf("%lld", v[0]);
    rep(i, 1, v.size()){
        printf(" %lld", v[i]);
    }
    return 0;
}