第 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 最小处理时间
排序：设四个 p r o c e s s o r T i m e processorTime processorTime 的元素形成的数组为 p p p ， p p p 降序排序， t a s k s tasks tasks 升序排序， p p p 和 t a s k s tasks 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 执行操作使两个字符串相等
动态规划：设 s 1 s1 s1 和 s 2 s2 s2 相同下标元素不同的下标位置的序列为 l i li li ，若 l i li li 长度为奇数则返回 − 1 -1 −1 。设 p i , j p_{i,j} pi,j 为使得 s 1 s1 s1在 l i [ i , j ] li[i,j] li[i,j] 中的下标处与 s 2 s2 s2 相同的最小代价， p i , j p_{i,j} pi,j 可由 p i + 1 , j − 1 p_{i+1,j-1} pi+1,j−1 或 p i , k + p k + 1 , j p_{i,k}+p_{k+1,j} pi,k+pk+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 1 的数目，所以统计二进制各位 1 1 1 的总数，按非降序，尽可能大地生成 k k 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;}
};