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 
#include 
using namespace std;
// 是个简单的动态规划就算了
// 怎么又是一道越界题目
// 以后统一不用long long改用 unsigned long long。更大。
int main(){
    vector dp(4,0);
    string str="";
    for(int i=1; i2) num1 += i-2; // 求取数量相同的数在减2；
    else if(i==1) num2++;
  }
  int sum = 0;
  // 当已被占用的id的数量，大于未被占用id时，那么sum = num1;
  if(num1>num2){
    sum = num1;  
  }else{ // num2>m;
    vector a(n,0);
    vector b(m,0);
    for(int i=0; i>a[i];
    for(int i=0; i>b[i];
    // sum_a a数列的前缀和
    // sum_b b数列的前缀和
    // cnt_a a的位数
    // cnt_b b的位数
    // cnt_sum 总共需要的次数
    long long sum_a=0,sum_b=0,cnt_a=0,cnt_b=0,cnt_sum=0;
    while(true){
        if(sum_a==sum_b){
            sum_a+=a[cnt_a++];
            sum_b+=b[cnt_b++];
        }else if(sum_a>p[i].y;
    vector vec(n); // 存
    // 预处理，只需要耗时O(n^2)，即可分堆，避免3层暴力的大量重复计算
    for(int i=0; i{0,1},{1,0},{0,-1},{-1,0}};
        boolean[][][] visited = new boolean[n][m][2 * k];
        for (int step = 0; !qu.isEmpty(); step++) {
            int num = qu.size();
            for (int i = 0; i l>>r,res[r+l]++; 
    for(int i=1; iL>>R;
        L*=2,R*=2;
        if(L==0) cout