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

☁️体验#

DSUDSU 还是太有操作了😋

FF 卡死我了，数学太菜😭

💡题解#

A - 小红的区间计数#

题意#

给定三个整数 a,b,ca,b,c 和一个区间 [l,r][l,r]，请你统计区间 [l,r][l,r] 中有多少个整数与 a,b,ca,b,c 中的每一个都不相等。

思路#

模拟即可，注意 a,b,ca,b,c 可能有重复的数。

代码#

void solve()
{
    int a, b, c, l, r;
    cin >> a >> b >> c >> l >> r;


    int ans = r - l + 1;


    set<int> s = {a, b, c};
    for(int i : s)
        if(l <= i && i <= r)
            ans--;


    D(ans);
}

B - 小红的牛魔#

题意#

给你一个长度为 nn 且仅含 'nn'，'ii'，'uu'，'mm'，'oo' 的字符串。

每次操作可以删除一个 "niuniu" 或 "momo" 子串，问能不能把整个字符串删完。

思路#

用数组模拟栈，维护不能及时删掉的部分。

代码#

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


    vector<char> t;
    for(char& c : s)
    {
        t.push_back(c);


        int m = t.size();
        if(m >= 3)
        {
            if(t[m - 3] == 'n' && t[m - 2] == 'i' && t[m - 1] == 'u')
            {
                t.pop_back();
                t.pop_back();
                t.pop_back();
            }
        }


        m = t.size();
        if(m >= 2)
        {
            if(t[m - 2] == 'm' && t[m - 1] == 'o')
            {
                t.pop_back();
                t.pop_back();
            }
        }
    }


    if(t.empty()) Yes;
    else No;
}

C - 小红的矩阵计数#

题意#

给定一个 nn 行 mm 列的矩阵，矩阵中的每个格子包含字符 0、1 或 2。

定义「L 块」为：恰好三个格子组成的连通块，且这三个格子的形状恰好构成一个 L 形（即一个 2×22 \times 2 的方形中的任意三个格子）。

请你统计有多少个「L 块」，其三个格子上的字符互不相同（即三个格子恰好包含 0、1、2 各一个）。

思路#

枚举每个 2×22 \times 2 的方形，如果包含 0、1、2，答案就 +2+2。

代码#

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


    vector<string> a(n);
    vcin(a);


    int ans = 0;


    for(int i = 0; i < n - 1; i++)
        for(int j = 0; j < m - 1; j++)
            if(unordered_set<char>{a[i][j], a[i][j + 1], a[i + 1][j], a[i + 1][j + 1]}.size() == 3)
                ans += 2;


    D(ans);
}

D - 小红的排序（easy）#

解法同 hard version。

E - 小红的排序（hard）#

题意#

给定一个长度为 nn 的排列 [p1,p2,…,pn][p1,p2,…,p_n]​，以及两个正整数 x,yx, y，保证 x,y≤nx, y \le n。

在下标合法范围内，你可以进行任意次以下两种操作：

  • 交换 pip_i 和 pi+xp_{i+x}
  • 交换 pip_i 和 pi+yp_{i+y}

问能否将排列变为升序排列 [1,2,…,n][1,2,\dots,n]。

思路#

对于两个位置来说，可交换就说明这两个位置相互可达，我们可以将它们加入同一个集合。

  • 对于处在正确位置的数，我们不需要管；
  • 对于不处在正确位置的数，即 pi≠ip_i \not= i，我们就需要看它们是否处于同一个集合中。如果不在一个集合中，则整个排列不可能变为升序排列。

代码#

void solve()
{
    int n, x, y;
    cin >> n >> x >> y;


    vector<int> p(n + 1);
    vcin1(p);


    DSU dsu(n);


    for(int i = 1; i <= n; i++)
    {
        if(i + x <= n) dsu.merge(i, i + x);
        if(i + y <= n) dsu.merge(i, i + y);
    }


    for(int i = 1; i <= n; i++)
        if(p[i] != i && !dsu.same(p[i], i))
        {
            No;
            return;
        }


    Yes;
}

F - 小红的三角形构造#

题意#

给定一个正整数 xx，现在需要构造一个直角三角形，满足其三边长均为正整数，且至少有一边长恰好等于 xx。

请你判断是否存在这样的三角形，如果存在，请给出任意一个合法构造。

思路#

构造勾股数 a2+b2=c2a^2 + b^2 = c^2：

  • a=n2−m2a = n^2 - m^2
  • b=2nmb = 2nm
  • c=n2+m2c = n^2 + m^2

如果 xx 是奇数，设 x=a=(n+m)(n−m)x = a = (n+m)(n-m)：

  • n+m=xn + m = x
  • n−m=1n - m = 1

解得，n=x+12,m=x−12n = \frac{x+1}{2}, m = \frac{x-1}{2}

如果 xx 是偶数，设 x=b=2nmx = b = 2nm:

解得，n=x2,m=1n = \frac{x}{2}, m = 1

然后分别将 n,mn, m 代入公式求解出 a,b,ca, b, c 即可。

代码#

void solve()
{
    int x;
    cin >> x;


    if(x < 3)
    {
        No;
        return;
    }


    Yes;
    if(x & 1)
    {
        int n = (x + 1) / 2, m = (x - 1) / 2;
        cout << x << ' ' << 2 * n * m << ' ' << n * n + m * m << endl;
    }
    else
    {
        int n = x / 2, m = 1;
        cout << n * n - m * m << ' ' << x << ' ' << n * n + m * m << endl;
    }
}

G - 小红的生成树构造#

题意#

给定一个无向连通图，每个顶点有颜色 A/B/C/DA/B/C/D。需要找出一棵生成树，使得：

  • 在生成树中，删除所有 C/DC/D 顶点后，剩下的 A/BA/B 顶点形成的每个连通块里同时含有 AA 和 BB（即每个 AA 都能不经过 C/DC/D 到达某个 BB，每个 BB 也能不经过 C/DC/D 到达某个 AA）。
  • 在生成树中，删除所有 A/BA/B 顶点后，剩下的 C/DC/D 顶点形成的每个连通块里同时含有 CC 和 DD（即每个 CC 都能不经过 A/BA/B 到达某个 DD，每个 DD 也能不经过 A/BA/B 到达某个 CC）。

如果存在这样的生成树，输出任意一种方案；否则报告无解。

思路#

A/BA/B 和 C/DC/D 各分一类。

首先，只看每一类内部的边，其他点和边视为空气，检查每个点是否可以相互连通，且每一类都要包含该类的两种颜色。

然后看是否存在一条边把两类连接起来。

另外，需要注意只有一个类的情况。

代码#

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


    string s;
    cin >> s;
    s = " " + s;


    vector<pair<int, int>> p(m), pab, pcd;
    for(auto& [x, y] : p)
        cin >> x >> y;


    DSU ab(n), cd(n);
    for(auto& [x, y] : p)
        if((s[x] == 'A' || s[x] == 'B') && (s[y] == 'A' || s[y] == 'B'))
            if(!ab.same(x, y))
            {
                ab.merge(x, y);
                pab.push_back({x, y});
            }


    for(auto& [x, y] : p)
        if((s[x] == 'C' || s[x] == 'D') && (s[y] == 'C' || s[y] == 'D'))
            if(!cd.same(x, y))
            {
                cd.merge(x, y);
                pcd.push_back({x, y});
            }


    unordered_set<int> rtab, rtcd;
    unordered_map<char, int> f;
    for(int i = 1; i <= n; i++)
    {
        f[s[i]]++;
        if(s[i] == 'A' || s[i] == 'B') rtab.insert(ab.find(i));
        else rtcd.insert(cd.find(i));
    }


    if(max(rtab.size(), rtcd.size()) > 1)
    {
        No;
        return;
    }


    if((f['A'] + f['B']) && f['A'] * f['B'] == 0 || (f['C'] + f['D']) && f['C'] * f['D'] == 0)
    {
        No;
        return;
    }


    pair<int, int> link {0, 0};
    for(auto& [x, y] : p)
        if((s[x] == 'A' || s[x] == 'B') && (s[y] == 'C' || s[y] == 'D') ||
           (s[x] == 'C' || s[x] == 'D') && (s[y] == 'A' || s[y] == 'B'))
        {
            link = {x, y};
            break;
        }


    if(!link.first && min(rtab.size(), rtcd.size()) > 0)
    {
        No;
        return;
    }


    Yes;
    if(link.first) cout << link.first << ' ' << link.second << endl;


    for(auto& [x, y] : pab) cout << x << ' ' << y << endl;
    for(auto& [x, y] : pcd) cout << x << ' ' << y << endl;
}

🎈模板#

并查集#

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 140
https://blog.hycode.qzz.io/posts/nk-weekly-140/post/
作者
Hycode
发布于
2026-04-19
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

牛客周赛 Round 145
2026年青鸟工作室招新-机试
相关文章 智能推荐
1
牛客周赛 Round 145
题解 牛客周赛 Round 145 题解
2
牛客周赛 Round 134
题解 牛客周赛 Round 134 题解
3
牛客周赛 Round 131
题解 新年快乐！
4
牛客周赛 Round 128
题解 牛客上绿（1500+）！
5
牛客周赛 Round 127
题解 较为简单的一场周赛
随机文章 随机推荐
1
Codeforces Round 1074 (Div. 4)
题解 2026-01-20
2
2026年青鸟工作室招新-机试
题解 2026-03-27
3
Codeforces Round 1072 (Div. 3)
题解 2026-01-15
4
牛客周赛 Round 134
题解 2026-03-09
5
牛客周赛 Round 145
题解 2026-05-25
© 2026 Hycode. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录