藍(lán)橋杯 2023年省賽真題
^{C/C++ 大學(xué)G組}

?試題 A: 工作時長
?試題 B: 與或異或
?試題 C: 翻轉(zhuǎn)
?試題 D: 階乘的和
?試題 E: 公因數(shù)匹配
?試題 F: 奇怪的數(shù)
?試題 G: 太陽
?試題 H: 子樹的大小
?試題 ?I: 高塔
?試題 J: 反異或 01 串

除去第 $\mathrm{F}$ 題，其他題目在其他組別都有出現(xiàn)過，這里就不重寫了。

奇怪的數(shù)

時間限制: $1.0\mathrm{s}$?內(nèi)存限制: $256.0\mathrm{MB}$?本題總分：$15$ 分

【問題描述】

??小藍(lán)最近在找一些奇怪的數(shù)，其奇數(shù)數(shù)位上是奇數(shù)，而偶數(shù)數(shù)位上是偶數(shù)。同時，這些數(shù)的任意 $5$ 個連續(xù)數(shù)位的和都不大于 $m$。
??例如當(dāng) $m=9$ 時，$10101$ 和 $12303$ 就是奇怪的數(shù)，而 $12345$ 和 $11111$ 則不是。
??小藍(lán)想知道一共有多少個長度為 $n$ 的上述的奇怪的數(shù)。你只需要輸出答案對 $998244353$ 取模的結(jié)果。

【輸入格式】

??輸入一行包含兩個整數(shù) $n,m$，用一個空格分隔。

【輸出格式】

??輸出一行包含一個整數(shù)表示答案。

【樣例輸入】

5 5

【樣例輸出】

6

【評測用例規(guī)模與約定】

??對于 $30\%$ 的評測用例，$n\le 12$；
??對于 $60\%$ 的評測用例，$n\le 5000$；
??對于所有評測用例，。

動態(tài)規(guī)劃

??因為是要校驗連續(xù)的 $5$ 個數(shù)位上的數(shù)字之和是否大于 $m$，自然能設(shè)計出狀態(tài) $f_{i,a,b,c,d}$，表示第 $i?3$ 個數(shù)位上的數(shù)字為 $a$；$i?2:b$；$i?1:c$；$i:d$ 的奇怪的數(shù)有多少個，容易找到狀態(tài)轉(zhuǎn)移方程：$$f_{i,a,b,c,d}=\sum f_{i?1,e,a,b,c},a+b+c+d+e\le m.$$??轉(zhuǎn)移復(fù)雜度為 $O(n{D}^5)$，其中 $D=5$ 即每個數(shù)位可能的取值的個數(shù)，這樣看來復(fù)雜度就超了，$1s$ 指定是跑不出來，于是考慮維護(hù) $f$ 在第二維的前綴和，具體地說我們記：$$g_{i,a,b,c,d}=\sum _{j=0}^a{f}_{i,j,b,c,d}.$$??則狀態(tài)轉(zhuǎn)移方程可改寫為：$$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}.$$??轉(zhuǎn)移復(fù)雜度為 $O(n{D}^4)$，$1s$ 有那么一點極限，標(biāo)程很有可能不是動規(guī)。還有就是在實現(xiàn)時為了使 $D=5$，轉(zhuǎn)移過程會有一定的微調(diào)，具體看代碼吧。

#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$ 系 $\mathrm{Ryzen}$ 剛好在 $1s$ 跑完，這放在評測機上不開 $\mathrm{O}$$2$ 就超時了。推了半天式子也沒什么結(jié)果，不過有一種實在的優(yōu)化方案是：
??記一個長度為 $4$ 奇偶交替數(shù) $n$ 為 $abcd$，它的數(shù)位之和為 $s=a+b+c+d$，我們記 $n$ 的逆 $n^{\prime }=(9?a)(9?b)(9?c)(9?d)$ ，則逆的數(shù)位之和為 $s^{\prime }=36?s$，顯然 $n$ 的全集的按數(shù)位之和劃分，它的大小以 $18$ 為中點對稱。如果輸入的 $m$ 在對稱點以左，我們按原問題求解，在對稱點及對稱點以右我們求其逆問題，即一個數(shù) $S$，為長度為 $n$ 且存在連續(xù) $5$ 個數(shù)位之和大于 $m$ 的數(shù)的個數(shù)，此時答案為 $5^n?S$，這樣下來狀態(tài)轉(zhuǎn)移的次數(shù)減少一半，可以在時間限制內(nèi)計算出答案。
??不過相應(yīng)的代碼量翻倍，沒這個必要，還是題太臭了。文章來源地址http://www.zghlxwxcb.cn/news/detail-473445.html

到了這里，關(guān)于第十四屆藍(lán)橋杯大賽軟件賽省賽（C/C++ 研究生組）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！