第十四届蓝桥杯大赛软件赛省赛（C/C++ 研究生组）-Toy模板网

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯大赛软件赛省赛（C/C++ 研究生组）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

蓝桥杯 2023年省赛真题
^{C/C++ 大学G组}

试题 A: 工作时长
试题 B: 与或异或
试题 C: 翻转
试题 D: 阶乘的和
试题 E: 公因数匹配
试题 F: 奇怪的数
试题 G: 太阳
试题 H: 子树的大小
试题 I: 高塔
试题 J: 反异或 01 串

除去第 $\rm F$ 题，其他题目在其他组别都有出现过，这里就不重写了。

奇怪的数

时间限制: $1.0\mathrm s$ 内存限制: $256.0\mathrm{MB}$ 本题总分： $15$ 分

【问题描述】

小蓝最近在找一些奇怪的数，其奇数数位上是奇数，而偶数数位上是偶数。同时，这些数的任意 $5$ 个连续数位的和都不大于 $m$ 。
例如当 $m = 9$ 时， $10101$ 和 $12303$ 就是奇怪的数，而 $12345$ 和 $11111$ 则不是。
小蓝想知道一共有多少个长度为 $n$ 的上述的奇怪的数。你只需要输出答案对 $998244353$ 取模的结果。

【输入格式】

输入一行包含两个整数 $n, m$ ，用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

5 5

【样例输出】

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $n \leq 12$ ；
对于 $60\%$ 的评测用例， $n \leq 5000$ ；
对于所有评测用例， $5 ≤ n ≤ 2 × 10^5，0 ≤ m ≤ 50$ 。

动态规划

因为是要校验连续的 $5$ 个数位上的数字之和是否大于 $m$ ，自然能设计出状态 $f_{i,a,b,c,d}$ ，表示第 $i - 3$ 个数位上的数字为 $a$ ； $i - 2 : b$ ； $i - 1 : c$ ； $i : d$ 的奇怪的数有多少个，容易找到状态转移方程： $f_{i,a,b,c,d}=\sum f_{i-1,e,a,b,c},a+b+c+d+e\leq m.$ 转移复杂度为 $O(nD^5)$ ，其中 $D = 5$ 即每个数位可能的取值的个数，这样看来复杂度就超了， $\rm 1s$ 指定是跑不出来，于是考虑维护 $f$ 在第二维的前缀和，具体地说我们记： $g_{i,a,b,c,d}=\sum_{j=0}^af_{i,j,b,c,d}.$ 则状态转移方程可改写为： $g_{i,a,b,c,d}=g_{i,a-1,b,c,d}+g_{i-1,\max(0,\min(9,m-a-b-c-d)),a,b,c}.$ 转移复杂度为 $O(nD^4)$ ， $\rm 1s$ 有那么一点极限，标程很有可能不是动规。还有就是在实现时为了使 $D = 5$ ，转移过程会有一定的微调，具体看代码吧。

#include <stdio.h>

const int M = 12, mod = 998244353;

int n, m, ans, g[2][M][M][M][M];

int main() {
    scanf("%d %d", &n, &m);
    int p = 1, q = 0;
    for (int a = p; a < 10; a += 2)
        for (int b = q; b < 10; b += 2)
            for (int c = p; c < 10; c += 2)
                for (int d = q; d < 10; d += 2) {
                    g[0][a + 2][b][c][d] = g[0][a][b][c][d] + (a + b + c + d <= m);
                }
    for (int i = 5; i <= n; ++i) {
        p ^= 1, q ^= 1;
        for (int a = p; a < 10; a += 2)
            for (int b = q; b < 10; b += 2)
                for (int c = p; c < 10; c += 2)
                    for (int d = q; d < 10; d += 2) {
                        int f = m - a - b - c - d;
                        if (q != (f & 1)) --f;
                        if (f > 8 + p) f = 8 + q;
                        g[i & 1][a + 2][b][c][d] = (g[i & 1][a][b][c][d] + (f < q ? 0 : g[~i & 1][f + 2][a][b][c])) % mod;
                    }
    }
    for (int b = q; b < 10; b += 2)
        for (int c = p; c < 10; c += 2)
            for (int d = q; d < 10; d += 2) {
                int f = m - b - c - d;
                if (f < p) continue;
                if (p != (f & 1)) --f;
                if (f > 8 + p) f = 8 + p;
                ans = (ans + g[n & 1][f + 2][b][c][d]) % mod;
            }
    printf("%d", ans);
}

输入200000 50， $4000$ 系 $\rm Ryzen$ 刚好在 $\rm 1s$ 跑完，这放在评测机上不开 $\rm\small O$ $2$ 就超时了。推了半天式子也没什么结果，不过有一种实在的优化方案是：
记一个长度为 $4$ 奇偶交替数 $n$ 为 $ab c d$ ，它的数位之和为 $s = a + b + c + d$ ，我们记 $n$ 的逆 $n^{'} = (9 - a) (9 - b) (9 - c) (9 - d)$ ，则逆的数位之和为 $s^{'} = 36 - s$ ，显然 $n$ 的全集的按数位之和划分，它的大小以 $18$ 为中点对称。如果输入的 $m$ 在对称点以左，我们按原问题求解，在对称点及对称点以右我们求其逆问题，即一个数 $S$ ，为长度为 $n$ 且存在连续 $5$ 个数位之和大于 $m$ 的数的个数，此时答案为 $5^n-S$ ，这样下来状态转移的次数减少一半，可以在时间限制内计算出答案。
不过相应的代码量翻倍，没这个必要，还是题太臭了。文章来源地址https://www.toymoban.com/news/detail-473445.html