算法1

(DP) $O(1e6)$

C++ 代码

class Solution {
private:
    static const int maxn = 2010;
    unordered_map<int,int> g[maxn];
    int gsize[maxn], f[2][1030];
public:
    int minChanges(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i = 0; i < n; i++) 
            gsize[i%k]++, g[i%k][nums[i]]++;
        for(int i = 1; i < 1024; i++) f[k&1][i] = INT_MAX;
        int tmin = 0;
        for(int d=k-1;d>=0;d--) {
            int nextt = INT_MAX;
            for(int j = 0; j < 1024; j++) {
                f[d&1][j] = tmin;
                for(const auto &[x, time] : g[d]) 
                    f[d&1][j] = min(f[d&1][j], -time+f[(d+1)&1][j^x]);
                f[d&1][j] += gsize[d];
                nextt = min(nextt, f[d&1][j]);
            }
            tmin = nextt;
        }
        return f[0][0];
    }
};
// 这道题，被转化为以下问题：
// 选出包含k个数的异或和为0的组合，找到权值最小的一个
// dfs(i,xsum)
// 直接枚举，爆定了
// 解是必定存在的，有无后效性
// for x in ith group
//  ans = min(ans, ith group size - amount of x in ith group + dfs(i+1, xsum^x))
// 要注意一种情况：不从ith组直接选出，而是将所有ith组位置的值改成一个值x，使得
// i...k-1的组合异或和为0，x取值什么呢？不重要，是一个不在ith组的值
// 然后，i+1...k-1组合异或和为0的最小代价+ith上元素全部修改为xsum的代价gsize[i];