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

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

简单题 【模板】队列

std::queue 成员函数：
push(x) 将 x 加入队尾。
pop() 弹出队头。
front() 获得队头。
empty() 判断队列是否为空。
size() 获得队列大小。

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

中等题 【模板】循环队列

需要自己实现一个队列。
循环队列的思想是用数组模拟队列，当 或 越界就对 取模。
需要开大小 的数组 。
初始化头尾 。
判空：。
判满：。
入队：。
出队：。
队头：。

#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咋这么难
区间dp。
设 为 中截取 内的子串和 中截取 内的子串能否组合成回文串。
只含 个字符或 个字符的串一定是回文串。
否则，回文串一定是由既有的回文串左右两边添加相同的字符转换来的。
现在能得出枚举顺序：。则 。
因为长度长的回文串一定要从长度短的回文串转移而来。
转移方程：

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