CF1188D Make Equal 题解-526互联

题意

给定 \(n\) 个数 \(a_1, a_2, \cdots, a_n\)，每次操作可以给其中的一个数加上 \(2\) 的非负整数次幂。求最小的操作次数，使得这 \(n\) 个数相等。

题解

首先考虑如何计算操作次数，设 \(maxa = \max\limits_{i = 1}^{n} a_i\)，如果我们把这 \(n\) 个数操作成了数 \(x\)（\(x \ge maxa\)），那么一共需要的操作次数为 \(\sum\limits_{i = 1}^{n} \operatorname{popcount\left(x - a_i\right)}\)。我们设 \(\Delta = x - maxa, b_i = maxa - a_i\)，那么需要的操作次数为 \(\sum\limits_{i = 1}^{n} \operatorname{popcount\left(\Delta + b_i\right)}\)。这样我们就可以把问题转化为求出一个 \(\Delta\)，最小化 \(\sum\limits_{i = 1}^{n} \operatorname{popcount\left(\Delta + b_i\right)}\)。

因为涉及到了位运算，我们考虑从低到高按位决策 \(\Delta\) 的值，影响第 \(i\) 位操作次数的因素有三：

\(\Delta\) 在第 \(i\) 位的取值；
\(b_k\) 在第 \(i\) 位的取值；
\(b_k + \Delta\) 在第 \(i - 1\) 位是否会产生进位。

发现二进制下在第 \(i\) 位越容易进位的数在模 \(2^i\) 下越大，所以再处理每一位的时候可以先将 \(b_i\) 按模 \(2^i\) 的值降序排序，这样的话如果有 \(j\) 个数进位，那么一定是排序后的前 \(j\) 个数。

这样我们就可以设计出状态了。设 \(f_{i, j}\) 表示在二进制表示下有 \(j\) 个数进位到了第 \(i\) 位时的最优解。

接下来考虑转移，发现我们只需要处理当前二进制下第 \(i\) 位是否为 \(1\)和在第 \(i - 1\) 位进位的数个数 \(j\)。那么一共有 \(4\) 种数。接下来的讨论钦定上一位有 \(j\) 个数进位。

令 \(allCount\) 为这一位下为 \(1\) 的 \(b_k\) 的个数，\(nowCount\) 为这一位下为 \(1\) 且 \(k \le j\) 的 \(b_k\) 的个数。

\(b_k + \Delta\) 在第 \(i - 1\) 位产生进位且 \(b_k\) 的第 \(i\) 位为 \(1\)，有 \(nowCount\) 个。
\(b_k + \Delta\) 在第 \(i - 1\) 位产生进位且 \(b_k\) 的第 \(i\) 位为 \(0\)，有 \(j - nowCount\) 个。
\(b_k + \Delta\) 在第 \(i - 1\) 位没有进位且 \(b_k\) 的第 \(i\) 位为 \(1\)，有 \(allCount - nowCount\) 个。
\(b_k + \Delta\) 在第 \(i - 1\) 位没有进位且 \(b_k\) 的第 \(i\) 位为 \(0\)，有 \(n - j - \left(allCount - nowCount\right)\) 个。

那么我们考虑 \(\Delta\) 在第 \(i\) 位如何决策。

如果 \(\Delta\) 取 \(1\)，那么第 \(1, 2, 3\) 种数会产生进位，第 \(1, 4\) 种数的 \(\Delta + b_k\) 这一位是 \(1\)，需要进行操作。
如果 \(\Delta\) 取 \(0\)，那么第 \(1\) 种数会产生进位，第 \(2, 3\) 种数的 \(\Delta + b_k\) 这一位是 \(1\)，需要进行操作。

所以我们可以得出转移式：

\[\begin{aligned}f_{i + 1, allCount - nowCount + j} &= \min{f_{i, j} + nowCount + \left(n - j\right) - \left(allCount - nowCount\right)} \\ f_{i + 1, nowCount} &= \min{f_{i, j} + j - nowCount + allCount - nowCount}\end{aligned}\]

至此我们就可以以 \(\mathcal{O}(n \log n \log a)\) 的复杂度通过本题。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

constexpr valueType maxB = 58;
constexpr valueType MIN = LONG_LONG_MIN >> 8, MAX = LONG_LONG_MAX >> 8;

typedef std::array<valueType, maxB> BitArray;
typedef std::bitset<maxB> bitset;
typedef std::vector<bitset> BitsetVector;

valueType popcount(valueType x) {
    return __builtin_popcountll(x);
}

constexpr std::array<valueType, maxB> bin = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 31072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 5184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872};

class ModCompare {
private:
    valueType mod;

public:
    explicit ModCompare(valueType mod) : mod(mod) {}

    bool operator()(valueType a, valueType b) const {
        return a % mod > b % mod;
    }

    void setMod(valueType m) {
        mod = m;
    }
};

int main() {
    std::ios::sync_with_stdio(false);

    valueType N;

    std::cin >> N;

    ValueVector source(N);

    for (auto &iter: source)
        std::cin >> iter;

    valueType const maxNumber = *std::max_element(source.begin(), source.end());

    for (auto &iter: source)
        iter = maxNumber - iter;

    BitArray bitCount;

    for (valueType i = 0; i < maxB; ++i)
        for (auto const &iter: source)
            if (iter & bin[i])
                ++bitCount[i];

    ValueMatrix dp(maxB, ValueVector(N + 1, MAX));

    dp[0][0] = 0;

    for (valueType i = 0; i < maxB - 1; ++i) {
        if (i > 0)
            std::sort(source.begin(), source.end(), ModCompare(bin[i]));

        valueType allCount = 0, nowCount = 0;

        for (auto const &iter: source)
            if (iter & bin[i])
                ++allCount;

        for (valueType j = 0; j <= N; ++j) {
            if (j > 0 && source[j - 1] & bin[i])
                ++nowCount;

            dp[i + 1][allCount - nowCount + j] = std::min(dp[i + 1][allCount - nowCount + j], dp[i][j] + nowCount + (N - j) - (allCount - nowCount));

            dp[i + 1][nowCount] = std::min(dp[i + 1][nowCount], dp[i][j] + j - nowCount + allCount - nowCount);
        }
    }

    std::cout << dp[maxB - 1][0] << std::endl;

    return 0;
}

codeforces 1188d equal make

problem 1188e panda from