代码随想录知识星球 双十二特别优惠活动进行中🔥🔥
上周在卡码网举办了 小米 24年笔试周赛。
如果大家想去小米的话，至少要过笔试吧，来看看小米的笔试难度。
坦白来说，小米这次笔试难度有点大了。
以下是 卡码网（https://kamacoder.com/）周赛（小米24年春季笔试真题）
题解为C++代码实现，其他语言版本可以看卡码网（https://kamacoder.com/）对应题目的评论区：
偏爱的字符
题目链接：https://kamacoder.com/problempage.php?pid=1269
思路分析：dp + 前后缀分解
第一步：令prefix[i]表示下标为i个字符前面离i最近的偏爱字符的位置（不包括下标为i的字符本身），我们从下标1开始遍历字符串。
如果前一个（下标为i-1）字符是偏爱字符，那么令prefix[i]为i-1，如果不是，那么令prefix[i]=prefix[i-1]。初始时，令prefix[0] = -1；因为下标为0的字符前面没有任何字符。
第二步：随后再倒序遍历整个字符串，用suffix记录第i个字符后面的离i最近的偏爱字符。转移公式如上面所述。
第三步：因为题目保证字符串中一定会出现偏爱字符，所以随后我们遍历每一个下标，如果这个字符本身就是偏爱字符，那么直接continue，如果不是，那么就看prefix[i]和suffix[i]谁离得更近。注意：如果prefix[i]或suffix[i]有一个是负数的话，那么说明，他的前面（后面）没有偏爱字符，而他本身又不是偏爱字符的话（因为它本身是偏爱字符的话，直接continue了），那么说明偏爱字符一定在另外一边。
第二步和第三步可以一起执行。
复杂度分析：
时间复杂度：O(n), 共需要扫描两遍字符串。 空间复杂度：O(n), 需要用前缀数组存储每个字符前面的偏爱字符。
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int N = 10005, mod = 1000000007;
using ll = long long;
using pil = pair<int, ll>;
using pii = pair<int, int>;
int t, ans = 0;
int main() {
int n, m;
char c;
cin >> n >> m;
// 用来记录偏爱字符，如果为true表示这一位是偏爱的字符
bool loves[128]{};
// 读取偏爱的字符
for (int i = 0; i < m; ++i) {
cin >> c;
loves[c] = 1;
}
// 读取字符串
string s;
cin >> s;
// 记录每一个字符的前面最近的偏爱字符在哪个位置
int *prefix = new int[n];
prefix[0] = -1;
for (int i = 1; i < n; ++i) {
if (loves[s[i - 1]]) prefix[i] = i - 1;
else prefix[i] = prefix[i - 1];
}
// 记录每个字符后面最近的偏爱字符的位置，并同时替换偏爱字符
int suffix = -1;
for (int i = n - 1; i >= 0; --i) {
if (loves[s[i]]) {
suffix = i;
continue;
}
// 如果前面没有偏爱字符，那么一定在后面
if (prefix[i] < 0) s[i] = s[suffix];
// 如果后面没有偏爱字符，那么一定在前面
else if (suffix < 0) s[i] = s[prefix[i]];
// 如果两边都有偏爱的字符，那么选择最近的替换，两个一样近就选择左边的
else {
int dt = i - prefix[i] - (suffix - i);
// 距离的差值为小于等于0的数就表示左边的符合题目的条件，用左边的替换
if (dt <= 0) s[i] = s[prefix[i]];
else s[i] = s[suffix];
}
}
cout << s << endl;
return 0;
}
小明打砖块
题目链接：https://kamacoder.com/problempage.php?pid=1270
思路分析：区间DP
状态定义：令dp[i][j]表示区间[i:j]全部消除能获得的最大的得分。
状态个数：设区间为[i:j]。
1、我们可以将左右区间端点进行单消, 这样得分变成了a+[i+1:j]或a+[i:j-1];
2、如果区间左右端点的颜色是一样的，那么我们可以把区间分成两个部分，即[i+1:j-1]和i，j两个点，我们的得分是[i+1:j-1]+b,即双消的得分;
3、 最后, 如果区间中有砖块与左右端点的颜色一致的话(假设这个位置是k), 那么可以选择三消, 即把区间分为[i+1:k-1]和[k+1:j-1]两个部分，得分为[i+1:k-1]+[k+1:j-1]+c；
就是说如果把这两个区间的内容全部消除完了，那么剩下来的i,j,k三个点的砖块就连在一起了，并且他们的颜色是一样的。
4、对于一个区间来说， 我们也可以选择任何一个点为中间点(同样设这个点是k)， 将这个区间分为两个部分， 即分为独立的区间， 即把区间分为[i:k]和[k+1:j], 得分就是两者相加。
为什么要这样划分？假设我们的序列为[a,b,c,d,e,f,g], 我们最优的划分是将区间分为[a,b,c,d]和[e,f,g]。即先消除前面四个，再消除后面三个，这里并不是单独消除，而是作为整体消除。
也就是说把前面的四个元素组成的区间当做一个子问题来消除获得最大的得分。
如果只有上述三种情况是没法处理这种情况的。所以需要把大区间分成两个可能得小区间来进行消除。
状态转移：设x, y, z, w分别为上述四种情况的得分。a,b,c分别为一二三消除的得分
x = max(dp[i][j-1], dp[i+1][j]) + a y = dp[i+1][j-1] + b if nums[i]==nums[j] else 0 z = dp[i+1][k-1] + dp[k+1][j-1] + c if nums[i]==nums[j]==nums[k] else 0 w = dp[i][k] + dp[k+1][j] dp[i][j] = max(x, y, z, w)
复杂度分析：
时间复杂度：O(n^3), 共有n^2个状态，每个状态的转移时间为O(n), 整体时间复杂度为O(n^3) 空间复杂度: O(n^2), 取决于dp数组的空间。
C++代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 10005, mod = 1000000007;
using ll = long long;
using pil = pair<int, ll>;
using pii = pair<int, int>;
int t, ans = 0;
int main() {
int n, a, b, c;
cin >> n >> a >> b >> c;
int *nums = new int[n]{};
// 读取砖块的颜色
for (int i = 0; i < n; ++i) cin >> nums[i];
vector<vector<int>> dp(n, vector<int> (n, 0));
// 枚举区间的左端点
for (int i = n - 1; i >= 0; --i) {
dp[i][i] = a;
// 枚举区间的右端点
for (int j = i + 1; j < n; ++j) {
// 单独消除这一块
int r = max(dp[i + 1][j], dp[i][j - 1]) + a;
// 将区间从这里划分成两块进行单独的消除
for (int k = i + 1; k < j; ++k) {
r = max(r, dp[i][k] + dp[k + 1][j]);
}
// 如果区间的左右端点颜色相同，可以把中间的全部消掉，再合并左右端点
if (nums[i] == nums[j]) {
// 两块一起消除
r = max(r, dp[i + 1][j - 1] + b);
// 如果区间中有一块砖块与左右端点的颜色相同，则把区间分为：
// [i, k-1],[k+1,j]以及左右端点和中间这个相同颜色的砖块
for (int k = i + 1; k < j; ++k) {
// 计算三消的得分
if (nums[i] == nums[k]) {
r = max(r, dp[i + 1][k - 1] + dp[k + 1][j - 1] + c);
}
}
}
dp[i][j] = r;
}
}
cout << dp[0][n - 1] << endl;
return 0;
}
---------------------------------
代码随想录知识星球 双十二特别优惠活动🔥🔥
星球置顶一，硬核资料可以让大家少走很多弯路：
