PAT-2022年春季考试 - 甲级题解

短命女 2024-03-31 14:00 74阅读 0赞

## 7-1 Simple Lie Detection ##

### 算法标签 ###

模拟

### 原题 ###

![在这里插入图片描述][626f6a30a96f457dbe2f29a296108c69.png]  
![在这里插入图片描述][e6edac6fb9094209915b5bac27e30457.png]

### 思路 ###

依题意模拟即可

### 代码 ###

#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 ##

### 原题 ###

![在这里插入图片描述][620e0b0950f94a8e8f7dcf53ebad300d.png]

### 算法标签 ###

排序 优先队列

### 思路 ###

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

### 优先队列AC代码 ###

### 只存储前K个值进行排序 ###

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

### 原题 ###

![在这里插入图片描述][fb315a3792514194903ece1046e8313a.png]  
![在这里插入图片描述][0ab468f6a3c6421dbe7bca584671a217.png]

### 算法标签 ###

树 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;
    }

## 7-4 The Rescue 分数 30 ##

### 原题 ###

![在这里插入图片描述][065e980021474b83b58e80ccb3489d54.png]  
![在这里插入图片描述][8d10a710ba564a25ad227211ef34f61b.png]  
![在这里插入图片描述][20308513979942078020bd20f042148b.png]

[626f6a30a96f457dbe2f29a296108c69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/502323a48a9e4c3fa585781ecdd64493.png
[e6edac6fb9094209915b5bac27e30457.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/48f2ccc9f0a94f30a0b86f0235322dcf.png
[620e0b0950f94a8e8f7dcf53ebad300d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/de438677a6fa4d50b6adcf2d285f5d95.png
[fb315a3792514194903ece1046e8313a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a94eb984db9d49ac964a3ca7932aa3d0.png
[0ab468f6a3c6421dbe7bca584671a217.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/eba0b3690f034432a2a9dfde83a8c838.png
[065e980021474b83b58e80ccb3489d54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a25cdee8e7b644ce894b51aa8a7f968e.png
[8d10a710ba564a25ad227211ef34f61b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/92fe50e5c110464d86603d94da20179a.png
[20308513979942078020bd20f042148b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/eb6357591fb045a5b933bc38cf18dbcd.png