1996(962div3)

A. Legs

农夫约翰来到农场后，数了数 $n$ 条腿。众所周知，农场里只住着鸡和牛，一只鸡有 $2$ 条腿，而一头牛有 $4$ 条腿。

假设约翰农场主数清了所有动物的腿，那么他的农场里最少有多少动物？

void solve() {
    int n;cin >> n;
    cout << (n + 3) / 4 << '\n';
}

B. Scale

分割网格

void solve() {
    int n, k;cin >> n >> k;
    vector<string> a(n + 1);
    for (int i = 1;i <= n;i++) {
        string s;cin >> s;s = " " + s;a[i] = s;
    }
    for (int i = 1;i <= n;i += k) {
        for (int j = 1;j <= n;j += k) {
            cout << a[i][j];
        }
        cout << '\n';
    }
}

C. Sort

给你两个长度为 $n$ 的字符串 $a$ 和 $b$ 。然后，您（被迫）回答 $q$ 个问题。

对于每个查询，你都会得到一个以 $l$ 和 $r$ 为边界的范围。在一次操作中，您可以选择一个整数 $i$ ( $l \leq i \leq r$ ) 并设置 $a_{i} = x$ 其中 $x$ 是您想要的任何字符。在 $sorted(a[l..r]) = sorted(b[l..r])$ 的情况下，输出必须执行的最少操作数。**对一个查询执行的操作不会影响其他查询。

对于任意字符串 $c$ ， $sorted(c[l..r])$ 表示由按词典顺序排列的字符 $c_{l}, c_{l + 1}, . . ., c_{r}$ 组成的子串。

这个题也是锻炼了一下像本题类型的前缀和。

void solve() {
    int n, q;cin >> n >> q;
    string a, b;cin >> a >> b;a = ' ' + a;b = ' ' + b;
    vector<array<int, 26>> prea(n + 1), preb(n + 1);
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j < 26;j++) {
            prea[i][j] = prea[i - 1][j];
            preb[i][j] = preb[i - 1][j];
        }
        prea[i][a[i] - 'a']++;
        preb[i][b[i] - 'a']++;
    }

    while (q--) {
        int l, r;cin >> l >> r;
        int ans = 0;
        vector<int> ala(26), alb(26);
        for (int i = 0;i < 26;i++)ala[i] = prea[r][i] - prea[l - 1][i];
        for (int i = 0;i < 26;i++)alb[i] = preb[r][i] - preb[l - 1][i];
        for (int i = 0;i < 26;i++) {
            ans += abs(ala[i] - alb[i]);
        }
        cout << ans / 2 << '\n';
    }
}

D. Fun

给定两个整数 $n$ 和 $x$ ，求满足 $a b + a c + b c \leq n$ 和 $a + b + c \leq x$ 的三联数（ $a, b, c$ ）的个数。

$(a, b, c) \neq (b, a, c)$ 即有顺序要求且 $a, b, c > 0$

Solution

这个题很简单，是自己想复杂了，总觉得复杂度不对 hh。

知道了 $a, b$ 后，计算出满足条件的最大的 $c$ ，所以种类数加上 $c$ 即可.

for i  i <= n i++
	for j  i * j <= n j++

运算次数为： $n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$ 次

proof for

n \log n

：

原式可化为： $n (1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n})$

其中 $A = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ 是一个调和级数。

$A = \ln (n + 1) + γ, γ \approx 0.5772156649$ ，即 $A \in O (\log n)$

则原式 $\in O (n \log n)$

void solve() {
    int n, x;cin >> n >> x;
    int sum = 0;
    for (int a = 1;a <= min(x - 2, n);a++) {
        for (int b = 1;a * b < n && a + b < x;b++) {
            sum += min((n - a * b) / (a + b), x - a - b);
        }
    }
    cout << sum << "\n";
}

E. Decode

为了获得你的 "女神 "最喜欢的角色，你不顾一切地侵入了游戏的源代码。经过数天的努力，你终于找到了编码游戏中 gacha 系统的二进制字符串。为了解码它，您必须首先解决以下问题。

给你一个长度为 $n$ 的二进制字符串 $s$ 。对于每一对整数 $(l, r)$ $(1 \leq l \leq r \leq n)$ ，请计算有多少对 $(x, y)$ $(l \leq x \leq y \leq r)$ 这样的整数。 $(l \leq x \leq y \leq r)$ 中 $0$ 的数量等于子串 $s_{x} s_{x + 1} . . . s_{y}$ 中 $1$ 的数量。

输出所有可能的 $(l, r)$ modulo $10^{9} + 7$ 的计数之和。

Solution

遇到这种要让之相等的题目，和牛客周赛52-F 有点像。

若 $s_{i} = 0$ ，则令 $p r e_{i} = - 1$ ,否则为 1，这样对于某个区间 $[l, r]$ ，直接判断 $p r e_{r} - p r e_{l - 1}$ 是否为 0 即 $p r e_{r} = p r e_{l - 1}$

即本问题变为：对于所有区间 $[l, r]$ ，数出使得满足 $p r e_{y} = p r e_{x - 1}$ 的 $(x, y)$ 的对数之和.

若对于某个区间 $[l, r]$ 有 0 的个数等于 1 的个数即 $p r e_{r} = p r e_{l - 1}$ 则这时有 $l \times (n - r + 1)$ 种。

即左边 $[1, l]$ 区间都可以选择，右边 $[r, n]$ 区间都可以选择

即：

for (int l = 1;l <= n;l++) {
	for (int r = l;r <= n;r++) {
		if (pre[r] == pre[l - 1]) {
			ans += l * (n - r + 1);ans %= mod;
		}
	}
}

运用 DP 的思想，通过枚举 $r$ ，每次将 $l$ 叠加起来计算。

$f_{i}$ 代表 $i$ 作为 $r$ ，在 $[0, i - 1]$ 的下标中满足和 $p r e_{i}$ 相等的下标之和，即 $f_{i} = \sum_{j = 0}^{i - 1} (j + 1) \times [p r e_{i} = p r e_{j}]$

#define int long long
constexpr int mod = 1e9 + 7;
void solve() {
    string s;cin >> s;int n = s.size();
    vector<int> pre(n + 1);
    for (int i = 0;i < n;i++) {
        pre[i + 1] = pre[i] + (s[i] == '0' ? -1 : 1);
    }
    vector<int> f(2 * n + 1);
    int ans = 0;
    for (int i = 0;i <= n;i++) {
        int t = pre[i] + n;
        ans += f[t] * (n - i + 1);ans %= mod;
        f[t] += i + 1;f[t] %= mod;
    }
    cout << ans << '\n';
}

F. Bomb

Sparkle 给你两个长度为 $n$ 的数组 $a$ 和 $b$ 。最初，您的分数是 $0$ 。在一次操作中，您可以选择一个整数 $i$ 并将 $a_{i}$ 添加到您的分数中。然后，您必须设置 $a_{i}$ = $max (0, a_{i} - b_{i})$ 。

在火花引爆核弹之前，您只有时间进行 $k$ 操作！在 $k$ 次操作之后，您能获得的最高分数是多少？

Solution

1995(961div2) 之后补