CF2157F 题解

考虑将不同的技能值

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

，足以通过。

Code

CPP

#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;
    }
}

文章操作

相关推荐

评论

CF2157F 题解