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

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

简单题 a的翻转

可以用 stoi() 函数计算字符串对应的整数值。
分别计算原字符串对应的整数，和反转后的字符串对应的整数，然后相加输出答案。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    string b = s;
    reverse(b.begin(), b.end());
    cout << stoi(s) + stoi(b);
    return 0;
}

中等题 斐波那契数列

和昨天跳台阶完全相同的做法。
直接偷懒贴代码来了

#include <iostream>
using namespace std;
int fib(int number) {
    if (number <= 2)return 1;
    int a1 = 1, a2 = 1, a3;
    for (int i = 1; i <= number - 2; i++) {
        a3 = a1 + a2;
        a1 = a2;
        a2 = a3;
    }
    return a3;
}
int main() {
    int n;
    cin >> n;
    cout << jumpFloor(n);
    return 0;
}

困难题 括号区间匹配

区间dp。
设 为 这个区间形成括号匹配的字符串最少需要添加的字符数。
首先枚举长度为 的区间， 固定为 。
然后枚举长度为 的区间，如果这个区间是匹配的括号， 值为 ，否则为 。
然后长度从 开始枚举到 ，记枚举到的左右端点分别为 ，当 可以和 匹配时，，否则 。
最后是区间dp常用套路：枚举断点 从 到 ，。

#include <bits/stdc++.h>
using namespace std;
int dp[102][102];
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] = n;
    for (int i = 1; i <= n; i++)dp[i][i] = 1;
    for (int i = 1; i + 1 <= n; i++)
        if ((s[i] == '(' && s[i + 1] == ')') || (s[i] == '[' && s[i + 1] == ']'))
            dp[i][i + 1] = 0;
        else
            dp[i][i + 1] = 2;    
    for (int len = 3; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']'))
                dp[l][r] = dp[l + 1][r - 1];
            else
                dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 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;
}