牛客春招刷题训练营-2025.4.24题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 ranko的手表

直接根据原串填充问号较困难，考虑枚举 时间点，去检查枚举的时间点对应的时间字符串是否和输入的字符串匹配。

#include <bits/stdc++.h>
using namespace std;
string to_time_string(int t) {
    string ans;
    ans += (t / 600) + '0';
    t %= 600;
    ans += (t / 60) + '0';
    t %= 60;
    ans += ':';
    ans += (t / 10) + '0';
    t %= 10;
    ans += t + '0';
    return ans;
}
bool check(string& s, string& t) {
    for (int i = 0; i < 5; i++)
        if (t[i] != '?' && s[i] != t[i])
            return false;
    return true;
}
int main() {
    string t1, t2;
    cin >> t1 >> t2;
    int minans = 1e9, maxans = 0;
    for (int i = 0; i < 24 * 60; i++)
        for (int j = i + 1; j < 24 * 60; j++) {
            string timei = to_time_string(i);
            string timej = to_time_string(j);
            if (check(timei, t1) && check(timej, t2)) {
                minans = min(minans, j - i);
                maxans = max(maxans, j - i);
            }
        }
    cout << minans << ' ' << maxans << '\n';
    return 0;
}

中等题 跳台阶

观察得到这是斐波那契数列，使用递推求解。
因为每一步递推是 ，所以只需要 个 int 类型变量的空间。
使用 存储 ，每一步递推计算完成后 。

class Solution {
  public:
    int jumpFloor(int number) {
        if (number <= 1)return 1;
        int a1 = 1, a2 = 1, a3;
        for (int i = 1; i <= number - 1; i++) {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }
};

困难题 [CQOI2007]涂色PAINT

区间dp。
从短区间枚举到长区间。
表示将 内需要染色多少次。

1. 如果 则 。
2. 如果 ，那么 能从 左端点向左扩展一格涂来，或者从 右端点向右扩展一格涂来，换句话说这种扩展可以涂 这一层底色来少涂一次。转移方程：。
3. 否则不能直接涂 这一层底色，那可以枚举区间断点 ， 内的涂色可以分解为 和 ，转移方程：。

答案为 。

#include <bits/stdc++.h>
using namespace std;
int dp[52][52];
int main() {
    string s;
    cin >> s;
    int n = s.length();
    s = ' ' + s;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = 1e9;
    for (int i = 1; i <= n; i++)dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            if (s[l] == s[r])
                dp[l][r] = min({dp[l][r], dp[l + 1][r], dp[l][r - 1]});
            for (int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
        }
    }
    cout << dp[1][n];
    return 0;
}