ACM训练 5月补题题解

CF2094 Div.4 F

题意

给定 \(n,m,k\) 满足 \(k \mid nm\)，构造一个 \(n\times m\) 的矩阵满足其中每个数都在 \([1,k]\)，且出现次数都相同，并且相同的两个数不能位置相邻。

题解

万恶的构造题。

既然 \(k\mid nm\)，那么可以使得 \([1,k]\) 所有数都满足出现 \(\frac{nm}{k}\) 次，我们可以围绕这一点去构造。

我们直接从左到右，从上到下放置 \(1,2,3,...,k\) ，那么只有 \(k \mid m\) 时会违反相邻的要求，此时我们把偶数行循环右移一下，顺序为 \(k,1,2,3,...\)。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    int x = 1;
    for (int i = 1; i <= n; i++) {
        int j = 1;
        while (j <= m) {
            std::cout << (i % 2 == 0 && m % k == 0 ? (x == 1 ? k : x - 1) : x)
                      << " \n"[j == m];
            x++;
            if (x > k) {
                x -= k;
            }
            j++;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

CF2094 Div.4 G

题意

对一个空数组进行如下操作：

1. 循环右移一次
2. 反转数组
3. 向数组末尾添加一个数

每次操作后输出 \(\sum_{i=1}^n ia_i\)。

题解

观察答案的形式，我们可以尽量去发现每种操作后答案如何变化：我们维护答案 \(ans\)、每个数的和 \(sum\)、数组大小 \(sz\)。进行第三种操作就是对答案额外增加 \(sz\times a_{sz}\)，而对于循环右移，等价于每个数都额外加一次，但是最后一个数被移到最前面了，需要减去 \(n\times a_{n}\)，对于反转操作，我们还要考虑对答案的影响。我们还需要知道此时数组的第一个数和最后一个数用于反转。

我们使用一个标记来判断是否反转，不反转时进行操作 1，数组开头的数变成数组末尾的数，反转时数组末尾的数变成数组开头的数，而对于操作 2，答案变化为 \(ans = (sz + 1)\times sum - ans\)。操作三知道反转情况添加即可。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
std::vector<i64> a(1e6);

void solve() {
    int q;
    std::cin >> q;
    int l = 2e5, r = 4e5;
    bool rev = false;
    i64 ans = 0, sum = 0;
    int sz = 0;
    while (q--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            if (!rev) {
                ans += sum - 1ll * sz * a[r];
                a[--l] = a[r--];
            } else {
                ans += sum - 1ll * sz * a[l];
                a[++r] = a[l++];
            }
        } else if (op == 2) {
            ans = sum * (sz + 1) - ans;
            rev ^= 1;
        } else {
            int x;
            std::cin >> x;
            sz++;
            ans += 1ll * sz * x;
            sum += x;
            if (!rev) {
                a[++r] = x;
            } else {
                a[--l] = x;
            }
        }
        std::cout << ans << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}	

CF2094 Div.4 H

题意

\(q\) 次询问，每次进行如下伪代码：

function f(k, a, l, r):
   ans := 0
   for i from l to r (inclusive):
      while k is divisible by a[i]:
         k := k/a[i]
      ans := ans + k
   return ans

题解

对于每个 \(k\)，如果能进行操作最少是除以 2，那么每个 \(k\) 进行除法的次数不会超过 \(\log k\)，考虑离线回答。

我们可以固定左端点，处理以该位置为左区间的所有询问：我们找到下一个当前询问的 \(k\) 的因数出现的位置，那么这段区间能贡献的答案就是长度乘以 \(k\) 被当前位置的数整除后的结果。因此，我们还可以预处理每个数的因数，以及数组中每个数下一次出现的位置，这样的复杂度是 \(O(n\log n)\) 的。每次端点处理完后，就向下一个出现的位置添加一个新的 \(k\prime\) 继续处理即可。对于当前数的所有因数，我们需要找到它后边最近的因数出现的位置。

时间复杂度：\(O(n\log n+q\sqrt{n})\)