自动搬运

查看原文

来自洛谷，原作者为

	wuhan1234 **

搬运于2025-08-24 22:41:51，当前版本为作者最后更新于2023-04-08 08:20:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

A 美丽的 $2$

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

void work1()
{
    int ans = 0;
    for (int i = 1; i <= 2020; i++)
    {
        int t=i;
        while (t)
        {
            if (t % 10 == 2)  break;
            t /= 10;
        }
        if (t) ans++;
    }
    printf("%d\n", ans);
}

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

B 扩散

本题实际是求无限大的画布里与给出的四个点中至少一个点曼哈顿距离小于等于 $2020$ 的点有多少个。可以想到，$x$ 坐标小于 $−2025$ 或者大于 $4045$ 的点不可能满足这个条件，同理 $y$ 坐标小于 $−2025$ 或者大于 $4025$ 的点也不可能满足这个条件。用循环枚举这个范围内的点，统计有多少个满足条件的点。

编写的函数如下。

int abs(int x)
{
    return x>0?x:-x;
}
void work2()
{
    int px[4]={0,2020,11,2000};
    int py[4]={0,11,14,2000};
    int ans = 0;
    for (int i = -2025; i <= 4045; i++)
    {
        for (int j = -2025; j <= 4025; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (abs(i-px[k])+abs(j-py[k])<=2020)
                {
                    ans++;
                    break;
                }
            }
        }
    }
    printf("%d\n", ans);
}

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

C 阶乘约数

对于任何一个大于 $1$ 的正整数 $N$，都存在一个标准的质因子分解式：

$N=p_1^{a_1} \times p_2^{a_2} \times ...\times p_n ^{a_n}$ （其中 $p_i$ 为质数）

则正整数 $N$ 的约数个数为 $(a_1+1)\times (a_2+1)\times ...\times(a_n+1)$。

编写的函数如下。

int isPrime(int n)   // 判断n是否为质数
{
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0) return 0;
    }
    return 1;
}
void work3()
{
    int p[100],a[100],cnt=0;
    int i,j,t;
    for (i = 2; i <= 100; i++)   // 将100以内的质数保存起来
    {
        if (isPrime(i))
        {
            p[cnt]=i;
            a[cnt]=0;     // 初始时含质因子p[i]的因子个数 a[i]=0
            cnt++;
        }
    }
    for (i = 2; i <= 100; i++)   // 将1~100中每个数的质因子分解的因子数累加起来
    {
        j = 0;
        t=i;
        while (j<cnt && p[j] <= t)
        {
            while (t % p[j] == 0)
            {
                t /= p[j];
                a[j]++;
             }
             j++;
        }
    }
    long long ans = 1;
    for (i = 0; i < cnt; i++)
    {
        ans *= (a[i] + 1);
    }
    printf("%lld\n", ans);
}

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

D 本质上升序列

用动态规划进行求解。 设 $dp_i$ 表示以字符 $s_i$ 为结尾的本质上升子序列个数。

因为每一个字母都算一个序列，所以 $dp_i$ 初始化为 $1$。之后利用 $dp_0 \sim dp_{i-1}$ 来更新 $dp_i$。转移方程为：

若 $s_j<s_i$ $(j<i)$，则有 $dp_i=dp_i+dp_j$。

若 $s_j=s_i (j<i)$，则有 $dp_i=dp_i-dp_j$。

上面的转移方程可以这样理解。在更新 $dp_i$，遍历字符 $s_0\sim s_{i-1}$。如果 $s_j<s_i$，就直接加上 $dp_j$，相当于直接在以第 $j$ 个字符 $s_j$ 结尾的本质上升序列结尾加一个字符 $s_i$，这样也是一个本质上升序列；如果 $s_i=s_j$，就减去 $dp_j$，因为前面利用 $dp_0 \sim dp_{j-1}$ 进行更新 $dp_i$ 时就相当于利用 $dp_j$ 来更新 $dp_i$，因为最后一个字母为 $s_i$ 的代价已经被计算进 $dp_j$ 中，所以要减去这部分。

编写的函数如下。

void work4()
{
    int dp[210]={0};
    char s[210]="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl";
    int ans = 0;
    int i,j;
    for (i = 0; s[i]!='\0'; i++)
    {
        dp[i]=1;
        for (j = 0; j < i; j++)
        {
            if (s[j] < s[i])
            {
                dp[i] += dp[j];
            }
            else if (s[i]==s[j])
                dp[i]-=dp[j];    // 减去重复计算的部分
        }
        ans += dp[i];
    }
    printf("%d\n", ans);
}

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

E 玩具蛇

从 $16$ 个方格中的每个方格作为起点，分别用 DFS 进行搜索，若从某个起点出发能走 $16$ 步，则就是一种可行的方案。

编写的函数如下。

int dx[4]={1, -1, 0, 0};
int dy[4]={0, 0, 1, -1};
int ans=0;
int vis[16];
int len;
void dfs(int n)
{
    if (len == 16)
    {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = n / 4 + dx[i];
        int ny = n % 4 + dy[i];
        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4)
            continue;
        int next = 4 * nx + ny;
        if (!vis[next])
        {
            vis[next] = 1;
            len++;
            dfs(next);
            vis[next] = 0;
            len--;
        }
    }
}
void work5()
{
    for (int i = 0; i < 16; i++)
    {
        vis[i] = 1;
        len++;
        dfs(i);
        vis[i] = 0;
        len--;
    }
    printf("%d\n", ans);
}

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

有了上面的处理结果，提交给本题的源程序如下。

#include <stdio.h>
#include <string.h>
int main()
{
    char T;
    scanf("%c",&T);
    if (T=='A') printf("563\n");
    else if (T=='B') printf("20312088\n");
    else if (T=='C') printf("39001250856960000\n");
    else if (T=='D') printf("3616159\n");
    else if (T=='E') printf("552\n");
    return 0;
}