模拟

class Solution {
public:int findKOr(vector<int> &nums, int k) {vector<int> cnt(32);for (auto x: nums)for (int i = 0; i < 32; i++)if (x >> i & 1)cnt[i]++;int res = 0;for (int i = 0; i < 32; i++)if (cnt[i] >= k)res |= 1 << i;return res;}
};

分类讨论：将两个数组中的 $0$ 看作 $1$ 求数组替换完后的最小数组和，若两个数组的最小数组和相等返回 $0$ ，否则只有最小数组和较小的一个数组存在 $0$ 有解。

class Solution {
public:using ll = long long;long long minSum(vector<int> &nums1, vector<int> &nums2) {ll s1 = 0, s2 = 0;//两个数组的最小数组和bool have1 = false, have2 = false;//两个数组是否含有0for (auto x: nums1) {if (x)s1 += x;else {have1 = true;s1 += 1;}}for (auto x: nums2) {if (x)s2 += x;else {have2 = true;s2 += 1;}}if (s1 > s2) {swap(s1, s2);swap(have1, have2);}if (s1 == s2)return s1;return have1 ? s2 : -1;}
};

动态规划：设 $p[i]$ 为将 $nums[0,i]$ 变为美丽数组且满足 $nums[i]\ge k$ 的最小递增运算数，有状态转移方程： p [ i ] = { m a x { k − n u m s [ i ] , 0 } i < 3 m i n { p [ i − 1 ] , p [ i − 2 ] , p [ i − 3 ] } + m a x { k − n u m s [ i ] , 0 } , i ≥ 3 p[i]=\left\{\begin{matrix} max\{k-nums[i],0\} & i<3 \\ min\{p[i-1],p[i-2],p[i-3] \}+max\{k-nums[i],0\} & ,i\ge 3 \end{matrix}\right. p[i]={max{k−nums[i],0}min{p[i−1],p[i−2],p[i−3]}+max{k−nums[i],0}​i<3,i≥3​

class Solution {
public:using ll = long long;long long minIncrementOperations(vector<int> &nums, int k) {int n = nums.size();ll p[n];for (int i = 0; i < 3; i++)p[i] = max(k - nums[i], 0);for (int i = 3; i < n; i++) {p[i] = min({p[i - 1], p[i - 2], p[i - 3]}) + max(k - nums[i], 0);}return min({p[n - 1], p[n - 2], p[n - 3]});}
};

记忆化搜索：设 $p[cur][cnt]$ 为以 $cur$ 为根的子树在之前已经使用了 $cnt$ 次第二种方法的情况下可获得的最大积分，有状态转移方程：$p[cur][cnt]=max\{\begin{array}{c}\lfloor \frac{coins[cur]}{2^{cnt}}\rfloor -k+{\sum }_{j\in son(cur)}p[j][cnt]\\ \lfloor \frac{coins[cur]}{2^{cnt+1}}\rfloor +{\sum }_{j\in son(cur)}p[j][cnt+1]\end{array}$

class Solution {
public:int maximumPoints(vector<vector<int>> &edges, vector<int> &coins, int k) {int n = coins.size();vector<int> e[n];for (auto &ei: edges) {e[ei[0]].push_back(ei[1]);e[ei[1]].push_back(ei[0]);}int M = 16, inf = INT32_MIN;int p[n][M];for (int i = 0; i < n; i++)for (int j = 0; j < M; j++)p[i][j] = inf;//初始化标志function<int(int, int, int)> dfs = [&](int cur, int cnt, int par) {//记忆化搜索if (p[cur][cnt] != inf)return p[cur][cnt];if (cnt == M - 1)//子树所有数已经为都0，接下来全用第二种方法return p[cur][cnt] = 0;int r1 = (coins[cur] >> cnt) - k, r2 = coins[cur] >> (cnt + 1);for (auto j: e[cur]) {if (j == par)continue;r1 += dfs(j, cnt, cur);r2 += dfs(j, cnt + 1, cur);}return p[cur][cnt] = max(r1, r2);};return dfs(0, 0, -1);}
};