活動(dòng)地址： 牛客春招刷題訓(xùn)練營(yíng) - 編程打卡活動(dòng)

簡(jiǎn)單題 【模板】隊(duì)列

std::queue 成員函數(shù)：
push(x) 將 x 加入隊(duì)尾。
pop() 彈出隊(duì)頭。
front() 獲得隊(duì)頭。
empty() 判斷隊(duì)列是否為空。
size() 獲得隊(duì)列大小。

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

中等題 【模板】循環(huán)隊(duì)列

需要自己實(shí)現(xiàn)一個(gè)隊(duì)列。
循環(huán)隊(duì)列的思想是用數(shù)組模擬隊(duì)列，當(dāng) 或 越界就對(duì) 取模。
需要開(kāi)大小 的數(shù)組 。
初始化頭尾 。
判空：。
判滿：。
入隊(duì)：。
出隊(duì)：。
隊(duì)頭：。

#include <bits/stdc++.h>
using namespace std;
struct Queue {
    vector<int> a;
    int front;
    int rear;
    int n;
    Queue(int n_) {
        front = 0;
        rear = 0;
        n = n_ + 1;
        a.resize(n + 1);
    }
    bool full() {
        return (rear + 1) % n == front;
    }
    bool empty() {
        return front == rear;
    }
    void push(int x) {
        if (full()) {
            cout << "full\n";
            return;
        }
        a[rear] = x;
        rear++;
        if(rear >= n) rear -= n;
    }
    void printfront() {
        if (empty()) {
            cout << "empty\n";
            return;
        }
        cout << a[front] << '\n';
    }
    void printpop() {
        if (empty()) {
            cout << "empty\n";
            return;
        }
        cout << a[front] << '\n';
        front++;
        if(front >= n) front -= n;
    }
};
int main() {
    int n, q;
    cin >> n >> q;
    Queue qu(n);
    while (q--) {
        string op;
        cin >> op;
        if (op == "push") {
            int x;
            cin >> x;
            qu.push(x);
        } else if (op == "front")qu.printfront();
        else if (op == "pop")qu.printpop();
    }
    return 0;
}

困難題 合并回文子串

哎我去今天的dp咋這么難
區(qū)間dp。
設(shè) 為 中截取 內(nèi)的子串和 中截取 內(nèi)的子串能否組合成回文串。
只含 個(gè)字符或 個(gè)字符的串一定是回文串。
否則，回文串一定是由既有的回文串左右兩邊添加相同的字符轉(zhuǎn)換來(lái)的。
現(xiàn)在能得出枚舉順序：。則 。
因?yàn)殚L(zhǎng)度長(zhǎng)的回文串一定要從長(zhǎng)度短的回文串轉(zhuǎn)移而來(lái)。
轉(zhuǎn)移方程：

1. 如果 則 。
2. 如果 則 。
3. 如果 則 。
4. 如果 則 。
5. 如果 則 。

答案是所有為 的 中， 的最大值。

#include <bits/stdc++.h>
using namespace std;
bool dp[52][52][52][52];
void solve() {
    memset(dp, 0, sizeof(dp));
    string a, b;
    cin >> a >> b;
    int an = a.length(), bn = b.length();
    int ans = 0;
    a = ' ' + a;
    b = ' ' + b;
    for (int len1 = 0; len1 <= an; len1++)
        for (int len2 = 0; len2 <= bn; len2++)
            for (int l1 = 1; l1 + len1 - 1 <= an; l1++)
                for (int l2 = 1; l2 + len2 - 1 <= bn; l2++) {
                    int r1 = l1 + len1 - 1, r2 = l2 + len2 - 1;
                    if (len1 + len2 <= 1)dp[l1][r1][l2][r2] = 1;
                    else {
                        if (a[l1] == a[r1])dp[l1][r1][l2][r2] |= dp[l1 + 1][r1 - 1][l2][r2];
                        if (a[l1] == b[r2])dp[l1][r1][l2][r2] |= dp[l1 + 1][r1][l2][r2 - 1];
                        if (b[l2] == a[r1])dp[l1][r1][l2][r2] |= dp[l1][r1 - 1][l2 + 1][r2];
                        if (b[l2] == b[r2])dp[l1][r1][l2][r2] |= dp[l1][r1][l2 + 1][r2 - 1];
                    }
                    if (dp[l1][r1][l2][r2])ans = max(ans, len1 + len2);
                }
    cout << ans << '\n';
}
int main() {
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}