PAT(甲級)2022年夏季考試c++滿分題解-創(chuàng)新互聯(lián)

PAT (甲級) 2022年夏季考試 c++ 滿分題解 7-1 What Day is Today

分數(shù) 20

創(chuàng)新互聯(lián)為您提適合企業(yè)的網(wǎng)站設(shè)計?讓您的網(wǎng)站在搜索引擎具有高度排名，讓您的網(wǎng)站具備超強的網(wǎng)絡(luò)競爭力！結(jié)合企業(yè)自身，進行網(wǎng)站設(shè)計及把握，最后結(jié)合企業(yè)文化和具體宗旨等，才能創(chuàng)作出一份性化解決方案。從網(wǎng)站策劃到做網(wǎng)站、網(wǎng)站設(shè)計， 我們的網(wǎng)頁設(shè)計師為您提供的解決方案。原題

在這里插入圖片描述

算法標簽

模擬 枚舉

思路

依題意模擬

代碼
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
const int N = 10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
inline int read(){
   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);
}
int ff(int a,int b, int c, int d, int e, int f, int dd){
    int cnt=0;
    int x, y, z;
    if(dd==0){
        x=a;
        y=(a+1)%7;
        z=(a+2)%7;
    }
    else if(dd==1){
        x=(b-1+7)%7;
        y=b;
        z=(b+1)%7;
    }else if(dd==2){
        y=(c-1+7)%7;
        x=(c-2+7)%7;
        z=c;
    }
    if(d==x){
        cnt+=1;
    }if(e==y){
        cnt+=2;
    }if(f==z){
        cnt+=4;
    }
    return cnt;
}
umpump={
    {0, "Sunday"}, 
    {1, "Monday"}, 
    {2, "Tuesday"},
    {3, "Wednesday"},
    {4, "Thursday"},
    {5, "Friday"},
    {6, "Saturday"},
};
umpum={
    {0, "yesterday"}, 
    {1, "today"}, 
    {2, "tomorrow"},
};
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a=read(),b=read(), c=read();
	int d=read(),e=read(), f=read();
	int t;
	rep(i, 0, 3){
	    int aa=ff(a, b, c, d, e, f, i);
	        if(aa==1){
	            int t=(d+1)%7;
	            printf("%s\n%s\nyesterday\n", ump[t].c_str(), um[i].c_str());
                break;
	        }else if(aa==2){
	            int t=(e)%7;
	            printf("%s\n%s\ntoday\n", ump[t].c_str(), um[i].c_str());
                break;
	        }else if(aa==4){
	            int t=(f-1+7)%7;
	            printf("%s\n%s\ntomorrow\n", ump[t].c_str(), um[i].c_str());
                break;
	        }
	}
	return 0;
}
7-2 Least Recently Used Cache

分數(shù) 25

原題

在這里插入圖片描述

算法標簽

模擬

思路

依題意模擬， 具體思路見代碼

