题目链接

A题

答案为$n-1$。

B题

p变为q，q变为p，再反转即可。

C题

贪心安排a，b只猴子能坐的数量，剩余位置分配给c。

1
2
3
4
5
6
void solve() {
    int a, b, c, m;
    cin >> m >> a >> b >> c;
    cout << std::min(a, m) + std::min(b, m) + 
    std::min(2 * m - std::min(a, m) - std::min(b, m), c) << '\n';
}

D题

由于数列$a$中所有数字均在$n$之内，且需要填的数列$b$也必须在$n$之内，那就让$b$中每个数字出现的模只出现一次，空缺用$a$中未出现的数字替代，可知一定不会有冲突的情况，一定可以按要求填满。

1
2
3
4
5
6
void solve() {
    int a, b, c, m;
    cin >> m >> a >> b >> c;
    cout << std::min(a, m) + std::min(b, m) + 
    std::min(2 * m - std::min(a, m) - std::min(b, m), c) << '\n';
}

E题

转化为$y=x\cdot k^n$，考虑枚举$k^n$，然后对边界情况取交集即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    u64 k, l1, r1, l2, r2, ans = 0;
    cin >> k >> l1 >> r1 >> l2 >> r2;
    u64 tk = 1;
    while (l1 * tk <= r2) {
        int l = std::max(l1, (l2 + tk - 1) / tk);
        int r = std::min(r1, r2 / tk);
        if (r >= l) {
            ans += r - l + 1;
        }
        tk *= k;
    }
    cout << ans << '\n';
}

F题

方格所有数之和为$\sum_{i=1}^n\sum_{j=1}^ma_ib_j=\sum_{i=1}^na_i\cdot \sum_{j=1}^mb_j$，从中去除一行或者一列就是从$a$数列中去除一个数，$b$数列中去除一个数，再分别求和相乘。

由于两个数组中的元素绝对值均在$n$，$m$之内，直接使用数组模拟哈希表，每次询问的$x$在$2e5$以内，直接枚举$x$的因子，然后分别在两个数组中寻找即可。复杂度$O(n+m+q\sqrt{q})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    std::vector<bool> hasha(2 * n + 1), hashb(2 * m + 1);
    i64 suma = 0, sumb = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        suma += a;
        hasha[a + n] = true;
    }
    for (int j = 0; j < m; j++) {
        int b;
        cin >> b;
        sumb += b;
        hashb[b + m] = true;
    }
    auto check = [&](i64 x, i64 y) -> bool {
        if (x > n || x < -n || y > m || y < -m) return false;
        return hasha[x + n] && hashb[y + m];
    };
    while (q--) {
        int que;
        cin >> que;
        bool flag = false;
        for (int i = 1; 1ll * i * i <= std::abs(que); i++) {
            if (que % i == 0) {
                if (check(suma - i, sumb - que / i) || check(suma + i, sumb + que / i) || check(suma - que / i, sumb - i) || check(suma + que / i, sumb + i)) {
                    flag = true;
                    cout << "YES\n";
                    break;
                }
            }
        }
        if (!flag) {
            cout << "NO\n";
        }
    }
}

G1题

由于每只蜘蛛手里最多只能有一个玩具，因此一遍拓扑序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n + 1), in(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        in[a[i]]++;
    }
    int ans = 2;
    std::queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        ans++;
        int size = q.size();
        while (size--) {
            int u = q.front();
            q.pop();
            if (--in[a[u]] == 0) {
                q.push(a[u]);
            }
        }
    }
    cout << ans << '\n';
}

G2题

这次每只蜘蛛手里可以有多个玩具，由于每个点出度均为1，因此用一个变量$t$来表示还没变为0的点，到目前为止应该已经递出去了$t$件礼物，用$dp[i]$表示当前节点$i$总共收到了多少件玩具，当目前$dp[i]=t$时，弹出该节点，这时将整个$dp[i]$递给下一个节点，令下一个节点的入度减一，入度为0时，入队。

由于每次需要弹出当前层的所有节点，但有的节点弹出时$dp[i]>t$，那么这个节点需要重新入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void solve() {
    int n;
    cin >> n;
    std::vector<int> dp(n + 1, 1), in(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
        in[r[i]]++;
    }
    std::queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            q.push(i);
        }
    }
    int ans = 2, t = 1;
    while (!q.empty()) {
        ans++;
        int size = q.size();
        while (size--) {
            int u = q.front();
            q.pop();
            if (dp[u] > t) {
                q.push(u);
            }
            int v = r[u];
            if (dp[u] == t) {
                dp[v] += dp[u];
                if (--in[v] == 0) {
                    q.push(v);
                }
            }
        }
        t++;
    }
    cout << ans << '\n';
}

H题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void solve() {
    int n, q;
    n = read<int>();
    q = read<int>();
    std::vector<std::vector<i64>> sum(n + 1, std::vector<i64>(n + 1));
    std::vector<std::vector<i64>> sumr(n + 1, std::vector<i64>(n + 1));
    std::vector<std::vector<i64>> sumc(n + 1, std::vector<i64>(n + 1));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int a;
            a = read<int>();
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a;
            sumr[i][j] = sumr[i - 1][j] + sumr[i][j - 1] - sumr[i - 1][j - 1] + a * j;
            sumc[i][j] = sumc[i - 1][j] + sumc[i][j - 1] - sumc[i - 1][j - 1] + a * i;
        }
    }

    auto get_sum = [&](std::vector<std::vector<i64>> &a, int x1, int y1, int x2, int y2) -> i64 {
        return a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1];
    };
    for (int i = 0; i < q; i++) {
        int x1, y1, x2, y2;
        x1 = read<int>();
        y1 = read<int>();
        x2 = read<int>();
        y2 = read<int>();
        
        i64 sr = get_sum(sumr, x1, y1, x2, y2);
        i64 sc = get_sum(sumc, x1, y1, x2, y2);
        i64 s = get_sum(sum, x1, y1, x2, y2);
        
        cout << sr + sc * (y2 - y1 + 1) - s * (x1 * (y2 - y1 + 1) + y1 - 1) << ' ';
    }
    cout << '\n';
}