题解：CF2157F Git Gud

· · 题解

Solution

以下 N = 250000。

首先第一反应是分块，设每 B 个一组，组内从大到小排序，组内代价总和就是 \frac{B(B + 1)}{2}。这样贡献就是 \frac{1000N}{B} + \frac{B^2(B + 1)}{2}，这个显然是很劣的。但这个分组，且组内从大到小的想法自然且十分重要。

接着我们考虑，每一次组内的一个数 X，加上一个它的代价后，跳到 Y，那么需要满足 Y 的位置在 X 后，且我们还希望分的组较少，每个数的代价也少。

从这个向后跳的过程中，有无感觉出树状数组的影子，就是每一次 X + \operatorname{lowbit}(X)。这启示我们可以按照 \operatorname{lowbit}(X) 分组。这样一共有 \log_2{N} 组，总贡献写个程序算一下，可以达到 2238248。

还是不可以，但我们想到，我们分的组还是太少了，才不到 20 个。那就从这个地方入手，考虑若以 m 为底，那么组数将会是 (m - 1)\log_mN，并且这个是单增的。然后对于一个数 X，设它在 m 进制下一共从最低位开始连续 0 的个数为 x，那么定义其代价就是 m^x。这样整体代价随 m 增长越平均，其平均数也显然是一个凸函数，求个导什么的应该就能证。

懒得算了，手动二分以下，m = 100 即可通过，总代价为 956000。但最小的时候应该是 m = 63，总代价为 923093。但 CodeForces 的题解评论区中，还有神仙达到了 8.5 \times 10^5，很神秘，很智慧，很无敌，很是非人类。

对于 n = 4，直接输出样例就可以了。

:::success[AC Code (m = 100)]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 250005;
pair<int, pair<int, int> > a[N];
bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
    if (a.x == b.x) return a.y.x > b.y.x;
    return a.x < b.x;
}
int calc() {
    long long ans = 0;
    For(i, 1, 250000) ans += min(a[i].y.y, 250000 - a[i].y.x);
    cout << 249999 << '\n';
    For(i, 1, 250000) if (a[i].y.x != 250000)cout << a[i].y.x << ' ' << min(a[i].y.y, 250000 - a[i].y.x) << '\n';
    For(i, 2, 250000) if (a[i].y.x != 250000) if (a[i].y > a[i - 1 - (a[i - 1].y.x == 250000)].y) ans += 1000;
    return ans;
}
int work(int B) {
    For(i, 1, 250000) {
        int last = 1;
        int x = i;
        while (x % B == 0) {
            last = last * B;
            x /= B;
        }
        a[i].x = last * (x % B);
        a[i].y.x = i;
        a[i].y.y = last;
    }
    sort(a + 1, a + 250000 + 1, cmp);
    long long ans = calc();
    return ans;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    if (n == 4) {
        cout << "4\n";
        cout << "1 4\n";
        cout << "3 1\n";
        cout << "2 1\n";
        cout << "3 1\n";
        return 0;
    }
    int B = 100;
    int ans = work(B);
    //cout << ans;
    return 0; 
}

:::

:::success[AC Code (m = 63)]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 250005;
pair<int, pair<int, int> > a[N];
bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
    if (a.x == b.x) return a.y.x > b.y.x;
    return a.x < b.x;
}
int calc() {
    long long ans = 0;
    For(i, 1, 250000) ans += min(a[i].y.y, 250000 - a[i].y.x);
    cout << 249999 << '\n';
    For(i, 1, 250000) if (a[i].y.x != 250000)cout << a[i].y.x << ' ' << min(a[i].y.y, 250000 - a[i].y.x) << '\n';
    For(i, 2, 250000) if (a[i].y.x != 250000) if (a[i].y > a[i - 1 - (a[i - 1].y.x == 250000)].y) ans += 1000;
    return ans;
}
int work(int B) {
    For(i, 1, 250000) {
        int last = 1;
        int x = i;
        while (x % B == 0) {
            last = last * B;
            x /= B;
        }
        a[i].x = last * (x % B);
        a[i].y.x = i;
        a[i].y.y = last;
    }
    sort(a + 1, a + 250000 + 1, cmp);
    long long ans = calc();
    return ans;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    if (n == 4) {
        cout << "4\n";
        cout << "1 4\n";
        cout << "3 1\n";
        cout << "2 1\n";
        cout << "3 1\n";
        return 0;
    }
    int B = 63;
    int ans = work(B);
    //cout << ans;
    return 0; 
}

:::