题意#

你有$1'000'000$块钱, 当前等级为$[1, 250'000]$内的任意整数.

需要构造一个$(y, l)$的任务序列. 对于每个任务的花费是: 若本任务的y比前一个任务的y大, 则为$l + 1000$, 否则为$l$. 每个任务的收益是: 若当前技能等级等于$y$, 则技能等级提升$l$. 要求总花费不超过初始财产的限制下, 这个操作序列能将任意的初始等级提升到至少$n$.

分析#

总花费是多少? 实际上就是任务序列所有的$l$总和, 再加上$y$提升的次数乘以$1'000$.

这是个构造题, 先猜一猜一些可能的解. 比如我们构造$1, 2, 3..., n - 1$这个难度序列, $l$总和为$249'999$, 然而$y$提升了非常多次($249'998$), 每次都要花$1'000$, 这显然是非常不划算的.

如果我们这样构造呢? $n - 1, n - 2, n - 3, ..., 1$. 这样显然上升的次数是0, 但是由于没有地方中转, 每个任务我们都得将y提升到$n$. $l$的总和将会是$n^2$级别的, 不可接受.

所以说, 我们要让总花费最小, 重点在于平衡上升的次数与$l$的总和.

如果说我们这样构造呢? $n - 1, n - 3, n - 5...$, 每次上升1, 相当于把所有技能等级收集到了偶数上.再进行$n - 2, n - 4, n - 6...$我们会发现, 虽然上升的次数多了一次, 然而由于我们提供了偶数作为中转, $l$的总和下降了非常多(虽然离我们的目标还很远). 进一步, 如果我们再把偶数收集到4倍数上, 4倍数收集到8倍数上…这样虽然上升的次数会增加, 但是总和会下降, 我们能不能找到一个比较好的极值呢? 很不幸并不能, 因为题目的限制非常严格. 然而我们很快会发现, 以上我们默认了”2”为基数, 而事实上”2”并非最好的基数.

解法#

我们假设基数为$m$. 这时候我们需要收集$\log_m n$趟. 对于每趟来说: 先把所有模$m$为1的数收集到模$m$为2的数上, 再把模$m$为2的数收集到模$m$为3的数上…最后收集到模$m$为0的数上, 这趟就算是跑完了. 我们会发现每一趟来说, 每个任务的$l$都是1, 且几乎每个技能等级都会涉及一次(除了那些模m为0的技能等级). 所以, 每一趟中$l$的总和我们可以看作$n$. 每一趟上升多少次呢? 实际上就是收集的次数, 至多为$m$.

所以我们可以列出总花费:

注意到$log_m n$不会有太多值, 我们可以手算枚举$\log_m n$的值为$1, 2, 3...$时的情形, 得到$log_m n = 3$的时候总花费可以低于$1'000'000$(当然你想求导也是可以的). 此时$m = n^{1 / 3} \approx 63$. 于是我们就解决了这个问题.

AC代码#

提交记录

1
void solution() {
2
    /* code here */
3
    int n;
4
    cin >> n;
5
    if (n == 4) {
6
cout << R"(4
7
1 4
8
3 1
9
2 1
10
3 1
11
)";
12
        return;
13
    }
14

15
    ll m = 63;
16
    ll base = 1;
17
    vector<int> vis(n + 1);
18
    vector<pair<int, int>> ans;
19
    ans.reserve(250000);
20
    for (int i = 0; i < 3; i++) {
21
        for (int j = 1; j < m; j++) {
22
            for (int k = n; k >= 1; k--) {
23
                if (vis[k]) {
24
                    continue;
25
                }
26
                if ((k / base) % m != j) {
27
                    continue;
28
                }
29
                vis[k] = 1;
30
                ans.emplace_back(k, base);
31
            }
32
        }
33
        base *= m;
34
    }
35
    cout << ans.size() << '\n';
36
    for (const auto& [x, y] : ans) {
37
        cout << x << ' ' << y << '\n';
38
    }
39
}