PAT 2022秋季乙级满分题解

迷南。 2024-04-07 13:01 201阅读 0赞

## PAT 2022秋季 乙级题解 ##

### 7-1 计算数列第n项 ###

#### 原题 ####

![在这里插入图片描述][48257a16e54f462080f7518c1fa825d9.png]

##### 样例： #####

###### 输入样例： ######

38 4

###### 输出样例： ######

#### 算法标签 ####

模拟

#### AC代码 ####

### 7-2 AB变换 ###

#### 原题 ####

![在这里插入图片描述][050bc2f9c57f4dff81f48d469fef796a.png]

##### 样例 #####

###### 输入样例： ######

13 2022
    BBBBBBAAAAAAA

###### 输出样例： ######

#### 算法标签 ####

模拟 STL容器

#### AC代码 ####

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>b; --i)
    #define x first
    #define y second
    #define ump unorderer_map
    #define pq priority_queue
    #define debug(a) cout<<"a = "<<a<<"\n"
    #define debugi(a) printf("a = %lld", a)
    using namespace std;
    int n,m;
    // 标准库容器set 去重 计数
    set<int> ss;
    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 A(int n){
    	return n/4;
    }
    int B(int n){
    	return n*8+1;
    }
    
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>m>>n;
    	int t=n;
    	string s;
    	cin>>s;
    	rep(i, 0, s.size()){
    		if(s[i]=='B'){
    			if(!i){
    				n=0;
    			}
    			n=B(n);
    			if(n<=t){
    				ss.insert(n);		
    			}
    		}else if(s[i]=='A'){
    			if(!i){
    				n=0;
    			}
    			n=A(n);
    			if(n<=t){
    				ss.insert(n);		
    			}
    		}
    	}
    //	printf("%lld\n", ss.size());
    	cout<<ss.size()<<"\n";
    	return 0;
    }

### 7-3 中秋福利 ###

#### 原题 ####

![在这里插入图片描述][3cf5af042e354efcbf6570040fd85145.png]  
![在这里插入图片描述][814bc47d87b64a0984d395c09e1a5e30.png]

##### 样例 #####

###### 输入样例 1 ######

5 300 400
    12345678 820
    22345678 400
    01234567 220
    00000001 400
    23742784 386

###### 输出样例 1： ######

3 400
    22345678
    00000001

###### 输入样例 2： ######

5 250 300
    12345678 820
    22345678 400
    01234567 220
    00000001 400
    23742784 386

###### 输出样例 2： ######

220 820

#### 算法标签 ####

模拟 STL容器

#### AC代码 ####

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>b; --i)
    #define x first
    #define y second
    #define ump unorderer_map
    #define pq priority_queue
    #define debug(a) cout<<"a = "<<a<<"\n"
    #define debugi(a) printf("a = %lld", a)
    using namespace std;
    // 对于第二个测试点与第三个测试点 数据范围超过题目规定范围 需要扩大范围 第三个测试点需将mn设置的足够大
    int n,a,b, mx=-1, mn=100000005, MX=-1;
    // 标准库容器vector, pair 存储
    vector<pair<string, int>> ss;
    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);
    //	n=rd(), a=rd(), b=rd();
    	cin>>n>>a>>b;
    	while(n--){
    		string id;
    		int p;
    		cin>>id>>p;
    		if(p>=a&&p<=b){
    			ss.push_back({id, p});
    			mx=max(mx, p);
    		}
    		MX=max(MX, p);
    		mn=min(mn, p);
    	}
    	if(ss.size()){
    		cout<<ss.size()<<" "<<mx<<"\n";
    		for(auto xx:ss){
    			if(xx.y==mx)
    			cout<<xx.x<<"\n";	
    		}
    	}else{
    		cout<<mn<<" "<<MX<<"\n";
    	}
    	return 0;
    }

### 7-4 爆气球 ###

#### 原题 ####

