Hycode

Announcement

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

Learn More

标签

Hycode

Announcement

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

Learn More

标签

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

Hycode

Announcement

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

Learn More

标签

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

797 字

2 分钟

牛客周赛 Round 134

2026-03-09

题解

牛客

/

牛客周赛

☁️体验#

E 感觉难度偏低了。赛时 5 题。

💡题解#

A - Nowcoder Weekly Contest#

题意#

给出一个 $Rating$ ，判断是否参与牛客周赛的评级。根据规则，大于 $1599$ 就会 $Unrated$ 。

思路#

直接判断即可。

代码#

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

6
    if(n >= 1600) D("Unrated");
7
    else D("Rated");
8
}

B - ICPC Medal#

题意#

给出金银铜牌数量，分别为 $a, b, c$ 。

$x$ 个铜牌可以合成 $1$ 个银牌， $y$ 个银牌可以合成 $1$ 个金牌。其中，每合成 $1$ 个金牌时都会掉落 $1$ 个铜牌。

问最多可以有多少个金牌。

思路#

按题意模拟即可。

代码#

1
void solve()
2
{
3
    int a, b, c, x, y;
4
    cin >> a >> b >> c >> x >> y;
5

6
    while(c >= x || b >= y)
7
    {
8
        b += c / x;
9
        c %= x;
10
        a += b / y;
11
        c += b / y;
12
        b %= y;
13
    }
14

15
    D(a);
16
}

C - Unique Number#

题意#

给你一个初始化全 $0$ 长度为 $n$ 的数组。

你可以执行任意次操作：

选择一个右边界 $r$ ，将 $a_1, a_2, ... , a_r$ 全部增加 $1$ 。

另外，有一个同样长的限制数组 $d$ ，每个对应的 $a_i$ 都要满足 $a_i \leq d_i$ 。

问数组 $a$ 中最多可以有多少种不同的数。

思路#

很明显，构造出来的 $a$ 数组总是非递增的。

为了使后续能选的不同的数更多，左边的数应当尽可能大。所以， $a_1$ 我们直接取 $d_1$ 是最优的。

为了给后续的数尽可能留更多的选择，同时还要保证种数更多。理想情况下，我们希望构造出来的数组 $a$ 从左往右是依次减 $1$ 的。

因此，我们做一件事就好:

$能选多大选多大$

代码#

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

5
    int t = a[0], ans = 0;
6

7
    for(int& i : a)
8
    {
9
        t = min(t, i);
10
        ans++;
11
        t--;
12

13
        if(t < 0) break;
14
    }
15

16
    D(ans);
17
}

D - Balanced Array#

题意#

有一个长度为 $n$ 的数组 $a$ ，如果其子数组 $(l, r) = a_l, a_{l+1}, \dots, a_{r-1}, a_r$ 满足：

$\max(l, r) - \min(l, r) <= 1$

那么就称 $(l, r)$ 为平衡的。

问有多少个 $(l, r)$ 满足平衡条件。

思路#

对于子数组 $(l, r)$ ，如果一个右端点 $r$ 是合法的，那么不难推出 $(l, r), (l+1, r), \dots, (r-1, r), (r, r)$ 均是合法的。因此，只要找到合法区间，答案就直接加上当前区间长度。

所以，用一个 $map$ 动态维护滑动窗口即可。

代码#

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

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

8
    for(int r = 0; r < n; r++)
9
    {
10
        f[a[r]]++;
11

12
        while(f.rbegin()->first - f.begin()->first > 1)
13
        {
14
            int x = a[l++];
15
            if(--f[x] == 0) f.erase(x);
16
        }
17

18
        ans += r - l + 1;
19
    }
20

21
    D(ans);
22
}

E - Maximize The Sum#

题意#

有一个长度为 $n$ 的数组 $a1,a2,\dots,a_n$ ，其中每个元素是 $0$ 或 $1$ 。

你可以执行任意次操作：

