2019牛客暑期多校训练营（第四场） - K - number

https://ac.nowcoder.com/acm/contest/884/K

一开始整了好几个假算法，还好测了一下自己的样例过了。

考虑到300的倍数都是3的倍数+至少两个零（或者单独的0）。

求以第i个位置的数为结尾的前缀和为j的数的方案数。

当遇到至少两个0的时候，ans+=dp[0][i-2]+1。

+1是那两个0的贡献。

这样子算会漏算单独的0的贡献，最后加回去。

还因为忘记mod3段错误好几次。

老了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

char s[100005];

int dp[3][100005];

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    while(~scanf("%s", s)) {

        int n = strlen(s);

        for(int i = 0; i < n; ++i)

            s[i] -= '0';

        dp[0][0] = dp[1][0] = dp[2][0] = 0;

        ++dp[s[0] % 3][0];

        int lx0 = (s[0] == 0);

        ll ans = 0;

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

            int c = s[i];

            dp[c % 3][i] = dp[0][i - 1];

            dp[(c + 1) % 3][i] = dp[1][i - 1];

            dp[(c + 2) % 3][i] = dp[2][i - 1];

            ++dp[c % 3][i];

            lx0 = (c == 0) ? lx0 + 1 : 0;

            if(lx0 >= 2)

                ans += dp[0][i - 2] + 1;

        }

        for(int i = 0; i < n; ++i)

            ans += (s[i] == 0);

        printf("%lld\n", ans);

    }

}

巴特西

2019牛客暑期多校训练营（第四场） - K - number - dp

最新文章

热门文章