LeeCode 1787 DP

题意

传送门 LeeCode 1787 使所有区间的异或结果为零

题解

任一个元素都至多对$k$个长度为$k$的区间产生影响，故难以直接依次处理每一个元素。

观察到满足条件的数组中模$k$意义下索引相等的各个元素相同，故可以依次处理每一个同余类。$dp[i][j]$表示前$i$个同余类异或结果为$j$情况下的最小更改元素数。直接枚举每一种取值，时间复杂度$O(n{2}^{20})$，难以胜任。设同余类$i$元素规模为$m$，则至多改动$m$个元素，则可以从任一个状态转移过来，那么贪心地选择改动数量最少的状态即可。对于出现在同余类中的取值，直接暴力枚举即可。总时间复杂度$O(n{2}^{10})$。

#include <bits/stdc++.h>
using namespace std;class Solution {public:int minChanges(vector<int>& nums, int k) {vector<map<int, int>> cnt(k);vector<int> num(k);int n = nums.size();for (int i = 0; i < n; ++i) {num[i % k] += 1;cnt[i % k][nums[i]] += 1;}auto _min = [](int& x, int y) {x = min(x, y);};const int lg = 10;const int inf = 1e9;vector<vector<int>> dp(k + 1, vector<int>(1 << lg, inf));dp[0][0] = 0;for (int i = 0; i < k; ++i) {int m = num[i];int p = min_element(dp[i].begin(), dp[i].end()) - dp[i].begin();for (int j = 0; j < 1 << lg; ++j) {for (auto& [x, c] : cnt[i]) {_min(dp[i + 1][j], dp[i][j ^ x] + m - c);}_min(dp[i + 1][j], dp[i][p] + m);}}return dp[k][0];}
};