选择相邻的三个位置，它们的值分别为 $x, y, z$ ；
然后将它们同时替换为：
- $x^{'} = x \oplus y$
- $y^{'} = y \oplus z$
- $z^{'} = x \oplus z$

问最后 $1$ 的数量最多可以有多少。

思路#

我们可以分出以下 $8$ 种情况：

$111 \rightarrow 000$
$011 \rightarrow 101$
$101 \rightarrow 110$
$110 \rightarrow 011$
$001 \rightarrow 011$
$100 \rightarrow 101$
$010 \rightarrow 110$
$000 \rightarrow 000$

显然，如果全为 ' $1$ ' 或 ' $0$ '，我们无法使数量增多，此时答案就是 $n$ 或 $0$ ；

更普遍的情况，对于任意排列的三元组，它们总是可以变成 $2$ 个 ' $1$ ' 和 $1$ 个 ' $0$ ' 的组合。此时答案为 $n - 1$ 。

代码#

1
void solve()
2
{
3
    int n;
4
    cin >> n;
5
    string s;
6
    cin >> s;
7

8
    int t = ranges::count(s, '1');
9

10
    if(t == n || t == 0) D(t);
11
    else D(n - 1);
12
}

F - Palindromic Value#

题意#

给你一个长度为 $n$ 的字符串 $s$ 。

每个回文子串的价值为其长度 $|t|$ 的平方。

把 $s$ 全部分割为回文子串，并记录方案价值 $\sum |t|^2$

求所有方案价值之和并取模 $\sum \sum |t| ^ 2 \mod 998244353$

思路#

$cnt$ 和 $dp$ 分别表示前缀 $s[1 \dots i]$ 的回文分割方案数和所有回文方案价值总和。

中心扩展法预处理回文串。

如果 $s[l \dots r]$ 是回文串，那么有：

$cnt[r] += cnt[l]$
$dp[i] += dp[j] + cnt[j] * (i - j)^2$

最后， $dp[n]$ 即为答案。

代码#

1
void solve()
2
{
3
    int n;
4
    cin >> n;
5
    string s;
6
    cin >> s;
7

8
    vector<vector<int>> ok(n + 1, vector<int>(n + 1));
9
    for(int i = 0; i < n; i++)
10
    {
11
        int l = i, r = i;
12
        while(l >= 0 && r < n && s[l] == s[r])
13
        {
14
            ok[l + 1][r + 1] = 1;
15
            l--, r++;
16
        }
17
        l = i, r = i + 1;
18
        while(l >= 0 && r < n && s[l] == s[r])
19
        {
20
            ok[l + 1][r + 1] = 1;
21
            l--, r++;
22
        }
23
    }
24

25
    vector<Z> cnt(n + 1), dp(n + 1);
26
    cnt[0] = 1;
27
    for(int i = 1; i <= n; i++)
28
        for(int j = 0; j < i; j++)
29
            if(ok[j + 1][i])
30
            {
31
                cnt[i] += cnt[j];
32
                dp[i] += dp[j] + cnt[j] * (i - j) * (i - j);
33
            }
34

35
    D(dp[n]);
36
}

🎈模板#

头文件#

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
}

自动取模#

1
constexpr int mod = 998244353;
2

3
template <class T>
4
constexpr T ksm(T a, ll b) {
5
    T res = 1;
6
    while (b) {
7
        if (b & 1)
8
            res *= a;
9
        b >>= 1;
10
        a *= a;
11
    }
12
    return res;
13
}
14

15
template <int P>
16
struct MInt {
17
    int x;
18
    constexpr MInt() : x() {}
19
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
20
    static int Mod;
21
    constexpr static int getMod() {
22
        if (P > 0) {
23
            return P;
24
        } else {
25
            return Mod;
26
        }
27
    }
28
    constexpr static void setMod(int Mod_) {
29
        Mod = Mod_;
30
    }
31
    constexpr int norm(int x) const {
32
        if (x < 0) {
33
            x += getMod();
34
        }
35
        if (x >= getMod()) {
36
            x -= getMod();
37
        }
38
        return x;
39
    }
40
    constexpr int val() const {
41
        return x;
42
    }
43
    explicit constexpr operator int() const {
44
        return x;
45
    }
46
    constexpr MInt operator-() const {
47
        MInt res;
48
        res.x = norm(getMod() - x);
49
        return res;
50
    }
51
    constexpr MInt inv() const {
52
        assert(x != 0);
53
        return ksm(*this, getMod() - 2);
54
    }
55
    constexpr MInt &operator*=(MInt rhs) & {
56
        x = 1LL * x * rhs.x % getMod();
57
        return *this;
58
    }
59
    constexpr MInt &operator+=(MInt rhs) & {
60
        x = norm(x + rhs.x);
61
        return *this;
62
    }
63
    constexpr MInt &operator-=(MInt rhs) & {
64
        x = norm(x - rhs.x);
65
        return *this;
66
    }
67
    constexpr MInt &operator/=(MInt rhs) & {
68
        return *this *= rhs.inv();
69
    }
70
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
71
        MInt res = lhs;
72
        res *= rhs;
73
        return res;
74
    }
75
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
76
        MInt res = lhs;
77
        res += rhs;
78
        return res;
79
    }
80
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
81
        MInt res = lhs;
82
        res -= rhs;
83
        return res;
84
    }
85
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
86
        MInt res = lhs;
87
        res /= rhs;
88
        return res;
89
    }
90
    friend constexpr istream &operator>>(istream &is, MInt &a) {
91
        ll v;
92
        is >> v;
93
        a = MInt(v);
94
        return is;
95
    }
96
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
97
        return os << a.val();
98
    }
99
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
100
        return lhs.val() == rhs.val();
101
    }
102
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
103
        return lhs.val() != rhs.val();
104
    }
105
};
106

107
template <>
108
int MInt<0>::Mod = 998244353;
109

110
template <int V, int P>
111
constexpr MInt<P> CInv = MInt<P>(V).inv();
112

113
using Z = MInt<mod>;

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

牛客周赛 Round 134

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

作者

Hycode

发布于

2026-03-09

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

2026年青鸟工作室招新-机试

牛客周赛 Round 131

PERSISTENCE

☁️体验#

💡题解#

A - Nowcoder Weekly Contest#

题意#

思路#

代码#

B - ICPC Medal#

题意#

思路#

代码#

C - Unique Number#

题意#

思路#

代码#

D - Balanced Array#

题意#

思路#

代码#

E - Maximize The Sum#

题意#

思路#

代码#

F - Palindromic Value#

题意#

思路#

代码#

🎈模板#

头文件#

自动取模#

目录