pat甲級考試+pat1051+1056

同上一篇部落格；

貪心題目我已經刷了將近30道了，由於那幾天考駕照就沒寫，以後有空的時候補過來吧，都在codeblock裡

pat的題也刷了點，acwing 的題也刷了點，基本都攢下了。以後也會慢慢補過來的

這幾天都在備戰四級，上午司機下午演演算法，有點忙不過來就一直沒寫部落格，今天打完比賽就想趁熱寫一下吧，正好昨天也做了22年夏的甲級考試

來說說pat甲級：

第一次做pat甲級考試真題感受，一共4道題須在3個小時內做完，我感覺這真的是時間很充裕了

同時四道題的難度可能也是逐級拉開的，通常甲級前兩道題是可以A出來的，對於高手們來講滿分直接輕輕鬆鬆，但是或許我甲級題庫刷的還不少很多並且很多演演算法和資料結構有點手生了，就比如二元樹和圖論的一些演演算法就不太會寫了。。。。。甚至第三道題建立鄰接表的時候我都在想鄰接表是怎麼寫來著？？？

所以說第一次做就只做了前兩道

在經過和隊友的討論和演演算法構思上把第三道自己不會的題目也是順利切了，最後一道題是考的完全多叉樹的遍歷，由於樹的知識點還沒有開始全面複習就只能等刷完list之後在補了

題目大意：兩小兒爭辯日期，A小兒和B小兒分別說了三個日期：y(昨天),td(今天），tom(明天，喲，這不快明天了嗎)，並且這兩個小兒說的話每人只有一句真話，確認今天的同時輸出today並且輸出那兩句話為真並且輸出他們是y or td or tom；

題目思路：他們兩個人每人只有一句話為真，所以我們只要是標記他們的話與1~7的匹配，如果他們匹配次數都是1，就說明他們的話不僅連了起來並且那兩句話是真話，

打的string表在標記後輸出就可以了；

 1 #include<bits/stdc++.h>//2022 pat 甲級1
 2 using namespace std;
 3 #define int long long
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 int a,b,c;
 6 int d,e,f;
 7 int yes[10]={6,0,1,2,3,4,5};
 8 int fut[10]={1,2,3,4,5,6,0};
 9 string day[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
10 int cur1;
11 int cur2;
12 int flag1;
13 int flag2;
14 string t[7]={"yesterday","today","tomorrow"};
15 signed main()
16 {
17     IOS;
18     cin>>a>>b>>c>>d>>e>>f;
19     for(int i=0;i<7;i++)
20     {
21         int cur1=0,cur2=0;
22         int flag1=0,flag2=0;
23         if(a==yes[i])
24         {
25             cur1++;
26             flag1=0;
27         }
28         if(b==i)
29         {
30             cur1++;
31             flag1=1;
32         }
33         if(c==fut[i])
34         {
35             cur1++;
36             flag1=2;
37         }
38         if(d==yes[i])
39         {
40             cur2++;
41             flag2=0;
42         }
43         if(e==i)
44         {
45             cur2++;
46             flag2=1;
47         }
48         if(f==fut[i])
49         {
50             cur2++;
51             flag2=2;
52         }
53         if(cur1==1&&cur2==1)
54         {
55             cout<<day[i]<<endl;
56             cout<<t[flag1]<<endl;
57             cout<<t[flag2];
58             return 0;
59         }
60     }
61     return 0;
62 }

題目大意：模擬LRU演演算法，所謂的LRU演演算法就是存取頁面次數最小的網頁會在進來新網頁的時候被kick off

面向樣例：

6，

題目思路：

沒采用dfs一是因為怕爆棧，二是因為dfs在處理沒有下一個地址的時候的回溯和對於重複走的點的處理有點麻煩了，就選擇了模擬dfs

參考程式碼：

#include<bits/stdc++.h>//pat夏甲級3
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N=1e4+10;
vector<int>G[N];
int s[N];
bool vis[1010];
bool f[1010][1010];
int t[1010];
signed main()
{
    IOS;
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        f[a][b]=true;
        G[a].push_back(b);
    }
    while(k--)
    {
        memset(t,0,sizeof(t));
        memset(vis,false,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            cin>>s[i];
            t[s[i]]++;
        }
        bool flag1=true;
        for(int i=0;i<n;i++){
            if(t[s[i]]!=1)
                flag1=false;
        }
        bool flag2=true;
        for(int i=0;i<n;i++)
        {
            int st=s[i];
            int ed=s[i+1];
            vis[st]=true;
            if(!f[st][ed])
            {
                for(int j=0;j<G[st].size();j++)
                {
                    int v=G[st][j];
                    if(!vis[v])
                    {
                        flag2=false;
                    }
                }
            }
        }
        if(flag1&&flag2)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

太困了太困了，有些細節沒寫，明天再寫吧，困死我了