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

wuhan1234 · 2023-04-08 12:13:24 · 题解

A 合数个数

直接用循环进行枚举搜索。编写的函数如下。

void work1()
{
    int ans=0;
    for (int i=4;i<=2020;i++)
    {
        int j;
        for (j=2;j*j<=i;j++)
            if (i%j==0) break;
        if (j*j<=i) ans++;
    }
    printf("%d\n", ans);
}

执行上面的处理函数，输出结果为：1713。

B 含 2 天数

直接用循环对每一天进行枚举判断，若年、月、日数字中含有 2，则计数。 编写的函数如下。

int check(int x)   // 判断整数x 中是否含有数字 2
{
    while(x)
    {
        if (x%10==2) return 1;
        x/=10;
    }
    return 0;
}
void work2()
{
    int month[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},
                      {0,31,29,31,30,31,30,31,31,30,31,30,31}};
    int y,m,d,ans=0;
    for (y=1900;y<=9999;y++)
    {
        int f;
        if (y%400==0||(y%4==0 && y%100!=0)) f=1;
        else f=0;
        for (m=1;m<=12;m++)
        {
            for (d=1;d<=month[f][m];d++)
            {
                if (check(y)||check(m)||check(d)) ans++;
            }
        }
    }
    printf("%d\n", ans);
}

执行上面的处理函数，输出结果为：1994240。

C 本质上升序列

用线性动态规划进行求解。

定义状态 dp_i 表示以字符 s_i 结尾的本质不同的方案数。

由于第 i 个字符的状态只会和前 i-1 个字符有关，因此我们需要枚举前 i-1 个字符。

当前 i-1 个字符中有某个字符 s_j 和 s_i 相同时，那么就会出现重复的方案；但是由于 dp_i 是一定已经包含了 dp_j 的，所以为了避免重复，可以令 dp_j=0。

当前 i-1 个字符中有某个字符 s_j 小于 s_i 时，那么 dp_i=dp_i+dp_j。因为 s_i>s_j，所以直接在以 s_j 结尾的本质上升序列结尾加一个字符 s_i，这样也是一个本质上升序列。这样可以继承 dp_j 的所有可行方案。

当前 i-1 个字符中有某个字符 s_j 大于 s_i 时，直接跳过即可。

最后结果便是 dp_1+dp_2+…+dp_{200}。

编写的函数如下。

void work3()
{
    int dp[210]={0};
    char s[210]="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl";
    int ans = 0;
    int i,j;
    for (i=0;i<strlen(s);i++)
    {
        dp[i]=1;
        for (j=0;j<i;j++)
        {
            if (s[i]==s[j]) dp[i]=0;
            else if (s[j]<s[i]) dp[i]+=dp[j];
        }
    }
    for (i=0;i<strlen(s);i++)  ans+=dp[i];
    printf("%d\n", ans);
}

执行上面的处理函数，输出结果为：3616159。

D 咫尺天涯

一个 k 阶的皮亚诺曲线有 3^k 行，每行 3^k 列，共 3^k\times 3^k 个格子，在这些格子中，每行中相邻的格子数有 3^k-1 个，每列中相邻的格子数也有 3^k-1 个，因此相邻的格子总数为 2\times 3^k \times (3^k-1) 个。

例如，1 阶皮亚诺曲线中相邻的格子有 2\times 3 \times (3-1)=12 个。