mobile wallpaper 1
Profile Image of the Author
Hycode
Announcement
欢迎来到我的博客！这里分享我的个人生活与学习日常！
标签
1117 字
3 分钟
牛客周赛 Round 145
2026-05-25
题解
牛客
/
牛客周赛

☁️体验#

是的，如你所见，我上周武汉邀请赛打铁了。

于是我决定今天开把牛客周赛放松一下，顺便水一篇博客。

💡题解#

A - 小红的好串#

题意#

小红定义一个字符串是一个「好串」，当且仅当其恰好含有两种不同的字符。

判断一个长度为 33 且只包含小写字母的字符串 ss 是否是「好串」。

思路#

直接塞到 set 里面，判断大小是否为 22。

代码#

void solve()
{
    string s;
    cin >> s;


    set<char> st(all(s));
    if(st.size() == 2) Yes;
    else No;
}

B - 小红的好串计数#

题意#

给定一个长为 nn 的仅由 00 和 11 组成的字符串 ss。

计算共有多少个 ss 的非空子串是一个「好串」。

思路#

ss 的子串数量为 n×(n+1)2\frac{n \times (n + 1)}{2}。

那么可以得出，好串数量 = n×(n+1)2\frac{n \times (n + 1)}{2} - 非好串数量。

其中，非好串，就是全 0/10 / 1 的子串。

对于长度为 tt 的全 0/10 / 1 串，它的子串数量为 t×(t+1)2\frac{t \times (t + 1)}{2}。

最后答案就是

n×(n+1)2−∑ti×(ti+1)2\frac{n \times (n + 1)}{2} - \sum \frac{t_i \times (t_i + 1)}{2}

代码#

void solve()
{
    int n;
    string s;
    cin >> n >> s;


    s += "#";


    int ans = n * (n + 1) / 2, t = 1;
    for(int i = 1; i <= n; i++)
        if(s[i - 1] == s[i]) t++;
        else
        {
            ans -= t * (t + 1) / 2;
            t = 1;
        }


    D(ans);
}

C - 小红的染色平均数#

题意#

给定一个数组 aa 和颜色标记字符串 ss（0 红、1 蓝），保证至少有一个红和一个蓝。

允许操作：选择两个不同下标 i,ji,j，将 aia_i 加 1、aja_j 减 1（最终数值可为任意整数）。

求使红色元素的平均值等于蓝色元素的平均值所需的最少操作次数，若不可能则输出 −1-1。

思路#

设操作次数为 kk，sumisum_i 为颜色 ii 的和，fif_i 为颜色 ii 的数量。

如果可以通过操作完成要求，那么一定有：

sum0−kf0=sum1+kf1\frac{sum_0 - k}{f_0} = \frac{sum_1 + k}{f_1}

解得，k=∣sum1f0−sum0f1∣f0+f1=∣sum1f0−sum0f1∣nk = \frac{|sum_1 f_0 - sum_0 f_1|}{f_0 + f_1} = \frac{|sum_1 f_0 - sum_0 f_1|}{n}

我们设分子 ∣sum1f0−sum0f1∣|sum_1 f_0 - sum_0 f_1| 为 mm。

显然，只有 m≡0(modn)m \equiv 0 \pmod{n} 时才有合法的 kk。

代码#

void solve()
{
    input(int, n, a);
    string s;
    cin >> s;


    array<int, 2> sum {}, f {};
    f[0] = RG count(s, '0');
    f[1] = n - f[0];


    for(int i = 0; i < n; i++)
        sum[s[i] - '0'] += a[i];


    int m = abs(sum[1] * f[0] - f[1] * sum[0]);


    if(m % n == 0) D(m / n);
    else D(-1);
}

D - 小红的排列构造#

题意#

题意简述：
给定一个长度为偶数 nn 的数组 aa，需要构造两个 1∼n1 \sim n 的排列 bb 和 cc，使得：

  • 对每个下标 ii，aia_i 等于 bib_i 或 cic_i（至少一个成立）；
  • 至少有 n2\frac{n}{2} 个位置满足 ai=bia_i = b_i；
  • 至少有 n2\frac{n}{2} 个位置满足 ai=cia_i = c_i。
    若无法构造，输出 −1-1。

思路#

统计每种元素的频率，显然如果存在频率大于 22 的元素，那肯定是无解的。

优先安排完频率为 22 的元素的位置。

