蓝桥杯每日真题 - 第8天

题目：（子2023）

题目描述（14届 C&C++ B组A题）

解题思路：

该代码通过动态计算包含数字 "2023" 的子序列出现次数。主要思路是：

1. 拼接序列：将1到2023的所有数字按顺序拆分为单个数字，并存储在数组arr中。

2. 统计“2023”子序列：遍历数组中的数字，使用计数器分别记录数字2、0、3的累积出现次数，并通过组合计算出符合条件的 "2023" 子序列。

代码实现（C语言）：

#include <stdio.h>
#include <stdlib.h>
long long solve(long long i)
{long long sum=1;while(i/=10)sum++;return sum;
}
int main(int argc, char *argv[])
{long long i,j,n=0,a=0,b=0,c=0,d=0;long long arr[10000];for(i=1;i<=2023;i++){int I=i;int T=solve(i);for(j=T;j>0;j--){arr[n+j]=I%10;I/=10;}n+=T;}for(i=1;i<=n;i++){if(arr[i]==2){a++;c+=b;}else if(arr[i]==0)b+=a;else if(arr[i]==3)d+=c;}printf("%lld",d);return 0;
}

得到运行结果：

代码分析 ：

• solve() 函数：计算一个数字的位数。通过不断除以10来计算位数。例如，2023 返回 4。

• main() 函数：

  • 序列拼接：

    • 使用 for 循环，将1到2023的每个数字按位拆分，逐位存储在数组arr中。

    • T = solve(i); 获取当前数字的位数。

    • arr[n+j] = I % 10; 用于将每个位的数字逆序插入到 arr 中，直到数字 i 拆解完。

    • n += T; 更新当前已填充的总长度。

  • 查找“2023”子序列：

    • 遍历 arr 数组，依次检查每个位置的数字。

    • a：累计每次遇到的数字 2 的数量。

    • b：累计每次遇到的数字 0 前面有多少个数字 2。

    • c：累计每次遇到的数字 3 前面符合 20 序列的次数。

    • d：记录完整的 2023 子序列的数量。

• printf("%lld", d);：输出符合条件的子序列总数。

难度分析

⭐️⭐️ 

总结

本代码通过逐位遍历和计数器的方式实现了"2023"子序列的统计。此算法无需存储完整的字符串，通过位置的动态更新提高了效率。