Hycode

Announcement

欢迎来到我的博客！这里分享我的个人生活与学习日常！

Learn More

标签

Hycode

Announcement

欢迎来到我的博客！这里分享我的个人生活与学习日常！

Learn More

标签

Codeforces Div.3 Div.4 牛客牛客周赛青鸟工作室

Hycode

Announcement

欢迎来到我的博客！这里分享我的个人生活与学习日常！

Learn More

标签

Codeforces Div.3 Div.4 牛客牛客周赛青鸟工作室

842 字

2 分钟

牛客周赛 Round 131

2026-02-16

题解

牛客

/

牛客周赛

☁️体验#

My First AK! 但是vp

💡题解#

A - ICPC Balloons#

题意#

给出一个大写字符 $c∈\{‘A’,‘B’,‘C’,‘D’\}$ ，表示通过题目的题号。要求输出相应的气球颜色 $s∈\{‘red’,‘orange’,‘blue’,‘green’\}$ 。

思路#

按题意模拟即可。

代码#

1
void solve()
2
{
3
    vector<string> s = {"red","orange","blue","green"};
4
    char c;
5
    cin >> c;
6
    D(s[c - 'A']);
7
}

B - String Covering#

题意#

你有一个长度为 $n$ 的初始全 $0$ 的 $01$ 字符串，你可以执行任意次操作：

选择两个相邻的位置，将这两个位置都变成 $1$ 。

判断能否通过操作将这个字符串变成长度同样为 $n$ 的目标字符串 $s$ 。

思路#

显然，我们可以创造的最短连续全 $1$ 子串长度为 $2$ ，如果 $s$ 中有长度为 $1$ 的全 $1$ 子串，那必定无法完成。

因此，遍历统计每个连续全 $1$ 子串长度，在这个过程中进行判断即可。

代码#

1
void solve()
2
{
3
    int n;
4
    cin >> n;
5

6
    string s;
7
    cin >> s;
8

9
    s += '0';
10
    int t = 0;
11
    for(int i = 0; i <= n; i++)
12
        if(s[i] == '1') t++;
13
        else if(t == 1)
14
        {
15
            NO;
16
            return;
17
        }
18
        else t = 0;
19
    YES;
20
}

C - Get The Sequence#

题意#

你有一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ ，和一个长度为 $m$ 的序列 $b_1,b_2,…,b_m$ ，每个元素都是正整数。

你可以执行任意次操作：

删除 $a$ 中 $1$ 个元素
将 $a$ 中的 $1$ 个元素大小减少 $1$

判断是否可以通过操作将 $a$ 变成 $b$ 。

思路#

很明显，如果每个 $b_i$ 的对应位置上都有一个大于等于它的 $a_i$ 就行了。

双指针模拟即可。

代码#

1
void solve()
2
{
3
    int n, m;
4
    cin >> n >> m;
5

6
    vector<int> a(n), b(m);
7
    vcin(a);
8
    vcin(b);
9

10
    int l = 0, r = 0;
11
    while(l < n && r < m)
12
    {
13
        while(l < n && a[l] < b[r]) l++;
14
        if(l == n) break;
15
        l++, r++;
16
    }
17

18
    if(r == m) YES;
19
    else NO;
20
}

D - Longest Subsequence#

题意#

你有一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ ，从中选出一个子序列，使得选出的子序列中任意相邻两个元素的差的绝对值恰好为 $1$ 。

问最长子序列的长度是多少？

思路#

简单 $DP$ 简单做。

用 $f_i$ 表示以 $i$ 结尾的最长子序列的长度，那么我们容易得出以下关系：

$f_i = \max(f_{i - 1}, f_{i + 1}) + 1$

代码#

1
void solve()
2
{
3
    input(n, a);
4

5
    int ans = 0;
6
    unordered_map<int, int> f;
7

8
    for(int& i : a)
9
    {
10
        f[i] = max(f[i - 1], f[i + 1]) + 1;
11
        ans = max(ans, f[i]);
12
    }
13

14
    D(ans);
15
}

E - Eat The Candy#

题意#

你有 $n$ 个盒子，盒子里糖果的数量分别是 $a_1,a_2,…,a_n$ 。

你可以执行任意次操作：

选择相邻的两个盒子，各吃掉 $1$ 颗糖，然后得到 $1$ 颗新糖，并选择任意一个盒子放入

问最后糖最多的盒子里面有多少糖？

思路#

显然，选择 $a_i$ 为不动的盒子，把前面和后面的盒子的贡献全部加到 $a_i$ 里面，这种做法是最优的。

计算前缀贡献和以及后缀贡献和，然后遍历每个位置更新答案最大值即可。

代码#

1
void solve()
2
{
3
    input(n, a);
4

5
    if(n == 1)
6
    {
7
        D(a[0]);
8
        return;
9
    }
10

11
    vector<int> pre(n), suf(n), t = a;
12
    for(int i = 1; i < n; i++)
13
    {
14
        int d = min(t[i - 1], t[i]);
15
        pre[i] = pre[i - 1] + d;
16
        t[i] -= d;
17
    }
18

19
    t = a;
20
    for(int i = n - 2; i >= 0; i--)
21
    {
22
        int d = min(t[i], t[i + 1]);
23
        suf[i] = suf[i + 1] + d;
24
        t[i] -= d;
25
    }
26

27
    int ans = 0;
28
    for(int i = 0; i < n; i++)
29
        ans = max(ans, pre[max(i - 1, 0LL)] + a[i] + suf[min(i + 1, n - 1)]);
30
    D(ans);
31
}

