2023第十四届蓝桥杯国赛 C/C++ 大学 B 组

文章目录

• 前言
• 试题 A: 子 2023
• • 作者思考
  • 题解
  • 答案
  • 试题 B: 双子数
  • • 作者思考
    • 题解
    • 试题 C: 班级活动
    • • 作者思考
      • 题解
      • 试题 D: 合并数列
      • • 作者思考
        • 题解
        • 试题 E: 数三角
        • • 作者思考
          • 题解
          • 试题 F: 删边问题
          • • 作者思考
            • 题解
            • 试题 G: AB 路线
            • • 作者思考
              • 题解
              • 试题 H: 抓娃娃
              • • 作者思考
                • 题解
                • 试题 I: 拼数字
                • 试题 J: 逃跑

                  前言

                  第一次接触写国赛的题，在下才疏学浅，题解如有错误请指正。

                  A ~ H有题解，其中E题作者打的暴力。

                  如果能帮助你的话，点点赞吧！谢谢

                  试题 A: 子 2023

                  本题总分：5 分

                  【问题描述】

                  小蓝在黑板上连续写下从 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]…

                  【答案提交】

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

                  作者思考

                  作完省赛的就知道，这不就是省赛E题的接龙数列嘛。简单的dp就可以。分别以2 0 2 3（要转化，因为有两个2）结尾dp就可以了。

                  虽然正解是dp，但是暴力 + 剪枝也可以做，就是跑的有些慢。作者本地跑差不多50s。

                  还一个坑，就是如果你不开long long就会得到错的答案：1189693313

                  题解

                  #includeusing namespace std;#define int long long // 开long long string s; int f1() { int cnt = 0; for (int a = 0; a  x, q2.push(x);while (!q1.empty()) {tp1 = q1.front();tp2 = q2.front();if (tp1 == tp2) q1.pop(), q2.pop();else if (tp1  p[i].x >> p[i].y;// 遍历所有点，并且要避免重复 for (int i = 1; i for (int j = 1; j  b && b + c > a)if ((a == b) || (a == c) || (b == c)) ans++;}}}cout dfn[u] = low[u] = ++dfn_cnt;for (int v : G[u]) {if (!dfn[v]) {tarjan(v, u);w[u] += w[v];low[u] = min(low[u], low[v]);if (low[v]  dfn[u]) ans = min(ans, llabs(sum_w - 2 * w[v]));} else if (dfn[v]  n >> m;for (int i = 1; i > w[i], sum_w += w[i];for (int i = 1, u, v; i cin > u >> v;G[u].push_back(v);G[v].push_back(u);}tarjan(1, 0);if (w[1] != sum_w) cout     ios::sync_with_stdio(0);    cin.tie(0), cout.tie(0);    int t = 1;    /*cin  t;*/    while (t--) slove();    return 0;}0, 0, 0, 1, -1};int dy[] = {0, 1, -1, 0, 0};struct node {    int x;    int y;    int step;};int n, m, k;char G[maxl][maxl];bool vis[maxl][maxl][N];int dis[maxl][maxl][N];queue    cin  n  m >> k;    for (int i = 1; i         for (int j = 1; j             cin  G[i][j];        }    }    vis[1][1][1] = 1;    q.push({1, 1, 1});    while (!q.empty()) {        node tp = q.front();        q.pop();        for (int i = 1; i             int x = tp.x + dx[i];            int y = tp.y + dy[i];            if (x  m) continue; // 地图边界判断            // [1, k]走了k步， 所以第k + 1步要进行变号(注意这里用的是tp.step)            if (G[x][y] == G[tp.x][tp.y] && tp.step == k) continue; // 走了k + 1步， 没有变号            if (G[x][y] != G[tp.x][tp.y] && tp.step != k) continue; // 没走k + 1步，变号了            int step = (tp.step) % k + 1;            if (vis[x][y][step]) continue; // 这个点走过了第step步            vis[x][y][step] = 1;            dis[x][y][step] = dis[tp.x][tp.y][tp.step] + 1;            q.push({x, y, step});        }    }    int ans = maxn;    for (int i = 1; i         if (vis[n][m][i]) {            ans = min(ans, dis[n][m][i]); // 到达终点的可能步数全都遍历一遍        }    }    if (ans == maxn) cout     ios::sync_with_stdio(0);    cin.tie(0), cout.tie(0);    int t = 1;    /*cin  t;*/    while(t--) slove();    return 0;}cin  n > m;for (int i = 1, l, r; i cin > l >> r;sum[l + r]++;}for (int i = 1; i  l >> r;l *= 2;r *= 2;cout