![在这里插入图片描述][47f57938e1454dbd9aca766e75984e4b.png]  
![在这里插入图片描述][73c8f56b23884d208a9f8db319e51beb.png]

##### 样例 #####

###### 输入样例： ######

11 120
    -120 -40 0 80 122 140 160 220 240 260 300

###### 输出样例： ######

120 5

#### 算法标签 ####

模拟

#### 14分代码 ####

测试点3 4运行超时

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>b; --i)
    #define x first
    #define y second
    #define ump unorderer_map
    #define pq priority_queue
    #define debug(a) cout<<"a = "<<a<<"\n"
    #define debugi(a) printf("a = %lld\n", a)
    using namespace std;
    int n,m, mx=0, mn=1000, MX=0, MXID=0;
    int a[100005];
    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);
    	n=rd(), m=rd();
    	rep(i, 0, n){
    		a[i]=rd();
    		mn=min(a[i], mn);
    		mx=max(a[i], mx);
    	}
    	
    	rep(i, mn, mx-m){
    		int l=i, r=i+m;
    		int cnt=0;
    		rep(j, 0, n){
    			if(a[j]>=l&&a[j]<=r){
    				cnt++;	
    			}else if(a[j]>r){
    				break;
    			}else if(a[j]<l){
                    continue;
                }
    		}
    		if(cnt>MX){
    			MX=cnt;
    			MXID=i;
    		}
    	}
    	if(MX==0){
    		printf("%lld %lld\n", mn, MX);
    	}else{
    		printf("%lld %lld\n", MXID, MX);
    	}
    	return 0;
    }

#### AC代码 ####

#### 思路 ####

枚举数组元素， 判断每个元素覆盖气球数, 记录最多可覆盖气球数及最多可覆盖气球数开始下标， 则最小开始值为最后可覆盖气球位置减高度H

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>b; --i)
    #define x first
    #define y second
    #define ump unorderer_map
    #define pq priority_queue
    #define debug(a) cout<<"a = "<<a<<"\n"
    #define debugi(a) printf("a = %lld\n", a)
    using namespace std;
    int n,m, mx=0, mn=1000, MX=1, MXID=0;
    int a[100005];
    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);
    	n=rd(), m=rd();
    	rep(i, 0, n){
    		a[i]=rd();
    		mn=min(a[i], mn);
    		mx=max(a[i], mx);
    	}
    	rep(i, 0, n){
    		int cnt=1;
    		while(a[i]+m>=a[i+cnt]&&i+cnt<n){
    				cnt++;
    		}
    		if(cnt>MX){
    			MX=cnt;
    			MXID=i;
    		}
    	}
    	if(MXID==a[0]){
    		printf("%lld %lld\n", MXID, MX);
    	}else if(MXID!=a[0]){
    		printf("%lld %lld\n", a[MXID+MX-1]-m, MX);
    	}
    	return 0;
    }

### 7-5 快排第二轮 ###

#### 原题 ####

![在这里插入图片描述][6cb3f1fcc66443da8b7a2cbd17418d93.png]  
![在这里插入图片描述][ca0aa050195f4bff854893bb61f5f1cd.png]

##### 样例 #####

###### 输入样例： ######

4
    8
    5 2 16 12 28 60 32 72
    8
    2 16 5 28 12 60 32 72
    8
    2 12 16 5 28 32 72 60
    8
    5 2 12 28 16 32 72 60

###### 输出样例： ######

Yes
    Yes
    Yes
    No

#### 算法标签 ####

模拟 排序

#### 17分代码 ####

