LeetCode周赛280场，不讲武德，大家都用动态规划，你用蒙特卡洛瞎蒙？

class Solution {
public:
    int countOperations(int num1, int num2) {
        int ret = 0;
        while (num1 > 0 && num2 > 0) {
            if (num1 >= num2) num1 -= num2;
            else num2 -= num1;
            ret++;
        }
        return ret;
    }
};

class Solution {
public:
    
    map<int, int> separate(vector<int>& nums, int s=0) {
        // 对数组进行分组，统计分组中每个元素出现的次数
        int n = nums.size();
        map<int, int> mp;
        for (int i = s; i < n; i += 2) {
            mp[nums[i]]++;
        }
        
        return mp;
    }
    
    pair<int, int> get_pair(map<int, int>& mp, vector<int>& nums, int s=0, bool haslimit = false, int limit = 0) {
        // 获取出现次数最多的元素以及它出现的次数
        // 如果haslimit为true，则返回出现元素第二多的元素
        int maxi = 0, num = nums[s];
        int n = nums.size();
        for (int i = s; i < n; i+=2) {
            if (haslimit && nums[i] == limit) continue;
            if (mp[nums[i]] > maxi) {
                maxi = mp[nums[i]];
                num = nums[i];
            } 
        }
        return make_pair(num, maxi);
    }
    
    int minimumOperations(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 0;
        // 将数组分奇偶统计
        auto odd_map = separate(nums), even_map = separate(nums, 1);
        // 获取出现次数最多的元素
        auto odd = get_pair(odd_map, nums), even = get_pair(even_map, nums, 1);
        int left = n / 2 + n % 2, right = n / 2;
        // 如果出现最多的元素不相等，那么直接贪心求解
        if (odd.first != even.first) {
            return left - odd.second + right - even.second;
        }
        // 如果相等，需要做取舍
        return min(left - odd.second + right - get_pair(even_map, nums, 1, true, odd.first).second, left - get_pair(odd_map, nums, 0, true, odd.first).second + right - even.second);
    }
};

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        sort(beans.begin(), beans.end());
        int n = beans.size();
        vector<long long> sb(n+2, 0);
        sb[0] = beans[0];
        for (int i = 1; i < n; i++) sb[i] = sb[i-1] + beans[i];
        long long ret = 0x7fffffffffffffff;
        for (int i = 0; i < n; i++) {
            // 左侧部分，即左侧的所有元素和
            long long left = i > 0 ? sb[i-1]: 0;
            // 右侧部分，即右侧所有元素和减去 (n-i-i) * beans[i]
            long long right = sb[n-1] - sb[i] - (long long)beans[i] * (long long) (n-i-1);
            ret = min(ret, left + right);
        }
        return ret;
    }
};

class Solution {
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        int n = nums.size();
        
        int dp[1000000];
        memset(dp, 0, sizeof dp);
        int ret = 0;
        
        // 枚举元素
        for (int i = 0; i < n; i++) {
            // 枚举状态，为了防止同一个元素重复放入，所以倒叙遍历状态
            for (int s = (1 << (2 * numSlots)); s >= 0; s--) {
                // 如果状态中1的数量超过n，说明状态不可能成立，则跳过
                int c = __builtin_popcount(s);
                if (c >= n) continue;
                // 枚举篮子
                for (int j = 0; j < 2 * numSlots; j++) {
                    // 如果篮子为空
                    if ((s & (1 << j)) == 0) {
                        int ns = s + (1 << j);
                        int slots;
                        if (j >= numSlots) slots = j - numSlots + 1;
                        else slots = j+1;
                        dp[ns] = max(dp[ns], dp[s] + (nums[i] & slots));
                        ret = max(ret, dp[ns]);
                    }
                }
            }
        }
        
        return ret;
    }
};

class Solution {
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        int n = nums.size();
        int dp[1 << 20];
        memset(dp, 0, sizeof dp);
        int ret = 0;
        
        for (int s = 0; s < (1 << (2 * numSlots)); s++) {
            // c为s中1的数量
            int c = __builtin_popcount(s);
            if (c >= n) continue;
            for (int j = 0; j < 2 * numSlots; j++) {
                if ((s & (1 << j)) == 0) {
                    int ns = s + (1 << j);
                    int slots = j / 2 + 1;
                    dp[ns] = max(dp[ns], dp[s] + (nums[c] & slots));
                    ret = max(ret, dp[ns]);
                }
            }
        }
        
        return ret;
    }
};

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        ans=0
        for i in range(1000):
            random.shuffle(nums)
            cur=0
            counter=defaultdict(int)
            for n in nums:
                j=0
                for i in range(1,numSlots+1):
                    if counter[i]<2 and n&i>n&j:
                        j=i
                counter[j]+=1
                cur+=n&j
            ans=max(ans,cur)
        
        return ans