Educational Codeforces Round 8

A

模拟即可

int n, b, p;
    std::cin >> n >> b >> p;
    const int N = n;

    ll ans = 0;
    while (n > 1) {
        int k = bit_floor(n);
        ans += k / 2 * (b * 2 + 1);
        n -= k / 2;
    }

    std::cout << ans << " " << N * p << "\n";

B

一个数字字符串中有多少能被$4$整除的字串，由于$100$是$4$的倍数，只要考虑低两位是不是$4$的倍数，和一位是$4$的倍数的情况

    std::string s;
    std::cin >> s;

    const int N = s.size();
    std::vector<int> a;
    for (auto c : s) {
        a.push_back(c - '0');
    }

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += a[i] % 4 == 0;
        if (i > 0 && (a[i] + a[i - 1] * 10) % 4 == 0) {
            ans += i;
        }
    }

    std::cout << ans << "\n";

C

能否构造一个小写字符串，使得到另外一个给定小写字符串的距离为给定值，距离的定义是相同长度的两个小写字符串的对应位置的字符ascii码差的绝对值之和。

考虑贪心，每次取最大差，因为满足条件后所有剩下的位都可以取$0$

    int n, k;
    std::string s;
    std::cin >> n >> k >> s;

    std::string ans;
    for (auto c : s) {
        int a = std::abs('a' - c), z = std::abs('z' - c);
        int d = std::min(k, std::max(a, z));
        k -= d;
        ans.push_back(islower(c + d) ? c + d : c - d);
    }

    std::cout << (k ? "-1" : ans) << "\n";

D

给定$[a,b]$，求其中有多少满足能被$m$整除且偶数位上为$d$，奇数位上不为$d$的数。

考虑数位dp，令$dp[i][j][k]$表示当前枚举到第$i$位，余数是$j$，限制为$k$的满足条件的数的个数（$k=0$表示无限制，$k=1$表示有限制）

转移如下:

假设下一位选$b$，奇数位只能选非$d%$且在范围内的数或没有方案，偶数位只能选$d$或没有方案

$$
dp[i+1][(j*10+b)%m][0]+=
\begin{cases}
dp[i][j][0] \text{ any case, ok}\
dp[i][j][1] \text{ if the top is not reached}
\end{cases}
$$

由于这里位数给的很长，而且$d=0,a=1$的时候会有问题，所以在最后特判一下$a$是否能选进去，复杂度$O(nm)$，$n$是数字长度

    int m, d;
    std::cin >> m >> d;

    std::string a, b;
    std::cin >> a >> b;

    std::for_each(a.begin(), a.end(), [](auto &c) { c -= '0'; });
    std::for_each(b.begin(), b.end(), [](auto &c) { c -= '0'; });

    Z ans = 0;
    auto work = [&](const std::string s) {
        const int N = s.size();
        std::vector dp(N + 1, std::vector(m, std::vector<Z>(2)));
        dp[0][0][1] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < 2; k++) {
                    const int end = k ? s[i] : 9;
                    for (int b = 0; b <= end; b++) {
                        if ((i % 2 == 0 && b == d) || (i % 2 && b != d)) {
                            continue;
                        }
                        dp[i + 1][(j * 10 + b) % m][k && s[i] == b] +=
                            dp[i][j][k];
                    }
                }
            }
        }
        return dp[N][0][0] + dp[N][0][1];
    };

    ans += work(b) - work(a);

    bool ok = true;
    int r = 0;
    for (int i = 0; i < a.size(); i++) {
        if (i & 1) {
            ok &= a[i] == d;
        } else {
            ok &= a[i] != d;
        }

        r = (r * 10 + a[i]) % m;
    }

    if (ok && r == 0) {
        ans++;
    }

    std::cout << ans << " ";

E

枚举拐点，之前不会学了一下，这次还是不会😕

预处理：

• ld：往左下角最多延伸多少个z
• l：往左最多延伸多少个z
• r：往右最多延伸多少个z

每个反对角线单独统计

右上角拐点要形成z-pattern的限制是ld和l

左下角拐点要形成z-pattern的限制是r

考虑每次把左下角的限制转化为时间维度，因为对于每个右上角拐点不会统计超过当前横坐标的值（可以理解为这也是一种限制），用树状数组来维护就好了

    int n, m;
    std::cin >> n >> m;

    std::vector<std::string> s(n);

    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
    }

    std::vector ld(n, std::vector<int>(m)), l(n, std::vector<int>(m)),
        r(n, std::vector<int>(m));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (i < n - 1 && j > 0 && s[i][j] == 'z') {
                ld[i][j] = ld[i + 1][j - 1] + 1;
            } else if (s[i][j] == 'z') {
                ld[i][j] = 1;
            }

            if (s[i][j] == 'z') {
                l[i][j] = 1;
                if (j > 0) {
                    l[i][j] += l[i][j - 1];
                }
            }
        }
        for (int j = m - 1; j >= 0; j--) {
            if (s[i][j] == 'z') {
                r[i][j] = 1;
                if (j < m - 1) {
                    r[i][j] += r[i][j + 1];
                }
            }
        }
    }

    std::vector<std::vector<PII>> add(m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (r[i][j] > 0) {
                add[std::min(j + r[i][j] - 1, m - 1)].emplace_back(i, j);
            }
        }
    }

    ll ans = 0;
    std::vector fen(n + m, Fenwick<int>(m));
    for (int j = m - 1; j >= 0; j--) {
        for (auto [x, y] : add[j]) {
            fen[x + y].add(y + 1, 1);
        }
        for (int i = 0; i < n; i++) {
            auto o = std::min(ld[i][j], l[i][j]);
            if (o > 0) {
                ans += fen[i + j].sum(j - o + 2, j + 1);
            }
        }
    }

    std::cout << ans << "\n";

剩下待补(还不会flow)