测试点3 4运行超时  
![在这里插入图片描述][6af4207f191a4f94956e3e4dbeb394a5.png]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>b; --i)
    #define x first
    #define y second
    #define ump unorderer_map
    #define pq priority_queue
    #define debug(a) cout<<"a = "<<a<<"\n"
    #define debugi(a) printf("a = %lld\n", a)
    using namespace std;
    int n,m, mx=0, mn=1000, MX=1, MXID=0;
    int a[100005];
    int b[100005];
    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 t=rd();
    	while(t--){
    		bool flag1=false;
    		bool flag2=false;
    		bool flag3=true;
    		int f1, f2, f3;
    		n=rd();
    		rep(i, 0, n){
    			a[i]=rd();
    			b[i]=a[i];
    		}
    		sort(b, b+n);
    		if(b[0]==a[0]){
    			flag1=true;
    		}
    		if(b[n-1]==a[n-1]){
    			flag2=true;
    		}
    		int cnt=0;
    		rep(i, 1, n-1){
    			bool flag3=true;
    			// 直接暴力枚举
    			rep(j, 0, n){
    				if(j<i&&a[j]>a[i]){				
    					flag3=false;
    				}
    				if(j>i&&a[j]<a[i]){				
    					flag3=false;
    				}			
    			}
    			if(flag3){
    				cnt++;
    				if(cnt>=3){
    					break;
    				}
    			}
    		}
    		if(flag1&&cnt>=1||flag1&&flag2){
    			printf("Yes\n");
    		}else if(flag2&&cnt>=1||flag1&&flag2){
    			printf("Yes\n");
    		}else if(cnt>=3){
    			printf("Yes\n");
    		}else{
    			printf("No\n");
    		}
    		
    	}
    	return 0;
    }

#### 14分代码 ####

测试点1 3 4答案错误  
![在这里插入图片描述][02039d0fac6d453bab1bc1ffee004628.png]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>b; --i)
    #define x first
    #define y second
    #define ump unorderer_map
    #define pq priority_queue
    #define debug(a) cout<<"a = "<<a<<"\n"
    #define debugi(a) printf("a = %lld\n", a)
    using namespace std;
    int n,m, mx=0, mn=1000, MX=1, MXID=0;
    int a[100005];
    int b[100005];
    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 t=rd();
    	while(t--){
    		bool flag1=false;
    		bool flag2=false;
    		bool flag3=true;
    		int f1, f2, f3;
    		n=rd();
    		rep(i, 0, n){
    			a[i]=rd();
    			b[i]=a[i];
    		}
    		sort(b, b+n);
    		if(b[0]==a[0]){
    			flag1=true;
    		}
    		if(b[n-1]==a[n-1]){
    			flag2=true;
    		}
    		int cnt=0;
    		rep(i, 1, n-1){
    			// l表示a[i]由小到大排序位置下标
    			int l= lower_bound(b, b+n, a[i])-b;
    			if(i==l){
    				cnt++;
    				if(cnt>=3){
    					break;
    				}	
    			}
            }
    		if(flag1&&cnt>=1||flag1&&flag2){
    			printf("Yes\n");
    		}else if(flag2&&cnt>=1||flag1&&flag2){
    			printf("Yes\n");
    		}else if(cnt>=3){
    			printf("Yes\n");
    		}else{
    			printf("No\n");
    		}	
    	}
    	return 0;
    }

### 思路 ###

对原序列进行sort排序，逐个比较，当当前元素没有变化且其左边的所有值的最大值都比其小时， 该元素即为主元

#### AC代码 ####

