第 366 场周赛 LeetCode 周赛题解

A 分类求和并作差

模拟

class Solution {
public:int differenceOfSums(int n, int m) {int res = 0;for (int i = 1; i <= n; i++)res += i % m != 0 ? i : -i;return res;}
};

---

B 最小处理时间

排序：设四个 $processorTime$ 的元素形成的数组为 $p$ ，$p$ 降序排序，$tasks$ 升序排序，$p$ 和 $tasks$ 按下标逐位相加产生的最大元素即为答案

class Solution {
public:int minProcessingTime(vector<int> &processorTime, vector<int> &tasks) {vector<int> p;for (auto x: processorTime)for (int i = 0; i < 4; i++)p.push_back(x);sort(p.begin(), p.end(), greater<>());sort(tasks.begin(), tasks.end());int res = 0;for (int i = 0; i < tasks.size(); i++)res = max(res, p[i] + tasks[i]);return res;}
};

---

C 执行操作使两个字符串相等

动态规划：设 $s1$ 和 $s2$ 相同下标元素不同的下标位置的序列为 $li$ ，若 $li$ 长度为奇数则返回 $-1$ 。设 $p_{i,j}$ 为使得 $s1$在 $li[i,j]$ 中的下标处与 $s2$ 相同的最小代价，$p_{i,j}$ 可由 $p_{i+1,j-1}$ 或 $p_{i,k}+p_{k+1,j}$转移得到。

class Solution {
public:int minOperations(string s1, string s2, int x) {vector<int> li;for (int i = 0; i < s1.size(); i++)if (s1[i] != s2[i])li.push_back(i);if (li.empty())return 0;if (li.size() & 1)return -1;int m = li.size();int p[m][m];for (int len = 1; len <= m; len++)for (int i = 0, j = i + len - 1; j < m; i++, j++)if (len & 1)p[i][j] = -1;else {if (len == 2)p[i][j] = li[j] == li[i] + 1 ? 1 : min(x, li[j] - li[i]);else {p[i][j] = p[i + 1][j - 1] + x;for (int k = i + 1; k < j; k += 2)p[i][j] = min(p[i][j], p[i][k] + p[k + 1][j]);}}return p[0][m - 1];}
};

---

D 对数组执行操作使平方和最大

贪心：题目所述操作不会改变数组中二进制各位上的 $1$ 的数目，所以统计二进制各位 $1$ 的总数，按非降序，尽可能大地生成$k$个数。

class Solution {
public:int maxSum(vector<int> &nums, int k) {vector<int> cnt(31);long long mod = 1e9 + 7;for (auto x: nums)for (int i = 0; i <= 30; i++)if (x >> i & 1)cnt[i]++;int res = 0;while (k--) {int cur = 0;for (int i = 0; i <= 30; i++)if (cnt[i]) {cnt[i]--;cur |= 1 << i;}res = (res + 1LL * cur * cur % mod) % mod;}return (res + mod) % mod;}
};