CF2157F 题解

modongtao · 2025-11-24 18:32:36 · 题解

考虑将不同的技能值 s 转移到同一个值进行统一处理。

运用二进制思想，在第 i 轮中，将所有非 2^i 倍数的技能值提升 2^{i-1} 层，总代价约为 \frac{1}{2} n \times \log_2 n + 1000 \log_2 n \approx 2.25 \times 10^6，代价过大。

尝试减少提升轮数。类似的，考虑对 B 进制完成上诉过程。

在第一轮操作，顺序枚举整数 1 \le k < B，逆序枚举技能值 k, B+k, 2B+k, 3B+k, \dots，依次执行一次 l=1 的任务。

完成第一轮操作后，所有非 B 倍数的技能值都被转移到了某个 B 的倍数上。类比二进制的情况，对于技能 pB^q + kB，进行一次 l = B^{q-1} 的任务。重复操作，可以把所有数都转移到某个满足 B^q \ge n 的 B^q 上。

上述过程总代价约为 \frac{B-1}{B} n \times \log_B n + 1000(B-1) \log_B n。若取 B = 64，总代价约为 7.7 \times 10^5，足以通过。

:::info[Code]

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define rrep(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
using pii = pair<int, int>;
constexpr int B = 64;
int n;
vector<pair<int, int>> e;
void step(int x) {
    rep(p, 1, B - 1) {
        if (p * x > n) break;
        int k = p * x;
        while (k + x * B <= n) {
            k += x * B;
        }
        for (int i = k; i >= 1; i -= x * B) {
            e.push_back({i, x});
        }
    }
}
int main() {
    cin >> n;
    step(1), step(B), step(B * B);
    // 三轮操作足以将所有数移到 B*B*B，取 B = 64 时大于 250000.
    cout << e.size() << endl;
    for (auto p : e) {
        cout << p.first << " " << p.second << endl;
    }
}

:::