本次周赛不难，随便水水就做完了，心情舒适
涉及知识点：二维数组翻转，前缀和，桶，滑动窗口，海明距离，二分查找，贪心
判断矩阵经轮转后是否一致
给定两个 (n imes n) 的 (01) 矩阵，分别记为 (A, B)，现在可以将 (A) 顺时针旋转 (90) 度，判断 (A) 能否变成 (B)
数据规定
(1leq nleq 10)
题解
设原来元素的位置为 ((i, j))，旋转后为 ((j, n - i - 1))，模拟即可
class Solution {
public:
bool check(vector<vector<int>>& A, vector<vector<int>>& B)
{
int n = A.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
if (A[i][j] != B[i][j]) return false;
}
return true;
}
vector<vector<int>> rot(vector<vector<int>>& A)
{
int n = A.size();
vector<vector<int>> B(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
B[j][n - i - 1] = A[i][j];
}
}
return B;
}
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
for (int i = 0; i < 4; ++i) {
if (check(mat, target)) return true;
mat = rot(mat);
}
return false;
}
};
使数组元素相等的减少操作次数
给定长度为 (n) 的正整数数组 (A)，你的目标是令 (A) 中的所有元素相等，完成一次减少操作需要遵照下面的几个步骤：
- 找出 (A) 中的 最大值，记录其下标 (pos)，如果有多个最大值，记录下标最小的那个
- 找出 (A) 中的 次大值，记录其值为 (val)，要求次大值严格小于最大值
- 将 (A_{pos}) 置为 (val)，即 (A_{pos} = val)
返回使得 (A) 中所有元素相等的最少操作数
数据规定
(1leq n, A_{i}leq 5cdot 10^4)
题解
从简单的情况分析，考虑数组 {1, 2, 3, 4, 5}
我们发现步骤如下
- 所有的 (5) 变成 (4)
- 所有的 (4) 变成 (3)
- 所有的 (3) 变成 (2)
- 所有的 (2) 变成 (1)
实际上，我们是把所有的最大值全部变成次大值，再把次大值变为次次大值，循环往复，直到所有的值都变成最小值
我们用 (cnt) 桶来维护每一个值出现的次数，反向枚举，用 (maxx, mini) 分别表示最大值和最小值，答案为
其中，若 (cnt_{i}) 本身不为 (0)，在统计答案前要先加上前缀和，因为更大的元素也变成了 (i)，即
时间复杂度为 (O(maxx))
使二进制字符串字符交替的最少反转次数
给定一个长为 (n) 的 (01) 串 (s)，你可以执行以下两个操作任意多次
- 删除 (s) 第一个字符并添加到 (s) 的尾部
- 翻转字符，即 (0 ightarrow 1, 1 ightarrow 0)
返回使得 (s) 变成 交替 字符串的前提下，操作 (2) 的 最小操作数
数据规定
(1leq nleq 10^5)
题解
操作 (1) 等同于将前缀拼接在 (s) 的尾部，这种问题，类似于循环队列，我们可以将两个 (s) 拼接在一起，然后用一个长度为 (n) 的滑动窗口扫描即可
对于变成交替字符串的最小操作数问题，我们可以使用 海明距离，确切的来讲，我们用长度为 (n) 的 (10101010..) 和 (01010101..) 分别与滑动的窗口异或，维护最小值即可
在实际异或过程中，我们舍弃窗户头的元素，添加窗户尾的元素，总的时间复杂度为 (O(n))
class Solution {
public:
int solve(string s, int flag)
{
int n = s.length();
int temp = 0;
for (int i = 0; i < n; ++i) {
temp += (s[i] - '0') ^ ((i + flag) % 2);
}
int ans = temp;
for (int i = 1; i < n; ++i) {
int L = i - 1, R = i + n - 1;
temp -= (s[L] - '0') ^ ((L + flag) % 2);
temp += (s[L] - '0') ^ ((R + flag) % 2);
ans = min(ans, temp);
}
cout << ans << endl;
return ans;
}
int minFlips(string s) {
return min(solve(s, 0), solve(s, 1));
}
};
装包裹的最小浪费空间
给定 (n) 个包裹，每个包裹的重量为 (p_{i})
给定 (m) 个箱子供货商，每个供货商提供 (b_{i}) 个箱子，容量为 (b_{i, j})
对于一个容量为 (v) 的箱子和一个重量为 (w) 的包裹，当且仅当 (vgeq w) 时，箱子可以容纳这个包裹，并且浪费的空间为 (v - w)
现在选择一个供货商，使得浪费的总空间最小，如果没有供应商可以承担这个责任，返回 (-1)
数据规定
(1leq n, m, p_{i}, b_{i, j}, sumlimits_{i = 1}^mb_{i}leq 10^5)
题解
对于每一个供应商，计算最小浪费空间
具体来讲，我们希望小箱子容纳小包裹，大箱子容纳大包裹，因此首先对供应商提供的箱子根据容量排序，然后计算可以被当前箱子容纳的最后一个包裹，这个过程可以二分查找解决，当然二分的前提是对包裹排序
考虑第 (i) 个供应商，再考虑当前箱子 (j) 可以容纳到第 (L) 个包裹，下一个容量更大的箱子 (j + 1) 可以容纳到第 (R) 个包裹，那么对答案的贡献为
其中式子的第二部分可以用前缀和处理
由于 (sumlimits_{i = 1}^{m}b_{i}leq 10^5)，因此总的时间复杂度为 (O((m + n)logn + mlogm))
注意运算涉及到取最小值，所以中间不要取模，用 long long 存储即可
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long LL;
const int MOD = 1e9 + 7;
class Solution {
public:
int minWastedSpace(vector<int>& p, vector<vector<int>> &b) {
int n = p.size();
vector<LL> s(n + 1, 0);
for (int i = 1; i <= n; ++i) s[i] = p[i - 1] + s[i - 1];
sort(p.begin(), p.end());
LL ans = INF;
for (auto &i: b) {
sort(i.begin(), i.end());
int m = i.size(), L = 0, R = 0;
LL temp = 0;
for (int j = 0; j < m; ++j) {
R = upper_bound(p.begin(), p.end(), i[j]) - p.begin();
if (R == 0) continue;
temp += 1LL * (R - L) * i[j] - (s[R] - s[L]);
L = R;
}
if (R == n) ans = min(ans, temp);
}
return ans == INF ? -1 : ans % MOD;
}
};