题解 | #牛客周赛 Round 131#

link

A

。

#include "bits/stdc++.h"

using namespace std;

int main() {
    char c;
    cin >> c;
    if (c == 'A') {
        cout << "red\n";
    } else if (c == 'B') {
        cout << "orange\n";
    } else if (c == 'C') {
        cout << "blue\n";
    } else {
        cout << "green\n";
    }

    return 0;
}

B

不可以存在孤立的 。

。

#include "bits/stdc++.h"

using namespace std;

void solve() {
    string s;
    int n;
    cin >> n >> s;
    s = "0" + s + "0";
    for (int i = 0; i + 2 < n + 2; i++) {
        if (s.substr(i, 3) == "010") {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C

贪心。

。

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    int s = 0, t = 0;
    while (s < n && t < m) {
        if (a[s] >= b[t]) {
            s++, t++;
        } else {
            s++;
        }
    }
    if (t < m) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

D

dp。

。

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> dp(n + 2);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int b = max(dp[a[i] - 1], dp[a[i] + 1]) + 1;
        dp[a[i]] = max(dp[a[i]], b);
        ans = max(ans, dp[a[i]]);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

E

做 次操作后，总糖数为 ，若令 盒子最多，每次操作都把新糖放入 中，对于 ，最多能执行操作数为左侧最大操作数加右侧最大操作数，同时还受最终糖数影响。

最终糖 ≤ S − k
→ a[j] + k ≤ S − k
→ k ≤ (S − a[j]) / 2

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 2);
    i64 sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    vector<i64> pre(n + 2), suf(n + 2);
    int r = a[1];
    i64 op = 0;
    for (int i = 1; i < n; i++) {
        int x = min(r, a[i + 1]);
        op += x;
        pre[i + 1] = op;
        r = a[i + 1] - x;
    }
    r = a[n], op = 0;
    for (int i = n - 1; i > 0; i--) {
        int x = min(r, a[i]);
        op += x;
        suf[i] = op;
        r = a[i] - x;
    }
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        i64 k = min(pre[i - 1] + suf[i + 1], (sum - a[i]) / 2);
        ans = max(ans, a[i] + k);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;
constexpr int P = 998244353;
i64 power(i64 a, int b, int p = P) {
    i64 r = 1;
    for (; b > 0; b >>= 1, a = a * a % p) {
        if (b & 1) {
            r = r * a % p;
        }
    }
    return r;
}

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> id(n), st;
    int pid = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            st.push_back(i);
        } else {
            int j = st.back();
            st.pop_back();
            id[i] = id[j] = pid++;
        }
    }
    vector<vector<int>> g(pid);
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            int u = id[i], v = id[i + 1];
            if (u == v) {
                pid = -1;
                break;
            }
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    if (pid == -1) {
        cout << "0\n";
        return;
    }
    vector<int> col(pid, -1);
    int comp = 0;
    for (int i = 0; i < pid; i++) {
        if (col[i] != -1) {
            continue;
        }
        comp++;
        queue<int> q;
        q.push(i);
        col[i] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : g[u]) {
                if (col[v] == -1) {
                    col[v] = col[u] ^ 1;
                    q.push(v);
                } else if (col[v] == col[u]) {
                    cout << "0\n";
                    return;
                }
            }
        }
    }
    cout << power(2, comp) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}