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

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

简单题 小红浏览论坛

该题需要一点码量。
字符串 为 的反转。
如果 字符串里存在 pqdb，需要将这些字符替换成轴对称后的字符。
如果 字符串存在 ilmnouvwx，不变。
否则不轴对称，可以替换成 #。
然后判断 和 是否相等。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    string s;
    cin >> s;
    string t(s.rbegin(), s.rend());
    bool ok = true;
    string u = "ilmnouvwx";
    for (int i = 0; i < t.length(); i++) {
        if (t[i] == 'p')t[i] = 'q';
        else if (t[i] == 'q')t[i] = 'p';
        else if (t[i] == 'b')t[i] = 'd';
        else if (t[i] == 'd')t[i] = 'b';
        else if (!count(u.begin(), u.end(), t[i]))
            t[i] = '#';
    }
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != t[i]) {
            ok = false;
        }
    }
    cout << (ok ? "Yes\n" : "No\n");
}
int main() {
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}

中等题 Y型树

不是……这题咋这么难……
发现答案有一个神奇公式： 。
好，看不懂（

print(((int(input()) - 1) ** 2 + 3) // 12 % 1000000007)

困难题 【模板】二分

二分模板题，可以直接用 STL 的 lower_bound 函数和 upper_bound 函数。
这两个函数都需传入 开区间，查找到满足条件的数则返回对应的指针或迭代器，查找不存在则返回 对应的指针或迭代器。
如果传入的是 C 风格数组，则会返回指针；如果传入 STL 容器，则会返回迭代器，二者用法相似。
对于 和 ，如果返回了 则说明指针位置不合法，输出 ；否则输出指针对应的数。
对于 和 ，需要将指针位置减 ，如果返回了 则说明指针位置不合法，输出 ；否则输出指针减 对应的数。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    while (q--) {
        int op, l, r, x;
        cin >> op >> l >> r >> x;
        if (op == 1) {
            auto it = lower_bound(a.begin() + l, a.begin() + r, x);
            if (it == a.begin() + r)cout << -1 << '\n';
            else cout << *it << '\n';
        }
        if (op == 2) {
            auto it = upper_bound(a.begin() + l, a.begin() + r, x);
            if (it == a.begin() + r)cout << -1 << '\n';
            else cout << *it << '\n';
        }
        if (op == 3) {
            auto it = lower_bound(a.begin() + l, a.begin() + r, x);
            if (it == a.begin() + l)cout << -1 << '\n';
            else cout << *(it - 1) << '\n';
        }
        if (op == 4) {
            auto it = upper_bound(a.begin() + l, a.begin() + r, x);
            if (it == a.begin() + l)cout << -1 << '\n';
            else cout << *(it - 1) << '\n';
        }
    }
    return 0;
}