Home 2022 夏季 PAT 甲级
Post
Cancel

2022 夏季 PAT 甲级

7-1 What Day is Today (20分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int a[3],b[3],ax,bx,day[3];
string str[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
string strr[3]={"yesterday","today","tomorrow"};
int main() {
    for(int i=0;i<3;++i)
        scanf("%d",&a[i]);
    for(int i=0;i<3;++i)
        scanf("%d",&b[i]);
    for(int i=0;i<3;++i){
        for(int j=0;j<3;++j){
            if((a[i]==(b[j]+i-j+7)%7)&&(a[(i+1)%3]!=(a[i]+((i+1)%3-i)+7)%7)&&(a[(i+2)%3]!=(a[i]+((i+2)%3-i)+7)%7)&&(b[(j+1)%3]!=(b[j]+((j+1)%3-j)+7)%7)&&(b[(j+2)%3]!=(b[j]+((j+2)%3-j)+7)%7)){
                ax=i,bx=j;
                day[i]=a[i];
                day[(i+1)%3]=(a[i]+((i+1)%3-i)+7)%7;
                day[(i+2)%3]=(a[i]+((i+2)%3-i)+7)%7;
                cout<<str[day[1]]<<endl<<strr[ax]<<endl<<strr[bx];
                return 0;
            }
        }
    }
    return 0;
}

7-2 Least Recently Used Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
queue<int>q;
int n,m,a,num[100010],cnt;
vector<int>ans;
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&a);
        if(cnt<n){
            q.push(a);
            if(num[a]==0) cnt++;
            num[a]++;
        }else{
            if(num[a]==0){
                while(num[q.front()]!=1){
                    num[q.front()]--;
                    q.pop();
                }
                num[q.front()]--;
                ans.push_back(q.front());
                q.pop();
            }
            q.push(a);
            num[a]++;
        }
    }
    for(int i=0;i<ans.size();++i){
        if(i!=0) printf(" ");
        printf("%d",ans[i]);
    }
    return 0;
}

7-3 DFS Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n,m,k,a[1010];
bool g[1010][1010],v[1010],flag;
vector<int>to[1010];
void DFS(int x){
    if(!flag||x>=n) return;
    if(v[a[x+1]]){
        // cout<<a[x+1]<<endl;
        flag=false;
        return;
    }
    if(!g[a[x]][a[x+1]]){
        for(int i=0;i<to[a[x]].size();++i)
            if(!v[a[to[a[x]][i]]]){
                flag=false;
                break;
            }
        return;
    }else{
        v[a[x+1]]=true;
        DFS(x+1);
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i){
        int s,t;
        scanf("%d%d",&s,&t);
        g[s][t]=true;
        to[s].push_back(t);
    }
    while(k--){
        memset(v,false,sizeof(v));
        flag=true;
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        v[a[1]]=true;
        DFS(1);
        printf("%s\n",flag?"yes":"no");
    }
    return 0;
}

7-4 Complete D-Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n,d,k,a,p,pre[55],level[55];
void DFS(int x){
    if(x>=n) return; //judge x, not p
    level[x]=pre[p++];
    for(int i=1;i<=d;++i)
        DFS(x*d+i);
}
int main() {
    scanf("%d%d",&n,&d);
    for(int i=0;i<n;++i)
        scanf("%d",&pre[i]);
    DFS(0);
    for(int i=0;i<n;++i){
        if(i!=0) printf(" ");
        printf("%d",level[i]);
    }
    printf("\n");
    scanf("%d",&k);
    while(k--){
        scanf("%d",&a);
        while(a){
            printf("%d ",level[a]);
            a=(a-1)/d;
        }
        printf("%d\n",level[a]);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.