代碼
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
const int N = 100005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
int st[N];
inline int read(){
   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(){
    int n=read(), m=read();
    vectora(m);
    vectorans;
    rep(i, 0, m){
        a[i]=read();
    }
    int cnt = 0;
    for (int i=0, j=0; iCache要求數(shù)量
        if (cnt>n){
        	// 進行LRU
            while(j
7-3 DFS Sequence

分數(shù) 25

原題

在這里插入圖片描述
在這里插入圖片描述

算法標簽

dfs 圖的遍歷

思路

將序列中的元素依次入隊，使用深度優(yōu)先搜索，從隊列的第一個元素進行搜索。
如果當前節(jié)點能到達隊列中下一個節(jié)點，則搜索下一個節(jié)點；
如果不能到達隊列中的下一個節(jié)點：
a. 如果當前結(jié)點能夠到達其他結(jié)點，則不是DFS序列；
b. 如果不能到達其他結(jié)點，則回溯，返回到上一個結(jié)點繼續(xù)搜索。（WA代碼由于未回溯至上一個節(jié)點而是回溯至底繼續(xù)搜索隊列里的下一個結(jié)點）

代碼
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pairPII;
const int N=10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
int n, m, k, g[1010][1010], vis[1010], flag=1;
vectorvec[1010];
queueq;
sets;
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 dfs(int x){
	if(flag==0||q.empty()){
		return;
	}
	vis[x]=1;
	while(!q.empty()){
		if(g[x][q.front()]==1){
			int y=q.front();
			q.pop();
			dfs(y);
		}
		else{
			rep(i, 0, vec[x].size()){
				if(!vis[vec[x][i]]){
					flag=0;
					return;
				}
			}
			return;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=rd(), m=rd(), k=rd();
	while(m--){
		int x=rd(), y=rd();
		g[x][y]=1;
		vec[x].push_back(y);
	}
	while(k--){
		memset(vis,0,sizeof vis);
		flag=1;
		while(!q.empty()){
			q.pop();
		}
		s.clear();
		rep(i, 0, n){
			int x=rd();
			q.push(x);
			s.insert(x);
		}
		while(!q.empty()){
			int y=q.front();
			q.pop();
			dfs(y);
		}		
		if(flag==0||s.size()!=n){
			puts("no");	
		}
		else{
			puts("yes");	
		}
	}
	return 0;
}
WA代碼
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pairPII;
const int N=10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
//int t, n, m, cnt, ans;
int n, m, k; 
bool g[108][108];
bool st[N];
vectorq;
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 ch(){
	memset(st, 0, sizeof st);
	// 對每個結(jié)點，檢查下一個結(jié)點是否合法
	rep(i, 0, q.size()-1){
		st[q[i]]=true;
		// 如果當前節(jié)點已訪問，返回否
		if (st[q[i]]) return false; 
		if(st[q[i+1]]){
			return false;
		}
		// 下一個節(jié)點走過的話肯定false
		if(g[q[i]][q[i+1]]){
			continue;
		}else{// 如果下個節(jié)點聯(lián)通
			rep(j, 1, n+1){// 如果序列的下一個結(jié)點不連通，并且存在一個已聯(lián)通且未訪問的結(jié)點
				if(g[q[i]][j]&&!st[j]){
					return false;
				}
			}
		}
	}
	return true;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=rd(), m=rd(), k=rd();
	memset(g, 0, sizeof g);
	while(m--){
		int a=rd(), b=rd();
		g[a][b]=true;
	}
	// resize函數(shù)  重定義容器大小
	q.resize(n);
	while(k--){
		rep(i, 0, n){
			q[i]=rd();
		}
		bool fl=ch();
		if(fl){
			puts("yes");
		}else{
			puts("no");
		}
	}
	return 0;
}
7-4 Complete D-Tree

分數(shù) 30

原題

在這里插入圖片描述

算法標簽

樹 dfs

思路

使用深度優(yōu)先搜索保存層序遍歷，再根據(jù) 父節(jié)點編號 = (子結(jié)點編號 - 1) / 度數(shù) 得出結(jié)點到根節(jié)點的路徑。

代碼
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pairPII;
const int N=55, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
//int t, n, m, cnt, ans;
// pre存儲前序遍歷序列 le存儲層序遍歷序列 n d k如題意 p前序遍歷節(jié)點下標
int pre[N], le[N], n, d, k, p; 
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;
	}
	le[u]=pre[p++];
	rep(i, 1, d+1){
		dfs(u*d+i);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=rd(), d=rd();
	rep(i, 0, n){
		pre[i]=rd();
	}
	dfs(0);
	printf("%lld", le[0]);
	rep(i, 1, n){
		printf(" %lld", le[i]);
	}
	puts("");
	k=rd();
	while(k--){
		int x=rd();
		while(x){
			printf("%lld ", le[x]);
			x=(x-1)/d;
		}
		printf("%lld\n", le[0]);
	}
	return 0;
}
參考文獻

2022夏PAT甲級題解 by小柳2022.6.7

原創(chuàng)不易
轉(zhuǎn)載請標明出處
如果對你有所幫助 別忘啦點贊支持哈
在這里插入圖片描述

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文標題：PAT(甲級)2022年夏季考試c++滿分題解-創(chuàng)新互聯(lián)
文章分享：http://muchs.cn/article30/djhdpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、用戶體驗、ChatGPT、品牌網(wǎng)站設(shè)計、軟件開發(fā)、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)