然后排频率为 11 的，如果第一行没有满 n2\frac{n}{2} 个元素，就放在第一行，否则放在第二行。

最后按顺序补上缺失的数。

代码#

void solve()
{
    input(int, n, a);


    vector<int> f(n + 1);
    for(int& i : a)
        {
            f[i]++;
            if(f[i] > 2)
            {
                D(-1);
                return;
            }
        }


    unordered_map<int, vector<int>> g;
    for(int i = 0; i < n; i++)
        if(f[a[i]] == 2)
            g[a[i]].push_back(i);


    vector<vector<int>> b(2, vector<int>(n));
    vector<unordered_set<int>> st(2);


    for(auto& [k, v] : g)
    {
        b[0][v[0]] = b[1][v[1]] = k;
        st[0].insert(k);
        st[1].insert(k);
    }


    for(int i = 0; i < n; i++)
        if(f[a[i]] == 1)
        {
            bool ok = st[0].size() >= n / 2;


            b[ok][i] = a[i];
            st[ok].insert(a[i]);


            f[a[i]]--;
        }


    for(int t : {0, 1})
    {
        int p = 1;
        for(int& i : b[t])
            if(i == 0)
            {
                while(st[t].contains(p)) p++;
                i = p++;
            }


        for(int i = 0; i < n; i++)
            cout << b[t][i] << " \n"[i == n - 1];
    }
}

E - 小红的染色生成树#

题意#

给定一个 nn 个结点、mm 条边的连通简单无向图，每条边染有颜色 0、1 或 2。

要求找出一棵生成树，使得树中边的颜色恰好有两种。

输出任意一棵符合条件的生成树，若不存在则输出 −1-1。

思路#

分为 (0,1)(0,2)(1,2)(0, 1) (0, 2) (1, 2) 三组颜色对，依次进行尝试。

设当前颜色对为 (a,b)(a, b)：

分别按照先 aa 后 bb 和 bb 后 aa 两种顺序对所有的边进行两次遍历。

先只考虑将第一种颜色的边插入，再只考虑第二种颜色。

这样做是为了防止以下情况：

NOTE

第一种颜色的边已经满足生成树了，导致第二种颜色用不上，从而忽略掉合法的情况。

维护连通分量的过程可以使用并查集解决。

代码#

void solve()
{
    int n, m;
    cin >> n >> m;


    vector<array<int, 3>> e;
    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        e.push_back({x, y, c});
    }


    vector<set<int>> p = {{0, 1}, {0, 2}, {1, 2}};
    for(auto& s : p)
    {
        for(int t : {0, 1})
        {
            int a = t ? *s.rbegin() : *s.begin();
            int b = t ? *s.begin() : *s.rbegin();
            DSU dsu(n);
            vector<pair<int, int>> ans;
            set<int> vis;


            for(auto& [x, y, c] : e)
                if(c == a && !dsu.same(x, y))
                {
                    dsu.merge(x, y);
                    ans.emplace_back(x, y);
                    if(!vis.contains(c)) vis.insert(c);
                }
            for(auto& [x, y, c] : e)
                if(c == b && !dsu.same(x, y))
                {
                    dsu.merge(x, y);
                    ans.emplace_back(x, y);
                    if(!vis.contains(c)) vis.insert(c);
                }


            if(ans.size() == n - 1 && s == vis)
            {
                for(auto& [x, y] : ans)
                    cout << x << ' ' << y << endl;
                return;
            }
        }
    }


    D(-1);
}

F - 小红的好串构造#

题意#

给出 TT 组询问。对于每组询问，请构造一个长为 nn 的仅包含小写字母的字符串 ss，使得其中恰好有 kk 个子串是「好串」。

保证 n−1≤k≤2(n−2)n − 1 \le k \le 2 (n − 2)。

思路#

对于长度为 nn 的字符串，子串中「好串」的数量为 kk。

我们先来看几个例子：

abcab...bcabcabcab...bcabc，k=n−1k = n - 1

…\dots，…\dots

abbbb...bcabcabbbb...bcabc，k=2(n−5)+3k = 2 (n - 5) + 3

abbbb...bbcababbbb...bbcab，k=2(n−4)+2k = 2 (n - 4) + 2

abbbb...bbbcaabbbb...bbbca，k=2(n−3)+1k = 2 (n - 3) + 1

abbbb...bbbbcabbbb...bbbbc，k=2(n−2)k = 2 (n - 2)

