【位运算】个人练习-Leetcode-2897. Apply Operations on Array to Maximize Sum of Squares

题目链接：https://leetcode.cn/problems/apply-operations-on-array-to-maximize-sum-of-squares/description/

题目大意：给定一个数组nums[]，给出一种操作，该操作选定两个不同的数组元素x, y，然后将其中一个变为x AND y，另一个变为x OR y（二进制操作）。给定一个k，要求在进行任意次操作后，从数组中选k个元素的平方和最大。

思路：观察这个操作，其实就是把二进制x的1和二进制y中的0互换（仅当同位置上一个为0一个为1时，因为AND和OR操作都不改变都为0和都为1的情况）。其实可以发现，这样下来，【每个位上面的总的0和总的1数量都不变】。

于是我们就统计一下每个位上面的总的0和总的1数量，开个30长度的数组就行，因为最大的$10^9<2^{30}$。

        int cnt[30] = {};
        for (auto x: nums) {
            for (int i = 0; i < 30; i++) {
                cnt[i] += (x >> i) & 1;
            }
        }

要使结果尽可能大，就要把1集中在选的k个数上，那么贪心即可，选k个数，每个数都尽量把剩下的每个位上的1都取走就行。

        long long ans = 0;
        while (k--) {
            int x = 0;
            for (int i = 0; i < 30; i++) {
                if (cnt[i]) {
                    cnt[i]--;
                    x |= 1 << i;
                }
            }
            ans = (ans + (long long)(x * x)) % MAX;
        }
        return ans;

思路倒是不太难的，只不过具体怎么位运算有点忘了，还是看了下题解…

完整代码

class Solution {
public:
    int maxSum(vector<int>& nums, int k) {
        const int MAX = 1000000007;
        int cnt[30] = {};
        for (auto x: nums) {
            for (int i = 0; i < 30; i++) {
                cnt[i] += (x >> i) & 1;
            }
        }
        long long ans = 0;
        while (k--) {
            int x = 0;
            for (int i = 0; i < 30; i++) {
                if (cnt[i]) {
                    cnt[i]--;
                    x |= 1 << i;
                }
            }
            ans = (ans + (long long)(x * x)) % MAX;
        }
        return ans;
    }
};