PAT (甲级) 2022年夏季考试 c++ 满分题解

╰半夏微凉° 2023-09-24 15:02 26阅读 0赞

## PAT (甲级) 2022年夏季考试 c++ 满分题解 ##

### 7-1 What Day is Today ###

分数 20

#### 原题 ####

![在这里插入图片描述][96f2d0e5df084e899909c37bfe55ce7e.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 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;
    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;
    }
    ump<int,string> ump={
        {0, "Sunday"}, 
        {1, "Monday"}, 
        {2, "Tuesday"},
        {3, "Wednesday"},
        {4, "Thursday"},
        {5, "Friday"},
        {6, "Saturday"},
    };
    ump<int,string> um={
        {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 ###

分数 25

#### 原题 ####

![在这里插入图片描述][2fcbe409e4aa43129077f2d19d07bdd7.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 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;
    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();
        vector<int> a(m);
        vector<int> ans;
        rep(i, 0, m){
            a[i]=read();
        }
        int cnt = 0;
        for (int i=0, j=0; i<m; ++i){
        	// 新页面加入
            if(st[a[i]]==0){
                cnt+=1;
            }
            // 页面访问次数加一
            st[a[i]]+=1;
            // 页面数量 > Cache要求数量
            if (cnt>n){
            	// 进行LRU
                while(j<i){
                    // 页面访问次数减一
                    st[a[j]]-=1;
                	// 页面过期     
                    if(st[a[j]]==0){
                        ans.push_back(a[j]);
                        j++;
                        cnt-=1;
                        break;
                    }
                    j++;
                }
            }
        }
        printf("%lld", ans[0]);
        rep(i, 1, ans.size()){
        	printf("%lld", ans[i]);    
        }
    }

### 7-3 DFS Sequence ###

分数 25

#### 原题 ####

![在这里插入图片描述][8dad50623d9843759547291864896a89.png]  
![在这里插入图片描述][dd4ae30fe90d42f6b4b5706cede2f921.png]

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

dfs 图的遍历

#### 思路 ####

将序列中的元素依次入队，使用深度优先搜索，从队列的第一个元素进行搜索。  
如果当前节点能到达队列中下一个节点，则搜索下一个节点；  
如果不能到达队列中的下一个节点：  
a. 如果当前结点能够到达其他结点，则不是DFS序列；  
b. 如果不能到达其他结点，则回溯，返回到上一个结点继续搜索。（WA代码由于未回溯至上一个节点而是回溯至底继续搜索队列里的下一个结点）

#### 代码 ####

#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 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;
    int n, m, k, g[1010][1010], vis[1010], flag=1;
    vector<int>vec[1010];
    queue<int>q;
    set<int>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;
    }
    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<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 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, m, k; 
    bool g[108][108];
    bool st[N];
    vector<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;
    }
    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);
    	// 对每个结点，检查下一个结点是否合法
    	rep(i, 0, q.size()-1){
    		st[q[i]]=true;
    		// 如果当前节点已访问，返回否
    		if (st[q[i]]) return false; 
    		if(st[q[i+1]]){
    			return false;
    		}
    		// 下一个节点走过的话肯定false
    		if(g[q[i]][q[i+1]]){
    			continue;
    		}else{// 如果下个节点联通
    			rep(j, 1, n+1){// 如果序列的下一个结点不连通，并且存在一个已联通且未访问的结点
    				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函数  重定义容器大小
    	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 ###

分数 30

#### 原题 ####

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

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

树 dfs

#### 思路 ####

使用深度优先搜索保存层序遍历，再根据 父节点编号 = (子结点编号 - 1) / 度数 得出结点到根节点的路径。

#### 代码 ####

### 参考文献 ###

[2022夏PAT甲级题解 by小柳2022.6.7][2022_PAT_ by_2022.6.7]

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

[96f2d0e5df084e899909c37bfe55ce7e.png]: https://img-blog.csdnimg.cn/96f2d0e5df084e899909c37bfe55ce7e.png
[2fcbe409e4aa43129077f2d19d07bdd7.png]: https://img-blog.csdnimg.cn/2fcbe409e4aa43129077f2d19d07bdd7.png
[8dad50623d9843759547291864896a89.png]: https://img-blog.csdnimg.cn/8dad50623d9843759547291864896a89.png
[dd4ae30fe90d42f6b4b5706cede2f921.png]: https://img-blog.csdnimg.cn/dd4ae30fe90d42f6b4b5706cede2f921.png
[d9d8861acccb479b99a38475253a6d32.png]: https://img-blog.csdnimg.cn/d9d8861acccb479b99a38475253a6d32.png
[2022_PAT_ by_2022.6.7]: https://blog.csdn.net/l503301397/article/details/125224271
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png