2023第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组(真题&题解)（C++/Java题解）

本来想刷省赛题呢，结果一不小心刷成国赛了
真是个小迷糊〒▽〒
但，又如何( •̀ ω •́ )✧
记录刷题的过程、感悟、题解。
希望能帮到，那些与我一同前行的，来自远方的朋友😉

注：感谢@Witton的提示，题目部分已完成修改( •̀ ω •́ )y

大纲：

一、子2023-（题解）-递推or动态规划

二、双子数-（题解）-筛法、类型(unsigned long long)😥

三、班级活动-（题解）-不出所料、贪心+计数

四、合并数列-（题解）-妥妥的前缀和😥，当然双指针也能做

五、数三角-（题解）-这个真的就是算术题了，还要用到各种优化（叉乘、用半径分组）

六、删边问题-（题解）-图(tarjan算法)割边、割点，经典板子题

七、AB路线-（题解）-BFS广搜，最短路径、记忆话搜索😉

八、抓娃娃-（题解）-简单点的差分+前缀和😊

九、十，等后续冲击国赛时，再解决。

一、子2023

问题描述

小蓝在黑板上连续写下从 1 到 2023之间所有的整数，得到了一个数字序列： S=12345678910111213…20222023。 小蓝想知道 S 中有多少种子序列恰好等于 2023？

以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：

1[2]34567891[0]111[2]1[3]14151617181920212223…
1[2]34567891[0]111[2]131415161718192021222[3]…
1[2]34567891[0]111213141516171819[2]021222[3]…

注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对：

1[2]345678910111[2]131415161718192[0]21222[3]…

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

动态规划解法：

本题解法，说成是状态规划，可能会引起恐惧，其实它就是一道简单的状态推导题( •̀ ω •́ )✧

C++

#include <iostream>
#include <vector>
using namespace std;
// 是个简单的动态规划就算了
// 怎么又是一道越界题目
// 以后统一不用long long改用 unsigned long long。更大。
int main(){
    vector<unsigned long long> dp(4,0);
    string str="";
    for(int i=1; i<=2023; ++i) str+=to_string(i);
    // 本题的解法是动态规划
    for(char c : str){
        if(c=='2'){
            dp[0]++;
            dp[2]+=dp[1];
        }
        if(c=='0') dp[1]+=dp[0];
        if(c=='3') dp[3]+=dp[2];
    }
    cout<<dp[3]<<endl;
    return 0;
}