小红的二进制操作

[牛客链接](https://www.nowcoder.com/practice/56abe43a513f46cd94ca5f9911ec9372)

题意

给定长度为 $n$ 的数组 $a$ ，最多执行两次操作：选择一个元素使其加 1（可以对同一个元素操作两次）。操作结束后，求数组所有元素乘积的二进制表示末尾最多有多少个 0。

思路

二进制末尾 0 的个数，就是乘积中因子 2 的个数。设 $v_2(x)$ 表示 $x$ 中因子 2 的幂次（2-adic valuation），则初始答案为：

$ $\text{base} = \sum_{i=1}^{n} v_2(a_i)$ $

我们有最多 2 次 +1 操作，分配方式只有以下四种情况：

不操作：答案为 $\text{base}$ 。
对某个元素 +1：增益为 $g_1(i) = v_2(a_i + 1) - v_2(a_i)$ ，取最大的 $g_1(i)$ 。
对某个元素 +2：增益为 $g_2(i) = v_2(a_i + 2) - v_2(a_i)$ ，取最大的 $g_2(i)$ 。
对两个不同元素各 +1：增益为 $g_1(i) + g_1(j)$ ，取 $g_1$ 数组中最大的两个值之和。

注意 $g_1(i)$ 可能为负（例如 $a_i = 2$ 时， $v_2(2) = 1$ 而 $v_2(3) = 0$ ），因此不操作的情况也要考虑。

以样例验证： $a = [1,2,3,4,5]$ ， $\text{base} = 0 + 1 + 0 + 2 + 0 = 3$ 。

$g_1 = [1, -1, 2, -2, 1]$ ，最大两个为 $2 + 1 = 3$ 。
情况 4 的答案 $= 3 + 3 = 6$ ，即对 $1 \to 2$ （+1）和 $3 \to 4$ （+2 因子）。

最终在所有情况中取最大值即可。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int v2(long long x) {
    if (x == 0) return 0;
    int cnt = 0;
    while (x % 2 == 0) { cnt++; x /= 2; }
    return cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> a(n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);

    int base = 0;
    for (int i = 0; i < n; i++) base += v2(a[i]);

    int ans = base;

    vector<int> g1(n), g2(n);
    for (int i = 0; i < n; i++) {
        g1[i] = v2(a[i] + 1) - v2(a[i]);
        g2[i] = v2(a[i] + 2) - v2(a[i]);
    }

    // 单次 +1
    int best1 = *max_element(g1.begin(), g1.end());
    ans = max(ans, base + best1);

    // 单次 +2
    int best2 = *max_element(g2.begin(), g2.end());
    ans = max(ans, base + best2);

    // 两个不同元素各 +1：取 g1 最大的两个
    if (n >= 2) {
        int top1 = INT_MIN, top2 = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (g1[i] >= top1) {
                top2 = top1;
                top1 = g1[i];
            } else if (g1[i] > top2) {
                top2 = g1[i];
            }
        }
        ans = max(ans, base + top1 + top2);
    }

    printf("%d\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    static int v2(long x) {
        if (x == 0) return 0;
        int cnt = 0;
        while (x % 2 == 0) { cnt++; x /= 2; }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();

        int base = 0;
        for (int i = 0; i < n; i++) base += v2(a[i]);

        int ans = base;

        int[] g1 = new int[n], g2 = new int[n];
        for (int i = 0; i < n; i++) {
            g1[i] = v2(a[i] + 1) - v2(a[i]);
            g2[i] = v2(a[i] + 2) - v2(a[i]);
        }

        int best1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) best1 = Math.max(best1, g1[i]);
        ans = Math.max(ans, base + best1);

        int best2 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) best2 = Math.max(best2, g2[i]);
        ans = Math.max(ans, base + best2);

        if (n >= 2) {
            int top1 = Integer.MIN_VALUE, top2 = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                if (g1[i] >= top1) {
                    top2 = top1;
                    top1 = g1[i];
                } else if (g1[i] > top2) {
                    top2 = g1[i];
                }
            }
            ans = Math.max(ans, base + top1 + top2);
        }

        System.out.println(ans);
    }
}

复杂度分析

时间复杂度： $O(n)$ ，遍历数组常数次，每个元素计算 $v_2$ 的复杂度为 $O(\log a_i)$ 。
空间复杂度： $O(n)$ ，存储增益数组。