F - Bracket Coloring#

题意#

给你一个长度为 $n$ 、仅由字符 $‘(’$ 和 $‘)’$ 组成的括号序列 $s$ ，且保证这是一个合法括号序列。

现在你要给每个括号染上红色或蓝色，但需要满足以下条件：

每一对相互匹配的括号必须染上相同的颜色
若序列中两个相邻位置的括号字符相同，则它们的颜色不能相同。

问有多少种不同的染色方案，对 $998 244 353$ 取模后输出。

思路#

给每对括号编号，如果相邻两个位置颜色不能相同，那么就把这两个编号连一条边，最后对于每一个连通分量，都是一个二分图染色问题。

设连通分量的个数为 $k$ 。

那么，最后答案就是 $2 ^ k \mod 998 244 353$ 。

代码#

1
void solve()
2
{
3
    int n;
4
    cin >> n;
5

6
    string s;
7
    cin >> s;
8

9
    stack<int> stk;
10
    vector<int> f(n);
11
    int id = 0;
12
    for(int i = 0; i < n; i++)
13
        if(s[i] == '(') stk.push(i);
14
        else
15
        {
16
            f[stk.top()] = f[i] = ++id;
17
            stk.pop();
18
        }
19

20
    DSU d(id);
21
    for(int i = 1; i < n; i++)
22
        if(s[i - 1] == s[i])
23
            d.merge(f[i - 1], f[i]);
24

25
    int ans = qpow(2, d.countKunion(1), mod);
26
    D(ans);
27
}

🎈模板#

快速幂#

1
int qpow(int a, int b, int m) {
2
    int res = 1;
3
    for ( ; b; b /= 2, a = a * a % m)
4
        if (b % 2)
5
            res = res * a % m;
6
    return res;
7
}

并查集#

1
struct DSU {
2
    vector<int> f, siz;
3
    int n;
4

5
    DSU() {}
6
    DSU(int _n) {
7
        n = _n;
8
        init(n);
9
    }
10

11
    void init(int n) {
12
        f.resize(n + 1);
13
        iota(f.begin(), f.end(), 0);
14
        siz.assign(n + 1, 1);
15
    }
16

17
    int find(int x) {
18
        return f[x] == x ? x : f[x] = find(f[x]);
19
    }
20

21
    void merge(int x, int y) {
22
        x = find(x), y = find(y);
23
        if (x == y)
24
            return;
25
        f[y] = x;
26
        siz[x] += siz[y];
27
    }
28

29
    bool same(int x, int y) {
30
        return find(x) == find(y);
31
    }
32

33
    int size(int x) {
34
        return siz[find(x)];
35
    }
36

37
    int countKunion(int k) {
38
        int res = 0;
39
        for (int i = 1; i <= n; i++)
40
            if (find(i) == i && siz[i] >= k)
41
                res++;
42
        return res;
43
    }
44
};

头文件#

1
#include <bits/stdc++.h>
2
#define vvcin(_x) for(auto& _e : _x) for(auto& _i : _e) cin >> _i
3
#define vcin(_x) for(auto& _i : _x) cin >> _i
4
#define input(_T, _n, _a) int _n; cin >> _n; vector<_T> _a(_n); vcin(_a)
5
#define D(_x) cout << _x << endl
6
#define vD(_x) for(int _i = 0; _i < _x.size(); ++_i) cout << (_x[_i]) << " \n"[_i == _x.size() - 1]
7
#define vvD(_x) for(auto& _e : _x) vD(_e)
8
#define vcin1(_x) for(int _i = 1; _i < _x.size(); ++_i) cin >> _x[_i]
9
#define input1(_T, _n, _a) int _n; cin >> _n; vector<_T> _a(_n + 1); vcin1(_a)
10
#define D1(_x) cout << "# " << _x << endl
11
#define vD1(_x) for(int _i = 1; _i < _x.size(); ++_i) cout << (_x[_i]) << " \n"[_i == _x.size() - 1]
12
#define YES cout << "YES" << endl
13
#define NO cout << "NO" << endl
14
#define Yes cout << "Yes" << endl
15
#define No cout << "No" << endl
16
#define yes cout << "yes" << endl
17
#define no cout << "no" << endl
18
#define all(_x) _x.begin(), _x.end()
19
#define rall(_x) _x.rbegin(), _x.rend()
20
#define INF LLONG_MAX
21
#define inf INT_MAX
22
#define endl '\n'
23
#define int long long
24
using namespace std;
25
typedef long long ll;
26
constexpr int MOD = 1000000007;
27
constexpr int mod = 998244353;
28

29
void solve()
30
{
31

32
}
33

34
signed main()
35
{
36
    ios::sync_with_stdio(false);
37
    cin.tie(nullptr);
38
    int _ = 1;
39
cin >> _;
40
    while (_--)
41
        solve();
42
    return 0;
43
}

如果这篇文章对你有帮助，欢迎分享给更多人！

牛客周赛 Round 131

https://blog.hycode.qzz.io/posts/nk-weekly-131/post/

作者

Hycode

发布于

2026-02-16

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

牛客周赛 Round 134

牛客周赛 Round 128

PERSISTENCE

☁️体验#

💡题解#

A - ICPC Balloons#

题意#

思路#

代码#

B - String Covering#

题意#

思路#

代码#

C - Get The Sequence#

题意#

思路#

代码#

D - Longest Subsequence#

题意#

思路#

代码#

E - Eat The Candy#

题意#

思路#

代码#

F - Bracket Coloring#

题意#

思路#

代码#

🎈模板#

快速幂#

并查集#

头文件#

目录