讨论/题目交流/🏆 第 182 场力扣周赛/
🏆 第 182 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 找出数组中的幸运数
4 分 - 统计作战单位数
5 分 - 设计地铁系统
8 分 - 找到所有好字符串

T4 数位dp

代码写的有点乱……

class Solution {
    int n = 0, m = 0;
    string evil;
    using ll = long long;
    const ll mod = 1e9 + 7;
public:
    ll dp[505][30][56];

    void kmp_init(int n, vector<int>&pi, const string&a)
    {
        pi = vector<int>(a.size(), 0);
        for (int i = 1; i < n; ++i)
        {
            int j = pi[i - 1];
            while (j > 0 && a[i] != a[j])
            {
                j = pi[j - 1];
            }
            if (a[i] == a[j]) j++;
            pi[i] = j;
        }
    }
    vector<int> p;
    ll dfs(int cur, int st, int front, bool op, const string&s)
    {
        if (front == m)return 0;
        if (cur >= n) return 1;
        if (!op && ~dp[cur][st][front]) return dp[cur][st][front];
        int mx = op ? s[cur] - 'a' : 25;
        ll res = 0;
        for (int i = 0; i <= mx; ++i)
        {
            if (i == evil[front] - 'a')
            {
                res += dfs(cur + 1, i, front + 1, op&& i == mx, s);
            }
            else
            {
                int tf = 0;
                if (front > 0)
                {
                    int j = p[front - 1];
                    while (j > 0 && evil[j] - 'a' != i)
                    {
                        j = p[j - 1];
                    }
                    if (evil[j] - 'a' == i) j++;
                    tf = j;
                }
                else
                {
                    tf = i == evil[0] - 'a';
                }
                res += dfs(cur + 1, i, tf, op&& i == mx, s);
            }
            res %= mod;
        }
        res %= mod;
        if (!op) dp[cur][st][front] = res;
        return res;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        if (s1 > s2) return 0;
        this->evil = evil;
        this->n = n;
        m = evil.size();
        kmp_init(m, p, evil);
        memset(dp, -1, sizeof(dp));
        ll res = dfs(0, 26, 0, 1, s1);
        memset(dp, -1, sizeof(dp));
        res = dfs(0, 26, 0, 1, s2) - res;
        int flag = 1;
        for (int i = 0; i + m <= n; ++i)
        {
            if (s1[i] == evil[0] && s1.substr(i, m) == evil)
            {
                flag = 0; break;
            }
        }
        return (res + mod + flag) % mod;
    }
};
1
展开全部 31 讨论