题解：CF2276E Good Substrings

zgfjyy2015 · 2026-11-09 19:11:04 · 题解

思路

关键点：正难则反，考虑求不合法的数量

预处理

这里很容易想到 dp 预处理，接下来讲一下大概思路。

定义

定义 dp_{i, j, k} 表示字符串前 i 个匹配到 2025 和 2026 的前 i 个和前 j 个的数量，当然还有一个 f_{i, j, k} 表示字符串后 i 个匹配到 2025 和 2026 的前 i 个和前 j 个的数量。

转移

转移比较难解释，详见以下代码：

for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 5; ++j) 
            for (int k = 0; k < 5; ++k) 
                dp[i][j + (j < 4 && s[i] == dx[j])][k + (k < 4 && s[i] == dy[k])] += dp[i - 1][j][k];

        dp[i][0][0]++;
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 0; j < 5; ++j) 
            for (int k = 0; k < 5; ++k) 
                f[i][j + (j < 4 && s[i] == dx[3 - j])][k + (k < 4 && s[i] == dy[3 - k])] += f[i + 1][j][k];

        f[i][0][0]++;
    }

初始化

由于本题有多组测试数据，可要记得清空呀：

for (int i = 0; i <= n + 1; ++i)
        for (int j = 0; j < 5; ++j)
            for (int k = 0; k < 5; ++k)
                dp[i][j][k] = f[i][j][k] = 0;

    dp[0][0][0] = f[n + 1][0][0] = 1;

答案计算

对于每个点枚举两对 j 和 k 用乘法原理计算答案即可。

完整代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 3e5 + 5;
const char dx[] = {'2', '0', '2', '5'}, dy[] = {'2', '0', '2', '6'};

int n, dp[N][5][5], f[N][5][5];
string s;

inline void solve() {
    cin >> n >> s; 
    s = ' ' + s;

    for (int i = 0; i <= n + 1; ++i)
        for (int j = 0; j < 5; ++j)
            for (int k = 0; k < 5; ++k)
                dp[i][j][k] = f[i][j][k] = 0;

    dp[0][0][0] = f[n + 1][0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 5; ++j) 
            for (int k = 0; k < 5; ++k) 
                dp[i][j + (j < 4 && s[i] == dx[j])][k + (k < 4 && s[i] == dy[k])] += dp[i - 1][j][k];

        dp[i][0][0]++;
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 0; j < 5; ++j) 
            for (int k = 0; k < 5; ++k) 
                f[i][j + (j < 4 && s[i] == dx[3 - j])][k + (k < 4 && s[i] == dy[3 - k])] += f[i + 1][j][k];

        f[i][0][0]++;
    }

    for (int i = 1; i <= n; ++i) {
        int ans = i * (n - i + 1);

        for (int j = 0; j < 5; ++j) {
            for (int k = 0; k < 5; ++k) {
                if (!dp[i - 1][j][k]) continue;

                for (int jj = 4 - (j + (s[i] == dx[j])); jj <= 4; ++jj)
                    for (int kk = 0; (k + (s[i] == dy[k])) + kk < 4; ++kk)
                        ans -= dp[i - 1][j][k] * f[i + 1][jj][kk];
            }
        }

        cout << ans << ' ';
    }

    cout << '\n';
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t; while (t--) solve();

    return 0;
}

大佬有意见的请在评论区提出，喜欢的话也请点个赞喵~