容易发现，我们可以构造 abbb...bbbcabbb...bbbc，再接上 abcabc...abcabc... 这样的循环序列。

每将 abbb...bbbcabbb...bbbc 右端缩短一位，再添加一位abc...abc... 循环序列，kk 会因为减少了中间的一个 bb 而 −2-2，而右端添上一位 kk 会 +1+1。总的来说，kk 减少了 11。

最初，全 abc...abc... 的 kk 是 n−1n - 1。

那么，对于任意给出的 kk，bbb...bbbbbb...bbb 的长度 m=k−(n−1)+1m = k - (n - 1) + 1。

abbb...bbbaabbb...bbba 的长度就是 m+2m + 2。

剩下需要用 abc...abc... 循环补全的长度为 n−(m+2)n - (m + 2)。

经过归纳，n−1≤k≤2(n−2)n − 1 \le k \le 2 (n − 2) 范围内的所有值都可以通过这种方法构造出来。

代码#

void solve()
{
    int n, k;
    cin >> n >> k;


    int m = k - (n - 1) + 1;
    string s = "a" + string(m, 'b') + "c";


    for(int i = 0; i < n - (m + 2); i++)
        s += "abc"[i % 3];


    D(s);
}

🎈模板#

并查集#

struct DSU {
    vector<int> f, siz;
    int n;


    DSU() {}
    DSU(int _n) {
        n = _n;
        init(_n);
    }


    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }


    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }


    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        f[y] = x;
        siz[x] += siz[y];
    }


    bool same(int x, int y) {
        return find(x) == find(y);
    }


    int size(int x) {
        return siz[find(x)];
    }


    int countKunion(int k) {
        int res = 0;
        for (int i = 1; i <= n; i++)
            if (find(i) == i && siz[i] >= k)
                res++;
        return res;
    }
};

头文件#

# include <bits/stdc++.h>
# define vvcin(_x) for(auto& _e : _x) for(auto& _i : _e) cin >> _i
# define vcin(_x) for(auto& _i : _x) cin >> _i
# define input(_T, _n, _a) int _n; cin >> _n; vector<_T> _a(_n); vcin(_a)
# define D(_x) cout << _x << endl
# define vD(_x) for(int _i = 0; _i < _x.size(); ++_i) cout << (_x[_i]) << " \n"[_i == _x.size() - 1]
# define vvD(_x) for(auto& _e : _x) vD(_e)
# define vcin1(_x) for(int _i = 1; _i < _x.size(); ++_i) cin >> _x[_i]
# define input1(_T, _n, _a) int _n; cin >> _n; vector<_T> _a(_n + 1); vcin1(_a)
# define D1(_x) cout << "# " << _x << endl
# define vD1(_x) for(int _i = 1; _i < _x.size(); ++_i) cout << (_x[_i]) << " \n"[_i == _x.size() - 1]
# define YES cout << "YES" << endl
# define NO cout << "NO" << endl
# define Yes cout << "Yes" << endl
# define No cout << "No" << endl
# define yes cout << "yes" << endl
# define no cout << "no" << endl
# define all(_x) _x.begin(), _x.end()
# define rall(_x) _x.rbegin(), _x.rend()
# define INF LLONG_MAX
# define inf INT_MAX
# define RG ranges::
# define endl '\n'
# define int long long
using namespace std;
typedef long long ll;
constexpr int MOD = 1000000007;
constexpr int mod = 998244353;


void solve()
{


}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
cin >> _;
    while(_--)
        solve();
    return 0;
}
分享

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

牛客周赛 Round 145
https://blog.hycode.qzz.io/posts/nk-weekly-145/post/
作者
Hycode
发布于
2026-05-25
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

牛客周赛 Round 140
相关文章 智能推荐
1
牛客周赛 Round 140
题解 牛客周赛 Round 140 题解
2
牛客周赛 Round 134
题解 牛客周赛 Round 134 题解
3
牛客周赛 Round 131
题解 新年快乐！
4
牛客周赛 Round 128
题解 牛客上绿（1500+）！
5
牛客周赛 Round 127
题解 较为简单的一场周赛
随机文章 随机推荐
1
牛客周赛 Round 131
题解 2026-02-16
2
牛客周赛 Round 140
题解 2026-04-19
3
牛客周赛 Round 128
题解 2026-01-27
4
Codeforces Round 1074 (Div. 4)
题解 2026-01-20
5
牛客周赛 Round 127
题解 2026-01-19
© 2026 Hycode. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录