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表在标记后输出就可以了；

#include//2022 pat 甲级1
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int a,b,c;
int d,e,f;
int yes[10]={6,0,1,2,3,4,5};
int fut[10]={1,2,3,4,5,6,0};
string day[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
int cur1;
int cur2;
int flag1;
int flag2;
string t[7]={"yesterday","today","tomorrow"};
signed main()
{
    IOS;
    cin>>a>>b>>c>>d>>e>>f;
    for(int i=0;i<7;i++)
    {
        int cur1=0,cur2=0;
        int flag1=0,flag2=0;
        if(a==yes[i])
        {
            cur1++;
            flag1=0;
        }
        if(b==i)
        {
            cur1++;
            flag1=1;
        }
        if(c==fut[i])
        {
            cur1++;
            flag1=2;
        }
        if(d==yes[i])
        {
            cur2++;
            flag2=0;
        }
        if(e==i)
        {
            cur2++;
            flag2=1;
        }
        if(f==fut[i])
        {
            cur2++;
            flag2=2;
        }
        if(cur1==1&&cur2==1)
        {
            cout<endl;
            cout<endl;
            cout<<t[flag2];
            return 0;
        }
    }
    return 0;
}

 

 题目大意：模拟LRU算法，所谓的LRU算法就是访问页面次数最小的网页会在进来新网页的时候被kick off

面向样例：

 

6，

可以这样来看（其实上图已经很明确了....）

4 11
1 2 3 1 4 5 2 1 5 6 3

先进来的是1，2，3，1四个网页，并且当前网页1的访问次数是2，所以说当前网页2是LRU状态，在进来网页4，达到满值n，再进来网页5，网页2是LRU状态被开，再进来网页2，网页3是LRU状态被开，再进来网页1，网页4是LRU状态被开并且网页1的访问次数是3，在5,6，3........

那怎么来写代码呢

首先直观感受是用queue了，并且还有一个数组来记录被开的网页和记录网页访问次数的数组，所以说可以酱紫分析：

首先是将每个网页入队，如果没有达到满值状态就记入队并且记录网页访问次数，同时未被访问的网页入队的时候计数器也要加一；

当计数器大于n时候也就是达到满值状态的时候，首先要考虑这个网页没有被访问过的情况

如果它没有被访问过，我们要找的肯定是下一个LRU状态就是按照次序删除访问页最少的网页，所以就每次取队头找最少访问网页，找到以后直接进入记录数组且出队并且减少访问次数（因为已经被弹出了）

参考代码：

#include//2022 pat 甲级2
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N=1e5+10;
//int a[N];
//mapp;
int f[N];
queue<int>p;
vector<int>q;
int n,m;
int cnt;
signed main()
{
    IOS;
    cin>>n>>m;
    for(int i=0;i)
    {
        int a;
        cin>>a;
        if(cnt<n)
        {
           p.push(a);
           if(!f[a])
           cnt++;
           f[a]++;
        }
        else
        {
            if(!f[a])
            {
                while(f[p.front()]!=1)
                {
                    f[p.front()]--;
                    p.pop();
                }
                q.push_back(p.front());
                f[p.front()]--;
                p.pop();
            }
            p.push(a);
            f[a]++;
        }
    }
    for(int i=0;i)
    {
        cout<<q[i];
        if(i1)
            cout<<" ";
    }
    return 0;
}

 

 

 

 题目思路：

 

 

 

 

 没采用dfs一是因为怕爆栈，二是因为dfs在处理没有下一个地址的时候的回溯和对于重复走的点的处理有点麻烦了，就选择了模拟dfs

参考代码：

#include//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)
    {
        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)
        {
            cin>>s[i];
            t[s[i]]++;
        }
        bool flag1=true;
        for(int i=0;i){
            if(t[s[i]]!=1)
                flag1=false;
        }
        bool flag2=true;
        for(int i=0;i)
        {
            int st=s[i];
            int ed=s[i+1];
            vis[st]=true;
            if(!f[st][ed])
            {
                for(int j=0;j)
                {
                    int v=G[st][j];
                    if(!vis[v])
                    {
                        flag2=false;
                    }
                }
            }
        }
        if(flag1&&flag2)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

太困了太困了，有些细节没写，明天再写吧，困死我了

-------------------------------------------------------------------------------------------------------------

分割线 2022-8-7更

pat甲级1051：https://pintia.cn/problem-sets/994805342720868352/problems/994805427332562944

题目大意：讲的是给定三个数分别是栈的最大容量，给定一个长度n的一组数和k次测试

问判断这k次测试中有多少组数是合法的栈的出栈序列

题目思路：模拟栈的出站序列，刚开始我利用数据结构中那个栈的结论卡特兰数，但是这个求的是合法性，就作罢，老老实实些栈

其实可以这样做：

面向样例：

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

我们要得到一个1~n的合法出站序列，就从1开始入栈，如果是在没有满栈的情况下出栈的元素要与输入的元素是相等的

为了方便解释请看

 

 我们要得到合法序列，就要每次第i个数入栈的时候，判断与a[i]是否一致，如果不一致继续入栈判断就好了

但是如果相等，就是栈顶元素和当前的a[i]相等（前提是未满栈），我们就要将进来的栈的数量+1，一旦当达到满栈的时候就是表明这个序列是不能够顺序满足栈的正确走向的，也就是不少合法序列，拿上图来说是酱紫的，1，2，3，4，5，6也可以

参考代码:

#include//pat甲级1051
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int a[1010];
int n;//数字串的数量
int m;//栈的容量
int k;
int b[1010][1010];
signed main()
{
    IOS;
    cin>>m>>n>>k;
    while(k--)
    {
        stack<int>q;
        int c=1;
        bool flag=true;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            q.push(i);
            if(q.size()>m)
            {
                flag=false;
                break;
            }
            while(!q.empty())
            {
                if(q.top()!=a[c])
                    break;
                q.pop();
                c++;
            }
        }
        if(flag&&q.empty())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

pat1056：https://pintia.cn/problem-sets/994805342720868352/problems/994805419468242944

题目大意：题目的意思有点绕，我读了好几遍才大致了解讲了个啥

就是m和r是一个编程比赛，这个编程比赛是要求每个玩家控制小老鼠吃东西的一个游戏，这个游戏的目的是找出最胖的小老鼠

下面是重点：

我们有np个玩家控制的小老鼠的体重，并且每ng个小老鼠一组，在组内决出最胖老鼠并进入下一轮，最后决出最胖的老鼠

输入是

老鼠的数量，几个老鼠一组

np只老鼠重量

np个老鼠编号

并且要按照老鼠的编号每ng老鼠一组

题目思路：

有点难搞的其实，我最初的思路是进行一个模拟，通过三个数组来标记失败的，进入下一轮的和排名，但是这样做的话就会导致信息记录不全并且代码上也不好实现，因为这个思路虽然显而易见但是每轮比赛每只老鼠的排名记录就很难搞

其实可以这样做：

面向样例分析

11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3

样例是挺容易分析的，怎么做呢？

我们知道进行比赛的轮数实际上就是一共有几组老鼠，因为每轮比赛决出每一组内最胖的老鼠，而题目的要求是决出最胖老鼠，所以说没决出一轮比赛就是要淘汰组内的其他老鼠，每次取1淘汰ng-1；

这样的话我们每次进行g组比赛就是老鼠的组数次比赛，就就可以得到最胖的老鼠；

其次在每轮比赛的每组决胜中，我们挑出最大的老鼠，所以说接每轮比赛中决出最大老鼠后被淘汰的老鼠名次得rank=g+1，就是老鼠的组数在进1，

同时每进行一轮比赛比赛的老鼠的只数就是上一轮的组数，这样是因为上一轮中共有t/ng组，每组决1，所以说就有t/ng组老鼠晋级，也就是当前有多少老鼠在决赛

参考代码：（有些细节，写写注释）

#include
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int np,ng;
queue<int>q;
struct node
{
    int weight;
    int rate;
}m[1010];
signed main()
{
    IOS;
    cin>>np>>ng;
    for(int i=0;i)
    {
        cin>>m[i].weight;
    }
    for(int i=0;i)
    {
        cin>>m[i].rate;
        q.push(m[i].rate);//讲老鼠的排名入队
    }
    int g=0,t=np;
    while(q.size()!=1)
    {
        if(t%ng)//两种组数情况
            g=t/ng+1;
        else
            g=t/ng;
        for(int i=0;i//每轮比赛
        {
            int k=q.front();
            for(int j=0;j//组内决赛
            {
                if(i*ng+j>=t)//为了适配当最后一组老鼠不满足ng只的时候推出循环，因为是每ng只老鼠找最胖的
                    break;
                int f=q.front();
                if(m[f].weight>m[k].weight)//组内找最胖的
                {
                    k=f;
                }
                m[f].rate=g+1;//被淘汰的赋g+1
                q.pop();//出队
            }
            q.push(k);//进入下一轮
        }
        t=g;//下一轮只数是晋级的老鼠
    }
    m[q.front()].rate=1;//只剩下最后一只是最胖的
    for(int i=0;i)
    {
        cout<<m[i].rate;
        if(i1)
            cout<<" ";
    }
    return 0;
}