题解：P8727 [蓝桥杯 2020 国 A] 填空问题

· · 题解

::::info[试题 A ：合数个数]{open} 合数是啥，合数就是，每个数都有因数。因此数就分为了三部分。

第一部分，质数

质数就是因数只有两个数的数，注意 2 也是质数。

第二部分，合数

合数就是因数两个以上的数，例如 9 就是个合数。

第三部分，既不是质数也不是合数

所以，我们知道，我们只需一个 pd 多少个因数就行。但要特判 1 这个情况。

用一个判断函数，从 1 到 2020 遍历判断

#include<iostream>
using namespace std;
bool pd(int x)
{
    if(x<2) return 1;
    else
    {
        for(int i=2;i*i<=x;i++)//注意i*i,不要写成i ，会超时的
        {
            if(x%i==0) return 1; 
        }
        return 0;
    }
}
int main()
{
   int ans=0;
    for(int i=1;i<=2020;i++)
    {
        if(pd(i)==1) ans++;
    }
    cout<<ans;
return 0;
}

最后输出 1713 为答案。 :::: ::::info[试题 B ：含 2 天数]{open} 我们首先要知道每月天数，这个可以开个 m_i 来标记。

int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

但是，如果有一年是闰年，二月就会变为 29 天，所以我们要特判闰年情况。

if((i%4==0&&i%100!=0)||(i%400==0))
{
    m[2]=29;
}
else
{
    m[2]=28;
}

然后，判断是否有 2 了，我们从后往前挨个判断。

  while(x>0)
  {
    int p=x%10;
    if(p==2) return 1;
    x/=10;
    return 0;
  }

最后的代码。

#include<bits/stdc++.h>
using namespace std;
int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans=0;
int pd(int x)
{
    while(x)
    {
        if(x%10==2)
        {
            return 1;
        }
        x/=10;
    }
    return 0;
}
int main()
{
    for(int i=1900;i<=9999;i++)
    {
        if((i%4==0&&i%100!=0)||(i%400==0))
        {
            m[2]=29;
        }
        else
        {
            m[2]=28;
        }
        for(int moon=1;moon<=12;moon++)
        {
            for(int day=1;day<=m[moon];day++)
            {
                if(pd(i)||pd(moon)||pd(day))
                {
                    ans++;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

最后输出 1994240 为答案。 :::: ::::info[试题 C ：本质上升序列]{open} 这是一道动态规划，我们要求出他给定字符串本质不同的单调递增子序列个数。求出 a_1 一直到 a_{200} 加起来的本质不同的单调递增子序列个数。

#include<bits/stdc++.h>
using namespace std;
int a[201],ans;
string s="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl"; 
int main()
{
    for(int i=0;i<200;i++)
    {   
        a[i]=1;
        for(int j=0;j<i;j++)
        {
            if(s[i]==s[j])
            {
                a[i]=0;
            }
            else if(s[j]<s[i])
            {
                a[i]+=a[j];
            }
        }
        ans+=a[i];
    }
    cout<<ans;
    return 0;
}

:::: ::::info[试题 D：咫尺天涯]{open} 求第 12 阶皮亚诺曲线中所有相邻格子在曲线上的距离之和。

我们设 f(k) 为 k 阶曲线的距离和。则 f(k)=9×f(k−1)+水平边界距离和+垂直边界距离和。

边界距离计算使用递归函数计算每个格子在曲线上的坐标，然后对边界上的相邻点计算距离差并求和即可。

结果为：184731576397539360。 :::: ::::info[试题 E：玩具蛇]{open} 运用深度优先搜索，枚举蛇的起点，从起点出发，向四个方向扩展，检查新位置是否在方格内且未被占用。输出即可。 :::: ::::success[AC代码]

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "1713", 
        "1994240", 
        "3616159", 
        "184731576397539360", 
        "552", 
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}

::::