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

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

简单题 【模板】栈

C++ #include <stack> 后可使用 STL 中的 std::stack。
成员函数：
size() 获得大小
empty() 判栈是否为空
push(x) 向栈顶插入x
top() 获取栈顶元素
pop() 弹出栈顶元素

#include <bits/stdc++.h>
using namespace std;
int main() {
    int q;
    cin >> q;
    stack<int> stk;
    while (q--) {
        string op;
        cin >> op;
        if (op == "push") {
            int x;
            cin >> x;
            stk.push(x);
        }
        if (op == "pop") {
            if (stk.empty())
                cout << "error\n";
            else {
                cout << stk.top() << '\n';
                stk.pop();
            }
        }
        if (op == "top") {
            if (stk.empty())
                cout << "error\n";
            else
                cout << stk.top() << '\n';
        }
    }
    return 0;
}

中等题 点击消除

字符串也可以做类似于栈的操作。
成员函数：
pop_back() 弹出字符串最后一个字符。
back() 获得字符串最后一个字符。
将答案字符串视作一个栈。
遍历字符串 ，如果 和栈顶元素相同，则弹出栈顶；否则将 压入栈。
最后输出栈中所有元素。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    string ans;
    cin >> s;
    for (auto it : s) {
        if (ans.empty() || ans.back() != it)
            ans += it;
        else ans.pop_back();
    }
    if (ans.empty())ans = "0";
    cout << ans << '\n';
    return 0;
}

困难题 小红取数

动态规划。
设计状态： 只从前 个数中取，取数之和除以 的余数为 时的最大可能和。
还需要 记录只从前 个数中取是否有任意一种取数之和除以 的余数为 。
当 时，转移方程： 。
答案为 。
发现 只会从 转移而来，可以降一个维度，只从两个一维 数组间转移。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> dp(k), dp2(k), a(n);
    vector<bool> vis(k), vis2(k);
    for (int i = 0; i < n; i++)cin >> a[i];
    vis[0] = 1;
    for (int i = 0; i < n; i++) {
        dp2 = dp;
        vis2 = vis;
        for (int j = 0; j < k; j++) {
            if (vis[j]) {
                dp2[(a[i] + j) % k] = max(dp2[(a[i] + j) % k], dp[j] + a[i]);
                vis2[(a[i] + j) % k] = 1;
            }
        }
        dp = dp2;
        vis = vis2;
    }
    if (dp[0] == 0)cout << -1 << '\n';
    else cout << dp[0] << '\n';
    return 0;
}