题解 | #小红的二进制操作#

题目链接

题目描述

小红拿到了一个数组，她可以进行最多两次操作：选择一个元素，使其加1。小红希望操作结束后，数组所有元素乘积的二进制末尾有尽可能多的0。你能帮帮她吗？

思路分析

一个数的二进制末尾有多少个0，取决于其质因数分解中因子2的数量。设这个数量为 $v_2(x)$ 。整个数组所有元素乘积的二进制末尾0的数量，就是数组中每个元素 $v_2(a_i)$ 的总和，即 $\sum_{i=1}^{n} v_2(a_i)$ 。

我们的目标是最多使用两次“加1”操作来最大化这个总和。这是一个典型的贪心问题，我们需要让每次操作的“收益”（即 $v_2$ 总和的增量）最大化。

我们可以分情况讨论这两次操作的分配方式：

0次操作： baseline，总和为初始数组的 $\sum v_2(a_i)$ 。
1次操作：我们应该遍历所有元素 $a_i$ ，计算将 $a_i$ 变为 $a_i+1$ 带来的增量 $v_2(a_i+1) - v_2(a_i)$ 。我们选择能使这个增量最大的那个元素进行操作。
2次操作：这两次操作可以有两种用法：
- 作用于两个不同元素：为了总收益最大，我们应该贪心地选择那两个能提供最大单次操作增量的元素。即，我们计算出所有元素的单次操作增量，然后取最大的两个相加。
- 作用于同一个元素两次：我们将两次操作都用于同一个元素 $a_i$ ，使其变为 $a_i+2$ 。这种情况带来的增量是 $v_2(a_i+2) - v_2(a_i)$ 。我们需要遍历所有元素，找到这种“二次操作”能带来的最大增量。

最终的答案就是上述所有可能情况（0次操作、1次操作、2次操作于不同元素、2次操作于相同元素）中，能得到的 $v_2$ 总和的最大值。

算法步骤：

计算初始的 $v_2$ 总和 $S = \sum v_2(a_i)$ 。
对每个元素 $a_i$ ，计算两种潜在的增量：
- 单次操作增量： $g_1(i) = v_2(a_i+1) - v_2(a_i)$ 。
- 二次操作增量： $g_2(i) = v_2(a_i+2) - v_2(a_i)$ 。
将所有单次操作增量 $g_1$ 存入一个列表并降序排序。
找到所有二次操作增量 $g_2$ 中的最大值，记为 max_g2。
最终的最大增量 max_gain 是以下几种情况的最大值：
- 0 (0次操作)
- g1[0] (1次操作)
- g1[0] + g1[1] (2次操作于不同元素)
- max_g2 (2次操作于相同元素)
最终答案是 $S + \text{max_gain}$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

// 使用GCC/Clang内置函数计算二进制末尾0的个数，效率很高
int count_trailing_zeros(int n) {
    if (n <= 0) return 0; // __builtin_ctz(0) is undefined
    return __builtin_ctz(n);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    long long initial_sum = 0;
    vector<int> gains1;
    vector<int> gains2;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        int v_orig = count_trailing_zeros(a[i]);
        initial_sum += v_orig;
        gains1.push_back(count_trailing_zeros(a[i] + 1) - v_orig);
        gains2.push_back(count_trailing_zeros(a[i] + 2) - v_orig);
    }

    long long max_gain = 0;

    sort(gains1.begin(), gains1.end(), greater<int>());

    // 情况1: 使用1次操作
    if (n >= 1) {
        max_gain = max(max_gain, (long long)gains1[0]);
    }

    // 情况2: 使用2次操作
    if (n >= 1) {
        long long max_gain_2_ops = -2e18; // 一个足够小的值
        if (n >= 2) {
            // 2次操作在不同元素上
            max_gain_2_ops = max(max_gain_2_ops, (long long)gains1[0] + gains1[1]);
        }
        
        // 2次操作在相同元素上
        int max_g2 = -2e9;
        for (int g : gains2) {
            max_g2 = max(max_g2, g);
        }
        max_gain_2_ops = max(max_gain_2_ops, (long long)max_g2);
        
        max_gain = max(max_gain, max_gain_2_ops);
    }

    cout << initial_sum + max_gain << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        long initialSum = 0;
        List<Integer> gains1 = new ArrayList<>();
        List<Integer> gains2 = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            int vOrig = Integer.numberOfTrailingZeros(a[i]);
            initialSum += vOrig;
            gains1.add(Integer.numberOfTrailingZeros(a[i] + 1) - vOrig);
            gains2.add(Integer.numberOfTrailingZeros(a[i] + 2) - vOrig);
        }

        long maxGain = 0;

        Collections.sort(gains1, Collections.reverseOrder());

        // 情况1: 使用1次操作
        if (n >= 1) {
            maxGain = Math.max(maxGain, gains1.get(0));
        }

        // 情况2: 使用2次操作
        if (n >= 1) {
            long maxGain2Ops = Long.MIN_VALUE;
            if (n >= 2) {
                // 2次操作在不同元素上
                maxGain2Ops = Math.max(maxGain2Ops, (long)gains1.get(0) + gains1.get(1));
            }

            // 2次操作在相同元素上
            int maxG2 = Integer.MIN_VALUE;
            for (int g : gains2) {
                maxG2 = Math.max(maxG2, g);
            }
            maxGain2Ops = Math.max(maxGain2Ops, maxG2);
            
            maxGain = Math.max(maxGain, maxGain2Ops);
        }

        System.out.println(initialSum + maxGain);
    }
}

import sys

# 辅助函数计算二进制末尾0的个数
def count_trailing_zeros(n):
    if n <= 0:
        return 0
    # (n & -n) 可以分离出最低位的1
    # .bit_length() - 1 可以得到这个1的位置(0-indexed)
    return (n & -n).bit_length() - 1

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    initial_sum = 0
    gains1 = []
    gains2 = []

    for x in a:
        v_orig = count_trailing_zeros(x)
        initial_sum += v_orig
        gains1.append(count_trailing_zeros(x + 1) - v_orig)
        gains2.append(count_trailing_zeros(x + 2) - v_orig)

    max_gain = 0
    
    gains1.sort(reverse=True)

    # 情况1: 使用1次操作
    if n >= 1:
        max_gain = max(max_gain, gains1[0])

    # 情况2: 使用2次操作
    if n >= 1:
        max_gain_2_ops = -float('inf')
        if n >= 2:
            # 2次操作在不同元素上
            max_gain_2_ops = max(max_gain_2_ops, gains1[0] + gains1[1])
        
        # 2次操作在相同元素上
        max_gain_2_ops = max(max_gain_2_ops, max(gains2))
        
        max_gain = max(max_gain, max_gain_2_ops)

    print(initial_sum + max_gain)

solve()

算法及复杂度

算法：贪心
时间复杂度： $O(N \log N)$ ，其中 $N$ 是数组的大小。主要的时间开销在于对单次操作增益列表 gains1 的排序。计算初始值和增益列表本身是 $O(N)$ 。
空间复杂度： $O(N)$ ，用于存储两种操作的增益列表。