尚未AC  
2022/09/08 更

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>b; --i)
    #define x first
    #define y second
    #define ump unorderer_map
    #define pq priority_queue
    #define debug(a) cout<<"a = "<<a<<"\n"
    #define debugi(a) printf("a = %lld\n", a)
    using namespace std;
    int n,m, mx=0, mn=1000, MX=1, MXID=0;
    int a[100005];
    int b[100005];
    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 t=rd();
    	while(t--){
    		bool flag1=false;
    		bool flag2=false;
    		int mx=-1;
    		n=rd();
    		rep(i, 0, n){
    			a[i]=rd();
    			b[i]=a[i];
    		}
    		sort(b, b+n);
    		if(b[0]==a[0]){
    			flag1=true;
    		}
    		if(b[n-1]==a[n-1]){
    			flag2=true;
    		}
    		int cnt=0;
    		rep(i, 1, n-1){
    			// 当当前元素没有变化并且它左边的所有值的最大值都比它小的时候就可以认为它一定是主元
    			if(a[i]==b[i]&&b[i]>mx){
    				cnt++;
    			}
    			if(b[i]>mx){
    				mx=b[i];
    			}
    		}
    		if(flag1&&cnt>=1||flag1&&flag2){
    			printf("Yes\n");
    		}else if(flag2&&cnt>=1||flag1&&flag2){
    			printf("Yes\n");
    		}else if(cnt>=3){
    			printf("Yes\n");
    		}else{
    			printf("No\n");
    		}
    		
    	}
    	return 0;
    }

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define ums unordered_set
    #define pq priority_queue
    #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=100005, INF=0x3f3f3f3f3f3f3f3f, MOD=1e9+7;
    const double Exp=1e-8;
    //int t, n, m, cnt, ans; 
    int n, l[N], r[N], a[N];
    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);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int t=rd();
    	while(t--){
    	    bool flagh=false, flagt=false;
    	    vector<int> res;
    		n=rd();
    		rep(i, 1, n+1){
    	    	a[i]=rd();
    		}
    		rep(i, 1, n+1){
    	    	l[i]=max(l[i-1], a[i]);
    		}
    		r[n+1]=INF;
    		Rep(i, n, 0){
    	    	r[i]=min(r[i+1], a[i]);
    		}
    		rep(i, 1, n+1){
    	    	if(a[i]>l[i-1]&&a[i]<r[i+1]){
    	        	if(i==1){
    	            	flagh=true;
    	        	}
    	        	if(i==n){
    	            	flagt=true;
    	        	}
    	        	res.push_back(a[i]);
    	    	}
    		}
    		// 头 尾
    		// 一轮头 
    		// 一轮尾
    		if(flagh&&flagt||flagh&&res.size()==2||flagt&&res.size()==2||res.size()==3){
    	   		puts("Yes");
    		}else{
    	   		puts("No");
    		}
    	}
    	return 0;
    }

### 战绩&战果 ###

![在这里插入图片描述][cb7d202584fa40edacc4e417a2f37a85.png]  
成绩 92/100  
排名 45/307

### 总结 ###

整体题目难度并不高， 前四题依题意使用合适的STL容器进行模拟， 最后一题主要考察对快排的理解。虽然成绩排名比较满意， 但是基础对于算法基础掌握不牢， 需要夯实算法基础。

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[48257a16e54f462080f7518c1fa825d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/679b1ce811304593a2006b64dcd7e755.png
[050bc2f9c57f4dff81f48d469fef796a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8a43cb3170fe41c999b5bcec85a4f967.png
[3cf5af042e354efcbf6570040fd85145.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/64a87aaed5d642968704406ae138dcbc.png
[814bc47d87b64a0984d395c09e1a5e30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/e570ac2ecb5948ff90f52310841c2a23.png
[47f57938e1454dbd9aca766e75984e4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8e2ccf9a9c4842f580a4b556322b9ce3.png
[73c8f56b23884d208a9f8db319e51beb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/63cc37c8ec264d3d9f81158a43d1796d.png
[6cb3f1fcc66443da8b7a2cbd17418d93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/bb057d9839724d228a58440ed4d3de03.png
[ca0aa050195f4bff854893bb61f5f1cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3065c3b1aa7548598fcd59391fbb17a9.png
[6af4207f191a4f94956e3e4dbeb394a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/957422bde64d4d56b20386fa43f480ad.png
[02039d0fac6d453bab1bc1ffee004628.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ab145abf10984e34b6c8dc6f97e02df8.png
[cb7d202584fa40edacc4e417a2f37a85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7f7f724f8d3c43b1827135aa47dac08f.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/af32455d464a4503a77b103feeb43beb.png