牛客周赛 Round 2

小红的环形字符串小红的环形字符串

题目描述
小红拿到了一个环形字符串s。所谓环形字符串，指首尾相接的字符串。
小红想顺时针截取其中一段连续子串正好等于t，一共有多少种截法？

思路分析

环形问题。

• 将字符串 s 拼接自身，得到新的字符串 tem，用于处理环形问题

时间复杂度

O(n * m)

代码

#include <iostream>
#include <string>
using namespace std;int main() {string s, t;cin >> s >> t;int n = s.length(), m = t.length();string tem = s + s;int cnt = 0;for (int i = 0; i < n; i++) {if (tem.substr(i, m) == t) {cnt++;}}cout << cnt << endl;return 0;
}

相邻不同数字的标记

题目描述
小红拿到了一个数组，每个数字被染成了红色或蓝色。
小红有很多次操作，每次操作可以选择两个相邻的不同颜色的数字标记，并获得它们数字之和的得分。已经被标记的数字无法再次标记。
小红想知道，自己最多能获得多少分。

思路分析

使用动态规划来解决该问题。定义一个数组 dp，其中 dp[i] 表示在第 i 个位置时，小红能够获得的最高得分。

• 如果数组中第 i 和 i-1 个数字颜色相同，则不能进行标记操作，此时 dp[i] = dp[i-1]。
• 如果数组中第 i 和 i-1 个数字颜色不同，则小红可以选择标记这两个数字，并获得它们的和作为得分。此时 dp[i] = dp[i-2] + a[i-1] + a[i]。

时间复杂度

O(n)

代码

#include <iostream>
using namespace std;
long long a[100005], dp[100005];
char b[100005];
int main() {int n;cin >> n;long long ans=0;for (int i = 1; i <= n; i++)cin >> a[i];cin >> b + 1;for (int i = 2; i <= n; i++) {if (b[i] == b[i-1])dp[i] = dp[i-1];elsedp[i] = max(dp[i-1],dp[i-2]+a[i-1]+a[i]);}cout << dp[n] << endl;return 0;
}

小红的俄罗斯方块

思路分析

模拟+找规律

时间复杂度

O(n）

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n;cin >> n;vector<int> cols(9, 0);for (int i = 0; i < n; i++) {int a, b;cin >> a >> b;if (a == 0) {int low = max(cols[b], cols[b + 1]);cols[b] = low + 3;cols[b + 1] = low + 1;} else if (a == 90) {int t2 = max(cols[b + 1], cols[b + 2]);if (t2 >= cols[b] + 1) {cols[b] = t2 + 1;cols[b + 1] = t2 + 1;cols[b + 2] = t2 + 1;} else {t2 = cols[b];cols[b] = t2 + 2;cols[b + 1] = t2 + 2;cols[b + 2] = t2 + 2;}} else if (a == 180) {if (cols[b] >= cols[b + 1] + 2) {int low = cols[b];cols[b] = low + 1;cols[b + 1] = low + 1;} else {int low = cols[b + 1];cols[b] = low + 3;cols[b + 1] = low + 3;}} else if (a == 270) {int low = max({cols[b], cols[b + 1], cols[b + 2]});cols[b] = low + 1;cols[b + 1] = low + 1;cols[b + 2] = low + 2;}}string res = "";for (int i = 1; i < 9; i++) {res += to_string(cols[i]) + " ";}cout << res << endl;return 0;
}