lc3811
合法子序列dp
lc560
前缀异或_hash动态统计，计算将数组分割为交替异或和等于 target1 、 target2 的子段的方案数，结果取模 10^9+7
class Solution {
public:
int alternatingXOR(vector<int>& nums, int target1, int target2) {
constexpr int MOD = 1'000'000'007;
unordered_map<int, int> f1;
unordered_map<int, int> f2 = {{0, 1}};
int pre_sum = 0;
for (int i = 0; ; i++) {
pre_sum ^= nums[i];
int last1 = f2[pre_sum ^ target1];
// [0,i] 的最后一段的异或和是 target1 的方案数
int last2 = f1[pre_sum ^ target2];
// [0,i] 的最后一段的异或和是 target2 的方案数
if (i == nums.size() - 1)
return (last1 + last2) % MOD;
f1[pre_sum] = (f1[pre_sum] + last1) % MOD;
f2[pre_sum] = (f2[pre_sum] + last2) % MOD;
}
}
};
不推荐用 状态机dp 不一定具有周期性
lc3810
class Solution {
public:
int minOperations(vector<int>& nums, vector<int>& target) {
unordered_set<int> st;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
if (x != target[i]) {
st.insert(x);
}
}
return st.size();
}
};
lc3809
多条件tuple cmp trick
ans = min(ans, tuple{-q, x, y}); // 加个负号，变成求 q 的最大值
class Solution {
public:
vector<int> bestTower(vector<vector<int>>& towers, vector<int>& center, int radius) {
int cx = center[0], cy = center[1];
auto ans = tuple{1, -1, -1};
for (auto& t : towers) {
int x = t[0], y = t[1], q = t[2];
if (abs(x - cx) + abs(y - cy) <= radius) {
ans = min(ans, tuple{-q, x, y}); // 加个负号，变成求 q 的最大值
}
}
return {get<1>(ans), get<2>(ans)};
}
};
)
