Codeforces Round #701 (Div. 2)

A - Add and Divide

如果有 ++b 操作, 那么一定是一开始直接先把 ++b 操作执行完

而我们知道 ++b 操作对于答案的函数 是个凸函数, 找最值就好了

int work(int a, int b) {
    int c = 0;
    while (a) ++c, a /= b;
    return c;
}
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m; k = m == 1 ? (++m, 1) : 0;
        while (work(n, m) > work(n, m + 1)) ++m, ++k;
        cout << k + work(n, m) << '\n';
    }
    return 0;
}

B - Replace and Keep Sorted

前缀和即可, 主要读题难受

int main() {
    IOS; cin >> n >> m >> k;
    rep (i, 1, n) cin >> a[i]; a[n + 1] = k + 1;
	rep (i, 1, n) s[i] = a[i + 1] - a[i - 1] - 1 + s[i - 1];
    rep (i, 1, m) {
        int l, r; cin >> l >> r;
		ll ans = s[r - 1] - s[l] + k - a[r - 1] + a[l + 1] - 1;
        cout << ans - r - 1 + l << '\n';
    }
    return 0;
}

C - Floor and Mod

设$a = k * b + b = k * (b + 1), k < b \ \ $ 先找到一个 b 使得 \(b * (b + 1) <= ans\)

我们就能得到第一部分的答案 \(a = \{1 * 2 + 1, 1 * 3 + 1, 2 * 3 + 2, 1 * 4 + 1 , ..., 1 * (b + 1) + 1, 2 * (b + 1) + 2, ..., b * (b + 1) + b\}\)

即有 \(ans = (b - 1) * b / 2\)

对于剩下的都是不能完全找到 \(b * (b + 1) <= n\) 的, 直接分块处理有多少个

int work(int n) {
    int c = sqrt(n); k = n;
    while (n / c < c + 1) --c;
    return c;
}
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> m >> n;
        if (m == 1) { cout << "0\n"; continue; }
        ll c = min(work(m), n);
        ll ans = (c - 1) * c >> 1;
        for (int l = c + 1, r; l <= n && l < m; l = r + 1) {
            r = min(m / (m / (l + 1)) - 1, n);
            ans += (m / (r + 1)) * (r - l + 1ll);
        }
        cout << ans << '\n';
    }
    return 0;
}

D

\(1, 2, 3, ..., 16\) 公倍数 \(720720\), 直接要么\(720720\), 要么\(720720 + a[i][j]^4\)

int main() {
    IOS; cin >> n >> m;
    rep (i, 1, 16) c[i] = i * i * i * i;
    for (int i = 1; i <= n; ++i, cout << '\n') rep (j, 1, m)
        cin >> k, cout << 720720 + (i + j & 1 ? 0 : c[k]) << ' ';
    return 0;
}