P8721 [蓝桥杯 2020 省 AB3] 填空问题 题解

· · 题解

P8721 题目

数青蛙

出现的数字一定为一位或两位，易知 1 到 10 有一个字，大于 10 的整十数有两个字，而几十几有三个字，我们从 1 枚举到 20 算出答案即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int zsh(int x)//计算字数的函数
{
    if(x<=10)
        return 1;
    if(x>10&&x<20||x%10==0)
        return 2;
    return 3;
}
signed main()
{
    int s=200;
    for(int i=1;i<=20;i++)//从1枚举到20
        s+=zsh(i)*2+zsh(i*2)+zsh(i*4);
    cout<<s;
    return 0;
}

答案为 353。

互质

两个数互质即两数最大公因数为 1，我们可以直接用最大公因数函数求出答案。

#include<bits/stdc++.h>
using namespace std;
signed main()
{
    int s=0;
    for(int i=1;i<=2020;i++)
    {
        if(__gcd(i,1018)==1)//__gcd可以求最大公因数
            s++;
    }
    cout<<s;
    return 0;
}

答案为 1008。

车牌

用深搜解决即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int s=0;
void dfs(int p,char sh,char shh,string x)//sh是上一个字符，shh是上上个字符
{
    if(p==7)//注意是7不是6
    {
        s++;
        return;
    }
    if(p<=3)
    {
        for(int i=0;i<=15;i++)
        {
            if(i<=9)
            {
                char h=i+'0';//h用来存储添加的字符
                if(!(sh==shh&&sh==h))
                    dfs(p+1,h,sh,x+h);
            }
            else
            {
                char h=char(i+55);
                if(!(sh==shh&&sh==h))
                    dfs(p+1,h,sh,x+h);              
            }
        }
    }
    else
    {
        for(int i=0;i<=9;i++)
        {
            char h=i+'0';
            if(!(sh==shh&&sh==h))
            dfs(p+1,h,sh,x+h);  
        }   
    }
}
signed main()
{
    dfs(1,'a','a',"");
    cout<<s;
    return 0;
}

答案为 4002750。

Fibonacci 集合

首先要注意 1 和 2 的 3 倍加 2，以及 1 的 5 倍加 3 已经在给出的前 5 个数中存在。

我们可以用 3 个队列储存产生的新数，但这样太麻烦了，其实只需要一个队列来维护生成的结果就可以了，只要用 3 个指针分别指向乘 3 加 2、乘 5 加 3 、乘 8 加 5 的位置，每次比较产生的 3 个新数，若最小的数未出现过，则取最小的数作为序列的下一个数，并将相应的指针向前移即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[3001]={0,1,2,3,5,8};
signed main()
{
    int p3=3,p5=2,p8=1;//3个指针
    for(int i=6;i<=2020;)
    {
        int t3=a[p3]*3+2;
        int t5=a[p5]*5+3;
        int t8=a[p8]*8+5;
        if(min(t3,min(t5,t8))!=a[i-1])//判断最小的数是否未出现过
        {
            a[i++]=min(t3,min(t5,t8));
            if(min(t3,min(t5,t8))==t3)//指针前移
                p3++;
            if(min(t3,min(t5,t8))==t5)
                p5++;
            if(min(t3,min(t5,t8))==t8)
                p8++;
        }
    }
    cout<<a[2020];
    return 0;
}

答案为 41269。

上升子串

这道题很明显是一道用深搜解决的题目，边深搜边计数即可。

由于本题缺少数据，以下为求解代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1002][1002],dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0},ss;
void dfs(int x,int y)//深搜
{
    for(int i=1;i<=4;i++)
    {
        int px=x+dx[i],py=y+dy[i];
        if(a[x][y]<a[px][py])
            ss++,dfs(px,py);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char ch;
            cin>>ch;
            a[i][j]=ch-'A'+1;
        }
    }
    int s=n*m;//先记录长度为1的上升子串
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            dfs(i,j);
    }
    cout<<s+ss;
    return 0;
}

Code

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "353",
        "1008",
        "4002750",
        "41269",
        "qwq",
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}