活動地址： ?？痛赫兴㈩}訓練營 - 編程打卡活動

簡單題 【模板】棧

C++ #include <stack> 后可使用 STL 中的 std::stack。
成員函數(shù)：
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;
}

中等題 點擊消除

字符串也可以做類似于棧的操作。
成員函數(shù)：
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;
}

困難題 小紅取數(shù)

動態(tài)規(guī)劃。
設計狀態(tài)： 只從前 個數(shù)中取，取數(shù)之和除以 的余數(shù)為 時的最大可能和。
還需要 記錄只從前 個數(shù)中取是否有任意一種取數(shù)之和除以 的余數(shù)為 。
當 時，轉移方程： 。
答案為 。
發(fā)現(xiàn) 只會從 轉移而來，可以降一個維度，只從兩個一維 數(shù)組間轉移。

#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;
}